Printer Friendly

Chromatic polynomials and rings in species.

One well-known invariant of a graph g is its chromatic polynomial x(g; q), whose evaluation at a nonnegative integer k counts the number of proper k-colorings of a graph [BL46]. Moreover, there are many generalizations, to the Tutte polynomial [Tut54] and the chromatic symmetric function [Sta95]. Here are some classical results:

Theorem 1 Let g be a graph with edge set E.

1. [chi](g; q) = [summation over ([pi])] q(q - 1) ... (q - [absolute value of n] + 1), where we sum over all stable partitions of g.

2. ([Tut54]) [chi](g; q) = [chi](g - e; q) - [chi](g/e; q) for any edge e of g, where g/e is contraction.

3. ([Whi32]) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [L.sub.g] is the bond lattice of g.

4. ([Whi32]) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where c(A) is the number of components of (V (g),A).

All terminology needed to understand these results appear in this paper. Several of these identities have been extended in various ways [Tut54, Ber73, Sta95, GS01, Hum11]. The goal of this present paper is to present a generalization of chromatic polynomials and symmetric functions, and extend the above results, by working with lattice rings in species. While the details are abstract, our results are similar to the Mobius Inversion formula: general algebraic results which give combinatorial results as corollaries. In particular, given any combinatorial setting where our framework applies, one immediately gets an analogue of the Tutte polynomial, and a variation of Theorem 1 for this invariant.

Our philosophy is to replace graphs with any notion of combinatorial objects which have operations analogous to disjoint union and taking induced subgraphs. Such a construction is an abelian Hopf monoid in species [AM10]. Given an abelian Hopf monoid in species, there is a notion of coloring, and the first three results of Theorem 1 generalize to this setting.

Our motivation comes from the work of Aguiar, Bergeron, and Sottile [ABS06], who showed that quasisymmetric functions form the terminal object in the category of combinatorial Hopf algebras. For example, graphs form a graded Hopf algebra, and the resulting map to quasisymmetric functions sends a graph g to its chromatic symmetric function. Thus, one obtains analogues of chromatic symmetric functions. However, the results of Theorem 1 have not been extended to arbitrary combinatorial Hopf algebras. Moreover, known results can have very involved proofs. For instance, in [HM12], a formula for the antipode of the Hopf algebra of graphs is proven, using a very complicated argument. However, with a deletion-contraction recurrence, one could reprove their result following Stanley's proof that [(-1).sup.[absolute value of g]] [chi](g; -1) is the number of acyclic orientations of g [Sta73]. So our goal is to create new invariants, and prove new results about these invariants.

The foundation for our work is Joyal's category of species [Joy81], where we can define the bond lattice. Moreover, the notion of bond lattice comes from the study of Galois connections, and a natural action of set partitions that is analogous to the action of integers on any abelian group. Naturally, in order to say that set partitions act on abelian Hopf monoids, we need to define the notion of ring in species. Rings in species are defined in ongoing joint work with Aguiar and Mahajan [AMW], as an attempt to generalize and understand Hopf rings [RW74] over other categories. We mention some of the axioms for the definition in this paper, as well as the result that every abelian Hopf monoid in species is a module over set partitions.

Our goal is to study 'graded lattice rings' and their modules. Given a module over a graded lattice ring, we can define a generalization of the chromatic polynomial, where the definition involves Mobius inversion, similar to Whitney's formula for the Tutte polynomial of a matroid. To justify that our setting is non-trivial, we give two examples of new enumerative invariants in Sections 5 and 6.

The paper is organized as follows. First, in Section 1, we review the definition of rings in species, and some fundamental results. Then in Section 2, we define our characteristic polynomials and chromatic symmetric functions, and verify Theorem 1, part 1. In Section 3, we prove some basic properties, and a generalization of Theorem 1, part 2, regarding deletion and contraction. In Section 4, we study coclosure operators, Galois connections, and generalizations of Theorem 1, part 3 and part 4. The last two section involves studying new examples related to blocks of graphs, and digraphs.

We acknowledge that we have had many fruitful conversations with Aguiar and Mahajan regarding this present work, which is related to an ongoing project [AMW]. Results obtained in joint work which we have chosen to mention in this abstract will be given appropriate attribution. Finally, we assume familiarity with terminology from the theory of posets, as presented in [Sta97, Rot64].

1 Rings in Species

We begin with some review of known and new material, regarding rings of species. Most of this comes from ongoing joint work with Aguiar and Mahajan [AMW], or previous material [AM10, Joy81].

Definition 2 A species (with restrictions) is a contravariant functor P: [set.sup.x] [right arrow] Set from the category of finite sets with injections to the category of all sets. It is connected if [absolute value of [P.sub.0]] = 1.

In this paper, all species are assumed to be connected. In particular, for every finite set I we have a set [P.sub.I] of I-structures with label set I. Moreover, any injection [sigma]: I [right arrow] J lifts to a map [P.sub.[sigma]]: [P.sub.J] [right arrow] [P.sub.I]. For a subset S [subset] I, we call this the restriction map [[rho].sub.I,S]: [P.sub.I] [right arrow] [P.sub.S]. For x [member of] [P.sub.I], we let x[|.sub.S] denote its image under [[rho].sub.I,S]. Species (with restrictions) were originally introduced by Joyal [Joy81], and have found applications in the theory of enumeration [BLL98].

Example 3 For these examples, fix a finite set I, and a subset S [subset] I.

* Let [G.sub.I] denote the collection of all graphs with vertex set I. This is a species with restrictions: for a graph g with vertex set I, g[|.sub.S] is the subgraph induced by S.

* Let [[PI].sub.I] denote the collection of all set partitions on I. Given a set partition [pi], [pi][|.sub.S] is given by replacing each part B of [pi] by B [intersection] S, and then removing empty parts. For instance, let [pi] = {{1, 2, 3}, {4, 5}, {6, 7}} = 123145167. Then [pi][|.sub.{1,2,5}] = 12|5.

Hopf monoids are a generalization of Hopf algebras [Mon93], defined with respect to any braided monoidal category [AM10]. However, for the abstract, we work with species.

Definition 4 A species (with restrictions) P is a Hopf monoid if there is a collection of maps [[??].sub.S,T]: [P.sub.S] x [P.sub.T] [right arrow] [P.sub.S[??]T] for any disjoint sets S and T, which is natural in S and T, and is associative. Given x [member of] [P.sub.S], y [member of] [P.sup.T], we let x [??] y denote their image under the map [[??].sub.S,T]. Then associativity means that, for three disjoint sets R, S, T, and x [member of] PR, y [member of] [P.sub.S], z [member of] [P.sub.T], we have (x [??] y) [??] z = x [??] (y [??] z). The Hopf monoid is abelian if x [??] y = y [??] x, where the equality involves identifying [P.sub.S] x [P.sub.T] [equivalent] [P.sub.T] x [P.sub.S].

Viewing [P.sub.I] as a collection of combinatorial objects, [[??].sub.S,T] is a rule for how to combine combinatorial objects with disjoint labels, where the order does not matter, and satisfying axioms which allow us to define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any collection of finite sets. There are other axioms involving units and counits, and there is a notion of negation (called the antipode). We omit these details for length considerations.

Definition 5 Let R be an abelian Hopf monoid, such that each [R.sup.I] is also a commutative monoid with multiplication [*.sub.I] and identity [1.sub.I]. Then R is a ring of species if multiplication distributes over addition: for disjoint sets S, T, x [member of] [R.sub.S[union]T], y [member of] [R.sub.S], z [member of] [R.sub.T], we have x x (y [??] z) = x[|.sub.S] x y [??] x[|.sub.T] x z.

Ring in species is a special case of a more general notion of a ring in a distributive category [AMW]. The main feature of a ring in species is that multiplication is defined for objects with the same label set, and addition is defined for objects with disjoint label sets.

Example 6 Now we mention some examples of rings in species.

* Consider G, the species of graphs. Addition is given by sending a pair of graphs (g, h) to their disjoint union g [??] h, while multiplication is given by sending pairs of graphs to their intersection g [intersection] h, the graph which contains only edges that are in both g and h.

* The species n is also a ring in species, where addition is given by disjoint union. That is, given set partitions [pi], [sigma] on disjoint label sets, [pi] [??] [sigma] is the set partition consisting of all the parts of [pi] and [sigma]. For instance, 12|3 [??] 456 = 12|3|456. If n and a are partitions of the same set, then their product is [pi] [conjunction] [sigma], their most common refinement. For instance, 131245 [conjunction] 1|23|45= 1|2|3|45.

Definition 7 Let R be a ring in species, and let P be an abelian Hopf monoid. Then P is a module over R if, for each I [R.sub.I] acts on [R.sub.I]. For each r [member of] [R.sub.I], p [member of] [R.sub.I], let r [??] p [member of] [R.sub.I] denote the action of r on p.

1. For r, s [member of] [R.sub.I], and p [member of] [R.sub.I], we have r [??] (s [??] p) = (r x s) [??] p. Moreover, [1.sub.I] [??] p = p.

2. For a disjoint union I = S [union] T, and r [member of] [R.sub.I], p [member of] [P.sup.S], q [member of] [P.sub.T], we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Moreover, if P is also a ring, R is commutative, and r [??] (s x p) = (r [??] s) x p = s x (r [??] p), for all r [member of] [R.sub.I], s, p [member of] [R.sub.I], then R is an algebra over P.

In the work of Aguiar and Mahajan [AM13], they study a 'characteristic' action of set partitions on every Hopf monoid. Using rings in species, we can restate their results in a succint way:

Proposition 8 ([AMW]) Let P be an abelian Hopf monoid in species. Then P is a module over n. If P is a ring, then P is an algebra over n.

The action is given as follows: let p [member of] [R.sub.I], [pi] [member of] [[PI].sub.I]. Then [pi] [??] p = [[??].sub.B[member of][pi]] p[|.sub.B], where we are taking the sum over all parts of the partition [pi]. This simple proposition is what allows us to prove results regarding bond lattices, stable partitions, and other simple properties of chromatic polynomials. This proposition is also the primary motivation for working with species. If we worked with graded Hopf algebras instead, then it turns out that [PI] is replaced by the Hopf ring of symmetric functions. Unfortunately, the resulting action is not as well-behaved, as it involves Kronecker products, which do not turn symmetric functions into a graded lattice. Using this action, we generalize the notion of 'connected components' of a graph to any element x in any abelian Hopf monoid P.

Definition 9 Given P and x G [R.sub.I], let [[pi].sub.x] be the most refined partition for which [pi] [??] x = x. We call the parts of [[pi].sub.x] the components of x.

For generalizations of Tutte polynomials, we need a ring in species to have extra structure.

Definition 10 A lattice ring in speces is a ring R such that:

1. The multiplication on [R.sub.I] is idempotent and commutative.

2. [R.sub.I] is a finite set.

3. Addition is an order-preserving operation [[??].sub.S,T]: [R.sub.S] x [R.sub.T] [right arrow] [R.sub.I], where we are using cartesian product of posets.

4. Moreover, if each [R.sub.I] is graded, then we call R a graded lattice ring if for all x [member of] [R.sub.S], y [member of] [R.sub.T], we have [[rho].sub.I] (x [??] y) = [[rho].sub.S] (x) + [[rho].sub.T] (y), where [[rho].sub.A] is the rank function of [R.sub.A].

The species G and n are examples of graded lattice rings. Also, the first two axioms force [R.sub.I] to be a lattice for all I, hence the name (graded) lattice ring.

2 Characteristic invariants for Abelian Hopf Monoids

In this section we define the polynomial and symmetric invariants which are the focus of our study. In each case, we focus on the example of graphs. Throughout, we let Z[t] be the polynomial ring in the variable t, and let [LAMBDA] be the ring of symmetric functions in the commuting indeterminates x = [x.sub.1], [x.sub.2], ..., with coefficients in a field K.

Given a graded poset P with bottom element [??] and top element [??], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote the characteristic polynomial of P, where [rho] is the rank function of P.

Definition 11 Let M be a module over a graded lattice ring R, and let Z[x]([M.sub.I]) denote the free Z[x]-module with generating set {m: m [member of] [M.sub.I]}. Given a finite set I, and m [member of] [M.sub.I], we define the characteristic polynomial of m to be

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is an element of Z[x]([M.sub.I]).

We write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and call these coefficients the characteristic polynomials for the pair (m, m'). There are three reasons we work in Z[x]([M.sub.I]). First, there is no general analogue of the edgeless graph for an arbitrary module. Second, in the next section we derive some combinatorial results about invariants for pairs (m, m') that we would not have noticed if we only focused on specific values of m'. Finally, by choosing to work in a free module, we obtain different results for any specialization where we replace elements of [M.sub.I] by polynomials or symmetric functions.

Let R = [PI], and M = G, and let g be a graph with vertex set I. Finally, let [d.sub.I] denote the edgeless graph on I. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Set partitions n for which [pi] [??] g = d are called stable partitions. Thus, by Theorem 1, part 1, [[chi].sub.[PI],G](g, d; x) = [chi](g; x). Similarly, if we replace the graphs h by [(t + 1).sup.e(h)], where e is the number of edges of h, then [[chi].sub.[PI],G] (g, x) specializes to the bad chromatic polynomial, which enumerates all colorings, weighting each coloring by [(t + 1).sup.m], where m is the number of monochromatic edges in the coloring.

Now allow M to be any abelian Hopf monoid in species, and let m [member of] [M.sub.I], and fix a set S. We generalize the chromatic symmetric function to this setting. Given any function f: I [right arrow] S, and m [member of] M, we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For the case of graphs, given a graph g, and a coloring f, g[|.sub.f] is the subgraph of g with the same vertex set, and only the edges of g whose endpoints get the same color. Given x = [x.sub.1], ..., a sequence of commuting indeterminates, and a coloring f, we weight f by [x.sup.f] = [[PI].sub.i[member of]I] [x.sub.f(i)]. Then

[[??].sub.M] (m; x) = [summation over (f:I[right arrow]P)] [x.sup.f] m[|.sub.f]

is the chromatic symmetric function of m, which lies in the free [LAMBDA]-module on the set [M.sub.I].

Proposition 12 We have the following results.

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

* For x [member of] N, [[chi].sub.[PI],M](m; x) = [summation over (f:I[right arrow]{1...f})]m[|.sub.f].

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [m.sub.[lambda]([pi])] are the augmented monomial symmetric functions, and [lambda]([pi]) consists of the sizes of the blocks of n, written in decreasing order.

In particular, for R = [PI], the characteristic polynomial has an interpretation in terms of coloring, and it generalizes to a symmetric function invariant. This leads to the following open question:

Question 1 What sufficient conditions on a graded lattice ring R are needed so that [[chi].sub.R,M](m; x) [member of] N for all x [member of] N, m [member of] [M.sub.I], and for all modules M over R?

Now we generalize the Tutte polynomial, following the definition given by Sokal [Sok05], which is equivalent to the classical Tutte polynomial.

Definition 13 Let R be an algebra over a graded lattice ring L in species, and assume that R is also a lattice ring. Given r [member of] [R.sub.I], let [l.sub.r] be the minimum element of [L.sub.I] such that [l.sub.r] [??] r = r. We call this the L-closure of r. Letting [rho] denote the rank function of [L.sub.I], the Tutte polynomial is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We have not shown that the L-closure is a well-defined operation: this is the content of Lemma 18. As we shall see in Theorem 22, the Tutte polynomial and characteristic polynomials are related by Mobius inversion. Let L = [PI] and R = G. Then [T.sub.[PI],G] (g; x) = [[summation].sub.h[subset]g] [x.sup.c(h)]h, where we are summing over all spanning subgraphs of G. Replacing h with [t.sup.e(h)], we obtain Sokal's definition of the Tutte polynomial.

3 Simple Identities and Deletion-Contraction

In this section, we describe a few simple identities for characteristic invariants, including a generalization of the deletion-contraction recurrence. This generalizes Theorem 1, part 2. All of these identities follow from elementary manipulations, and generalizations of properties of rings and their modules.

Proposition 14 ([AMW]) Let P be an abelian Hopf monoid. Fix a finite set I, and p, p' [member of] [P.sub.I]. Then

[[??].sub.P] (p; x + y) = [summation over (s[subset]I)] [[??].sub.P] (p[|.sub.S]; x) [[??].sub.P](p[|.sub.I\S]; y)

where x + y means that we set [x.sub.i] = [x.sub.i] + [y.sub.i] for each i, where the [x.sub.i] and [y.sub.i] are commuting indeterminates.

Also, by working with pairs (m, m'), we have found a new identity for chromatic polynomials.

Proposition 15 Let P be an abelian Hopf monoid. Fix a finite set I, p, p' [member of] [P.sub.I], and let q, t [member of] Z. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For graphs, this identity is equivalent to [chi](g; qt) = [[summation].sub.h[subset]g] [chi](g/h; q) [chi](h; t), where we sum over all spanning subgraphs h of g. It is an easy exercise to find a combinatorial proof.

Proposition 16 Let R be a ring in species, and let M be a module over R. Fix a finite set I, and r [member of] [R.sub.I], m, m' [member of] [M.sub.I]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover, this identity remains true if M is an algebra over R, and we choose r [member of] [M.sub.I] instead.

Consider the case R = [PI] and M = G, the ring of graphs. Let g, h be graphs, and let r = g - e, for some edge e [member of] E(g)\E(h). Applying the proposition in this case, we obtain the deletion contraction recurrence. A similar result holds when working with chromatic symmetric functions, obtained with Aguiar and Mahajan. We also obtained the following corollary.

Corollary 17 ([AMW]) Let G be the ring of graphs, and let I be a finite set, g, h [member of] [G.sub.I]. Then

1. If E (g) [subset] E(h), then [[??].sub.G] (g, h; x) = [p.sub.[lambda](h)], where [lambda](h) is the sizes of the components of h, written in decreasing order.

2. Otherwise, given e [member of] E(g)\E(h), we have

[[??].sub.G] (g, h;x) = [[??].sub.G] (g - e, h;x) - [[??].sub.G] (g, h + e;x).

4 Coclosure Operators and Galois Connections

Given a module M over a graded lattice ring R, and an element m [member of] [M.sub.I], we can define a coclosure operator on [R.sub.I]. Moreover, when M is also a lattice ring, we can obtain a Galois connection. We use the coclosure operator to define the bond lattice. In this section, we detail these two results, and demonstrate how to compute the characteristic invariants from the bond lattices, thus generalizing Theorem 1, parts 3 and 4. We define coclosure operator in Proposition 19, and define Galois connection in Proposition 23. The bond lattice L(g) of g is the collection of all set partitions [pi] of V(g) such that, for each block B of [pi], g[|.sub.B] is connected. The partial order for L(g) is refinement. The bond lattice is defined by a coclosure operator on [[PI].sub.I], which is the basis of our generalization.

Lemma 18 Let R be a graded lattice ring, M an R-module, m [member of] [M.sub.I]. If r [??] m = s [??] m for r, s [member of] [R.sub.I], then (r [conjunction] s) [??] m = r [??] m.

For m [member of] [M.sub.I], let [r.sub.m] denote its R-closure, which is well-defined. For fixed m, and s [member of] [R.sub.I], define [s.sup.m] = [r.sub.s<m]. Then [s.sup.m] is the minimum r [member of] [R.sub.I] such that r [??] m = s [??] m.

Proposition 19 Let m [member of] [M.sub.I], where M is a module over a graded lattice ring R in species. Then the map [(-).sup.m]: [R.sub.I] [right arrow] [R.sub.I] which sends s to [s.sup.m] is a coclosure operator, meaning that, for all s, t [member of] [R.sub.I], [s.sup.m] [less than or equal to] t if and only if [s.sup.m] [less than or equal to] [t.sup.m].

A ring element r is m-closed if [r.sup.m] = r. The collection of closed elements forms the m-closure lattice [R.sub.m], with the same join operation from [R.sub.I]. For G, and R = [PI], then [[PI].sub.g] is the bond lattice of g.

Theorem 20 Let R be a graded lattice ring with rank function [rho], M be an R-module, I be a finite set, and m [member of] [M.sub.I]. Furthermore, let [L.sub.m] denote the lattice of m-closed elements in [R.sub.I], and let r [member of] [L.sub.m]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 21 Let M be an abelian Hopf monoid, m [member of] [M.sub.I]. Furthermore, let [L.sub.m] denote the lattice of m-closed elements in [[PI].sup.I], and let [sigma] [member of] [L.sub.m]. Then, in terms of power sum symmetric functions,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now we extend Theorem 1, part 4, which is the subset expansion formula for chromatic polynomials. Our extension comes from two facts: first, the Tutte polynomial and the bad chromatic polynomial of a graph are equivalent, up to substitution. Second, the subset expansion is a summation of Mobius function values over the lattice of graphs, ordered by inclusion of edge sets. Consider the free Z[x]-module Z[x]([R.sub.I]), where [R.sub.I] is a lattice ring in species, and let [[mu].sub.R]: Z[x]([R.sub.I]) [right arrow] Z[x]([R.sub.I]) be the linear transformation defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This linear transformation is invertible, with inverse [[zeta].sub.R]: Z[x]([R.sub.I]) [right arrow] Z[x]([R.sub.I]) given by [[zeta].sub.R](r) = [[summation].sub.s[less than or equal to]r] s. The Tutte polynomial and characteristic polynomial are equivalent, up to Mobius inversion.

Theorem 22 Let S be a lattice ring in species, and an algebra over the graded lattice ring R. Let I be a finite set, s [member of] [S.sub.I].

1. [[chi].sub.R,S] (r; x) = [[mu].sub.s] [omicron] [T.sub.R,S] (r; x)

2. [T.sub.R,S] (r; x) = [[zeta].sub.R] [omicron] [[chi].sub.R,S] (r; x)

In particular, the characteristic polynomial for a pair (r, r') are given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similarly, the chromatic symmetric function for a pair (r, r') is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The fact that Mobius functions may vary for different elements in a lattice ring is the primary reason why we have chosen our invariants to lie in free modules Z[x]([M.sub.I]), rather than being elements of Z[x]. When M = G and R = n, then the Mobius function is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], so one recovers the familiar result that the bad coloring polynomial and the Tutte polynomial are equivalent, up to substitution.

The proof of Theorem 22 relies on basic facts about Mobius inversion and Galois connections, as in [Rot64]. When M is a lattice ring in species, and an algebra over R, then the coclosure operator comes from a natural Galois connection. Let [phi]: [M.sub.I] [right arrow] [R.sub.I] be the order-preserving map given by m [??] [r.sub.m]. For a fixed m [member of] [M.sub.I], let [psi]: [R.sub.I] [right arrow] [[??], m] be the order-preserving map given by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proposition 23 Let M be a lattice ring in species, and an algebra over R, a graded lattice ring in species. Then for m [member of] [M.sub.I], the pair ([psi][|.sub.[[??],m]], [psi]) forms a Galois connection. In other words, for all n [member of] [[??], m] and s [member of] [R.sub.I], we have [r.sub.n] [less than or equal to] s if and only if n [less than or equal to] s [??] m.

5 Block Tutte Polynomial of a Graph

In this section, we apply our results to the study of new polynomial invariants of graphs, based on studying the blocks of a graph. A (non-trivial) block of a graph g is a maximal subgraph h on at least two vertices with no cut vertex. Then h is either a bridge of g, or a maximal 2-connected subgraph. We identify blocks with their vertex sets for the rest of this section. Background regarding blocks can be found in [Die10].

The structure of the blocks of a graph g is known, although our approach to the structure will use hypergraphs. Recall that a hypergraph is a pair h = (V, E), where E [subset] [2.sup.V]. Given a graph g, let h be the hypergraph on the same vertex set with hyperedges S, one for each block S of g. Then h is a linear hyperforest, the block forest of g. A hypergraph h is linear if any two hyperedges of h intersect in at most one vertex. A linear hyperforest is a linear hypergraph which does not have an elementary hypercycle, which is any sequence ([[upsilon].sub.0], [e.sub.0], [[upsilon].sub.1], [e.sub.2], ..., [e.sub.k], [[upsilon].sub.0]) such that {[[upsilon].sub.i], [[upsilon].sub.i+1]} [subset] [e.sub.i], [[upsilon].sub.0] [member of] [e.sub.k], and [[upsilon].sub.0], ..., [[upsilon].sub.k], [e.sub.0], ..., [e.sub.k] are all distinct. We also assume that linear hyperforests have no hyperedges of size one.

Linear hyperforests form a graded lattice ring F, in species, which act on G. The species F is an abelian Hopf monoid, where addition is given by disjoint union. Given two linear hyperforests f and f', we define their product as follows: f x f' has edge set {e [intersection] e': e [member of] f, e' [member of] f'}\{0}. As such, [PI] is a subring of F. Thus [F.sub.I] is a graded lattice, and is isomorphic to the lattice [[summation].sup.2.sub.n,2] appearing in [BBL+99]. The rank of a hyperforest f is 2[absolute value of I] - 2 c(f) - e(f), where c(f) is the number of components, and e(f) is the number of hyperedges. Finally, the rank of I is 2[absolute value of I] - 3.

Now let G be the lattice ring of graphs. Then F acts on G as follows: given f [member of] [F.sub.I], and g [member of] [G.sub.I], we let f [??] g be the graph with edge set {e [member of] g: e [subset or equal to] e' [member of] f for some e'}. That is, we remove any edge from g that is not contained in some hyperedge of f. Then G is an algebra over F. Consider a fixed graph g. Then [F.sub.g] consists of all linear hyperforests f on V(G) such that, for each hyperedge S of f, g|S has no cut vertex. Moreover, [f.sub.g], the F-closure of G, is the block hyperforest of g, as in Figure 5. Thus, for g [member of] G, we have

[T.sub.F,G](g; x) = [summation over (h[subset]g)] [x.sup.2c(h)+b(h)-3]h

where b(h) is the number of non-trivial blocks of h. From our general theory, we obtain a natural invariant of graphs, which enumerates spanning subgraphs, with weights based on the number of connected components and the number of blocks. Moreover, from our general framework we obtain analogues of Theorem 1. An open question is to determine nice combinatorial interpretations for [[chi].sub.F,G] (g; x) when x [member of] N.

6 Strong Tutte Polynomial of a Directed Graph

In this section, we apply our results to the study of new polynomial invariants of directed graphs, or digraphs, based on studying the strongly connected components. A strongly connected component of a digraph [??] is a maximal subgraph [??], such that, for every pair of distinct vertices u and v, there is a directed path from u to [upsilon]. There is a combinatorial structure encoding the strongly connected components of [??]. A DAP (directed acyclic partition) is a pair [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [pi] is a set partition, and [??] is an acyclic digraph with vertex set given by the blocks of [pi]. Given [??], let [pi] denote the partition of V([??]) into its strongly connected components. Then direct an edge between two parts of [pi] if there is an edge between the corresponding components. We call this the associated DAP. An example appears in Figure 6. It turns out that DAPS form a graded lattice ring [??] in species, which act on [??], the lattice ring of directed graphs. The species [??] forms a ring in a way similar to graphs: restriction is given by induced subdigraphs, addition is given by disjoint union, and multiplication is given by intersection.

For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and S [subset] I, the restriction [??][|.sub.S] is given by restricting each part of [pi] to S, and sending directed edges (B, B') to (B [intersection] S, B' [intersection] S) when both sets are non-empty. Addition is given by disjoint union. For the multiplication structure, it is easier to define the cover relations of the resulting partitial order on [[??].sub.I]: given a DAP [pi], there are two types of cover relations:

* Suppose [??] has blocks B, B' where (B, B') is an arc. Then replacing B and B' with their union, and contracting the arc (B, B') gives a new DAP [??] which covers [??].

* Suppose [??] has blocks B, B' that have no arcs between them. If adding the arc B, B' does not create a cycle, then we may add it, to obtain a new DAP [??], which covers [??].

This does turns [[??].sub.I] into a graded lattice, with rank function [rho]([??]) = 2n - [absolute value of [pi]] - c([pi]), where c([pi]) are the number of components of the digraph on the blocks of [pi]. The rank of [??] is 2[absolute value of I] - 2. Then [??] acts on [??] as follows: given [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the directed graph obtained from [??] by removing any directed edge u, [upsilon], if u and [upsilon] are in distinct parts B, B' of [??], unless (B, B') is a directed edge of [??]. Moreover, for fixed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] consists of all daps [??] such that, for each block B, [??][|.sub.B] is strongly connected, and such that there are no directed edges from parts B, B' whenever there is no arc of [??] with source in B and target in B'. Moreover, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the closure of [??], forms an analogue of the notion of block forest. It is obtained by partitioning [??] into its strongly connected components, and then taking the quotient digraph, (so two parts are connected by an arc if and only if there is an arc between the corresponding vertex sets in [??]). This quotient is sometimes called the condensation of [??]. Note that since we are working with species, the vertices of the condensation are labeled by the sets we quotiented out by, which is how we arrived at the notion of a DAP. Thus, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where s([??]) is the number of strongly connected components of [??]. From our general theory, we obtain a very natural invariant of digraphs, which enumerates spanning subdigraphs, with weights based on the number of components and strongly connected components. Due to all the results in Theorem 1 generalizing to this situation, this makes T a natural analogue of the Tutte polynomial for digraphs. Of course, this is not the only possible analogue [CG95], although it does have the advantage that we get a notion of 'bond lattice' for our new invariant.

References

[ABS06] Marcelo Aguiar, Nantel Bergeron, and Frank Sottile, Combinatorial Hopf algebras and generalized Dehn-Sommerville relations, Compos. Math. 142 (2006), no. 1, 1-30. MR 2196760 (2006h:05233)

[AM10] Marcelo Aguiar and Swapneel Mahajan, Monoidal functors, species and Hopf algebras, CRM Monograph Series, vol. 29, American Mathematical Society, Providence, RI, 2010, With forewords by Kenneth Brown and Stephen Chase and Andre Joyal. MR 2724388 (2012g:18009)

[AM13] --, Hopf monoids in the category of species, Contemporary Mathematics 585 (2013), 17-124.

[AMW] Marcelo Aguiar, Swapneel Mahajan, and Jacob A. White, Rings and near-rings in higher monoidal categories, in preparation.

[BBL+99] Eric Babson, Anders Bjorner, Svante Linusson, John Shareshian, and Volkmar Welker, Complexes of not i-connected graphs, Topology 38 (1999), no. 2, 271-299. MR 1660341 (2000a:57001)

[Ber73] Claude Berge, Graphs and hypergraphs, North-Holland Publishing Co., Amsterdam, 1973, Translated from the French by Edward Minieka, North-Holland Mathematical Library, Vol. 6. MR 0357172 (50 #9640)

[BL46] G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355-451. MR 0018401 (8,284f)

[BLL98] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial species and tree-like structures, Encyclopedia of Mathematics and its Applications, vol. 67, Cambridge University Press, Cambridge, 1998, Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota. MR 1629341 (2000a:05008)

[CG95] F. R. K. Chung and R. L. Graham, On the cover polynomial of a digraph, J. Combin. Theory Ser. B 65 (1995), no. 2, 273-290. MR 1358990 (96j:05050)

[Die10] Reinhard Diestel, Graph theory, fourth ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811 (2011m:05002)

[GS01] David D. Gebhard and Bruce E. Sagan, A chromatic symmetric function in noncommuting variables, J. Algebraic Combin. 13 (2001), no. 3, 227-255. MR 1836903 (2002d:05124)

[HM12] Brandon Humpert and Jeremy L. Martin, The incidence Hopf algebra of graphs, SIAM J. Discrete Math. 26 (2012), no. 2, 555-570. MR 2967484

[Hum11] Brandon Humpert, A quasisymmetric function generalization of the chromatic symmetric function, Electron. J. Combin. 18 (2011), no. 1, Paper 31, 13. MR 2776807 (2012f:05143)

[Joy81] Andre Joyal, Une theorie combinatoire des series formelles, Adv. in Math. 42 (1981), no. 1, 1-82. MR 633783 (84d:05025)

[JR79] S. A. Joni and G.-C. Rota, Coalgebras and bialgebras in combinatorics, Stud. Appl. Math. 61 (1979), no. 2, 93-139. MR 544721 (81c:05002)

[Mon93] Susan Montgomery, Hopf algebras and their actions on rings, CBMS Regional Conference Series in Mathematics, vol. 82, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1993. MR 1243637 (94i:16019)

[Rot64] Gian-Carlo Rota, On the foundations of combinatorial theory. I. Theory of Mobius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340-368 (1964). MR 0174487 (30 #4688)

[RW74] Douglas C. Ravenel and W. Stephen Wilson, The Hopf ring for complex cobordism, Bull. Amer. Math. Soc. 80 (1974), 1185-1189. MR 0356030 (50 #8502)

[Sok05] Alan D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge Univ. Press, Cambridge, 2005, pp. 173-226. MR 2187739 (2006k:05052)

[Sta73] Richard P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973), 171-178. MR 0317988 (47 #6537)

[Sta95] --, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math. 111 (1995), no. 1, 166-194. MR 1317387 (96b:05174)

[Sta97] --, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cam bridge University Press, Cambridge, 1997, With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original. MR MR1442260 (98a:05001)

[Tut54] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canadian J. Math. 6 (1954), 80-91. MR 0061366 (15,814c)

[Whi32] Hassler Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), no. 8, 572-579. MR 1562461

Jacob A. White

Department of Mathematics, Texas A&M University, College Station, TX 77843, USA
COPYRIGHT 2014 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:White, Jacob A.
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2014
Words:6528
Previous Article:A new generation tree for permutations, preserving the number of fixed points.
Next Article:Combinatorics of diagrams of permutations.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters