THE TUTTE DICHROMATE AND WHITNEY HOMOLOGY OF MATROIDS

DAVID G. WAGNER

Abstract. We consider a specialization Y_{M}(q, t) of the Tutte polynomial of a matroid M which is inspired by analogy with the Potts model from statistical mechanics. The only information lost in this specialization is the number of loops of M. We show that the coefficients of Y_{M}(1 − p, t) are very simply related to the ranks of the Whitney homology groups of the opposite partial orders of the independent set complexes of the duals of the truncations of M. In particular, we obtain a new homological interpretation for the coefficients of the characteristic polynomial of a matroid.

0. Introduction.

In 1954, Tutte [30] introduced the dichromate of a (finite) graph, which has since become known as the Tutte polynomial. In the four decades since then this has provided a profound link between combinatorics and other branches of mathematics as diverse as statistical mechanics [3, 5, 17, 19, 20], low-dimensional topology [17, 18, 20], and the theory of Grothendieck rings [9, 10, 29]. Indeed, in 1947 Tutte [29] showed that the “Tutte-Grothendieck ring” K_{0}(𝔊) of a suitably defined category 𝔊 of graphs is ℤ[x, y]; the class T_{G}(x, y) in K_{0}(𝔊) of a graph G is its Tutte polynomial. This construction was axiomatized for “bidecomposition categories” and applied to a category 𝔐 of matroids by Brylawski [9, 10], with the result that K_{0}(𝔐) = ℤ[x, y] as well. (It is interesting to compare Brylawski’s axiomatization with the usual hypotheses of algebraic K-theory; see, e.g. Chapter 5 of Silvester [27].) Crapo’s generalization [14] of Tutte polynomials to matroids rests on this foundation. The fact that T_{M}(x, y) is the “universal Tutte-Grothendieck invariant” of the matroid M is just a restatement of the fact that it is the class of M in K_{0}(𝔐).

This categorical perspective overlooks the question of what combinatorial information about a matroid is encoded in its Tutte polynomial. Much of the inquiry into this subject has been motivated by this question, and various interpretations of coefficients or specializations of T_{M}(x, y) have been given; see [4, 7, 10, 11, 12, 14, 16, 25, 26, 30, 31, 34] and elsewhere. In this paper we consider a specialization Y_{M}(q, t) of T_{M}(x, y) inspired by analogy with the Potts model from statistical mechanics. This connection, first made explicit by Kasteleyn and Fortuin [19], is implicit in equation (10) of Tutte [31], the last equation on page 331 of Oxley and Welsh [25], and elsewhere in the literature. Although Y_{M}(q, t) is insensitive to the presence of loops, this is the only information lost in the specialization from T_{M}(x, y) to Y_{M}(q, t). Moreover, Y_{M}(q, t) presents a great deal of information about M in a very convenient form. For example, if M is the graphic matroid of a graph G = (V, E) with c connected components, then [q^{#E}]t^{c}Y_{M}(q, t) is the chromatic polynomial of G, and for each natural number i, [t^{i}]Y_{M}(1/2, t) is the probability that a random spanning edge-subgraph of G has exactly c + i connected components; Propositions 1.4 and 1.5 below give more general statements. (We use the notation [z^{a}]F (z) to denote the coefficient of z^{a} in the polynomial F (z).)

1991 Mathematics Subject Classification. 05B35, 06A08.

Key words and phrases. Tutte polynomial, dichromate, chromatic polynomial, reliability polynomial, percolation, Möbius function, Whitney homology.

Research performed while a General Member of MSRI during the 1996-1997 Program on Combinatorics, and supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392. Research at MSRI is supported in part by NSF grant DMS-9022140.

The main purpose of this paper is to explain the meaning of the coefficients of Y_{M}(1 − p, t); Section 1 is intended to put this result in context. These coefficients are simply related to the ranks of the Whitney homology groups of the opposite partial orders of the independent set complexes of the duals of the truncations of M; the precise statements appear in Section 3. The proof is in two parts: in Section 2 we give a numerical formula for the coeffients of Y_{M}(1 − p, t) involving Möbius functions of certain partial orders associated with M, and in Section 3 we use established results of topological combinatorics to interpret these numbers as ranks of certain homology groups. In particular, we obtain as a corollary a new homological interpretation for the coefficients of the characteristic polynomial of a matroid.

1. The Potts model and the Tutte dichromate.

We begin by considering general finite graphs G = (V, E), which may have both loops and multiple edges. The notations n(G), m(G), and c(G) denote the number of vertices, edges, and connected components of G, respectively. The lattice of set partitions of V is denoted by Π_{V}. For e ∈ E and π ∈ Π_{V}, denote by e ≺ π the relation that there exists a block B ∈ π such that both ends of e are in B; as usual, e ⊀ π denotes the negation of this relation. For π ∈ Π_{V}, let ⟨G : π⟩ := #{e ∈ E : e ⊀ π}. We define a polynomial Z_{G}(q, t) ∈ ℤ[q, t] by

Z_{G}(q, t) := ∑_{π∈Π_{V}} q^{⟨G:π⟩}t_{(#π)} (1.1)

in which t_{(k)} := t(t − 1) ⋯ (t − k + 1) is the k-th falling factorial polynomial. Clearly Z_{G}(q, t) depends only upon the isomorphism class of G. As an example, Figure 1 depicts a graph G and its associated polynomial Z_{G}(q, t). When t = N is a positive integer and q = e^{J/kT}, Z_{G}(e^{J/kT} , N) is (almost by definition) the partition function of

[figure: \begin{matrix}Z_{G} & 1 & q & q^{2} & q^{3} & q^{4} & q^{5} & q^{6} & q^{7} \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ t & 1 & 0 & −2 & −6 & 9 & 8 & −16 & 6 \\ t^{2} & 0 & 0 & 2 & 6 & −15 & −11 & 33 & −15 \\ t^{3} & 0 & 0 & 0 & 0 & 6 & 2 & −22 & 14 \\ t^{4} & 0 & 0 & 0 & 0 & 0 & 1 & 5 & −6 \\ t^{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

Figure 1. A graph G and its polynomial Z_{G}(q, t).

the N-state Potts model on G (T is temperature, k is the Boltzmann constant, and J is a material parameter); see [3, 5, 17, 19, 20] for references and more information.

The polynomial Z_{G}(q, t) can be calculated recursively as follows. For G = (V, E) and e ∈ E, let G ∖ e and G/e denote the graphs obtained from G by deletion of e and by contraction of e, respectively.

Proposition 1.1. Let G = (V, E) be a graph, and let e ∈ E. Then

Z_{G}(q, t) = qZ_{G∖e}(q, t) + (1 − q)Z_{G/e}(q, t).

If G consists of n vertices, any number of loops, and no nonloop edges, then Z_{G}(q, t) = t^{n}.

Proof. The partitions π ∈ Π_{V} such that e ≺ π are in a natural bijective correspondence with partitions in Π_{V (G/e)}. Thus we calculate that

Z_{G}(q, t) = q ∑_{e⊀π∈Π_{V}} q^{⟨G∖e:π⟩}t_{(#π)} + ∑_{e≺π∈Π_{V}} q^{⟨G:π⟩}t_{(#π)}
= qZ_{G∖e}(q, t) + (1 − q) ∑_{e≺π∈Π_{V}} q^{⟨G∖e:π⟩}t_{(#π)}
= qZ_{G∖e}(q, t) + (1 − q)Z_{G/e}(q, t).

The second assertion follows from (1.1) since t^{n} = ∑_{k} S(n, k)t_{(k)}, where S(n, k) denotes a Stirling number of the second kind.

Proposition 1.2. If G and H are vertex-disjoint graphs then

Z_{G∪H}(q, t) = Z_{G}(q, t)Z_{H}(q, t).

Proof. Use Proposition 1.1 and induction on the number of nonloop edges of G ∪ H.

Corollary 1.3. For any graph G, t^{c(G)} divides Z_{G}(q, t).

Proof. From (1.1) it follows that t divides Z_{C}(q, t) for each connected component C of G; the result follows from Proposition 1.2.

The polynomial Z_{G}(q, t) displays a great deal of information about G in a very convenient form, by considering the rows and columns of Figure 1 (for example) as univariate polynomials. For t ∈ ℕ, a t-colouring of G is any function f : V → {1, 2, ..., t}. An edge e ∈ E is proper with respect to f if e = {u, v} and f(u) ≠ f(v), so loops are never proper. Proposition 1.4 is equivalent to Theorem 3.2 of Brylawski [11]. (See also equations (10) and (12) of Tutte [31], and Theorem 6.3.26 of Brylawski and Oxley [12], in connection with Corollary 1.8 below.)

Proposition 1.4. Let G be a graph. For any k, t ∈ ℕ, [q^{k}]Z_{G}(q, t) is the number of t-colourings of G which have exactly k proper edges.

Proof. To each t-colouring f of G is associated the partition π_{f} ∈ Π_{V} defined as follows: v, w ∈ V are in the same block of π_{f} if and only if f(v) = f(w). For a given π ∈ Π_{V}, the number of t-colourings f such that π_{f} = π is t_{(#π)}. The result now follows directly from (1.1).

In particular, [q^{m(G)}]Y_{G}(q, t) is the chromatic polynomial of G [10, 11, 12, 18, 21, 26, 29, 30, 31, 35]. Given a graph G and 0 ≤ q ≤ 1, let 𝒢(q) denote a random spanning subgraph of G obtained by deleting each edge independently with probability q. Proposition 1.5 (in conjunction with Corollary 1.8) is implicit in the last equation on page 331 of Oxley and Welsh [25] (and is derived and interpreted there more generally for matroids).

Proposition 1.5. Let G be a graph. For any 0 ≤ q ≤ 1 and k ∈ ℕ, [t^{k}]Z_{G}(q, t) is the probability that 𝒢(q) has exactly k connected components.

Proof. Fix any k ∈ ℕ and 0 ≤ q ≤ 1. We proceed by induction on the number of nonloop edges of G. The basis of induction follows from the second assertion of Proposition 1.1. For the induction step, let e ∈ E be a nonloop, and denote by rel_{k}^{G}(q) the probability that 𝒢(q) has exactly k connected components. By conditioning on the state of e (deleted or included) we obtain

(1.2) rel_{k}^{G}(q) = q rel_{k}^{G∖e}(q) + (1 − q)rel_{k}^{G/e}(q).

Comparison of Proposition 1.1 and (1.2) completes the induction step.

In particular, [t^{1}]Z_{G}(q, t) is the reliability polynomial of G, also studied under the title of percolation on graphs; see [2, 12, 13, 25, 32, 34].

For background information on matroids the reader should consult Oxley [24] or Welsh [33]. We view a matroid M = (E, ρ) as a ground-set E with a rank function ρ : 2^{E} → ℕ satisfying certain axioms; the corank function σ : 2^{E} → ℕ is defined by σ(S) := #S − ρ(S). The rank of M is ρ(E), and will also be denoted by d(M). The simplicial complex of independent sets of M is ℐ(M) := {S ⊆ E : σ(S) = 0}. To each graph G = (V, E) is associated its graphic (or polygon, or cycle) matroid M(G), which has ground-set E and rank function ρ(S) := n(G) − c((V, S)); in this case ℐ(M) consists of all edge-sets of spanning forests of G. For a matroid M = (E, ρ) and e ∈ E we denote by M ∖ e and M/e the matroids obtained from M by deletion of e and by contraction of e, respectively. For S ⊆ E and e ∈ S, let S/e denote S ∖ e regarded as a subset of E(M/e). We regard S ∖ e either as a subset of E(M) or of E(M ∖ e), as required. The elements of E are of three types, called loops, coloops, and links, and the following relations on ranks and coranks hold.

type of e ρ(E ∖ e) σ(E ∖ e) ρ(E/e) σ(E/e)
loop ρ(E) σ(E) − 1 ρ(E) σ(E) − 1
coloop ρ(E) − 1 σ(E)  ρ(E) − 1 σ(E)
link ρ(E)  σ(E) − 1 ρ(E) − 1 σ(E)

(1.3)

The Tutte polynomial of M = (E, ρ), as defined by Crapo [14], is

T_{M}(x, y) := ∑_{S⊆E}(x − 1)^{ρ(E)−ρ(S)}(y − 1)^{σ(S)}. (1.4)

Proposition 1.1 shows that for any finite graph G, Z_{G}(q, t) = f(G; t, 1 − q, q) in which f(G; t, x, y) is a polynomial invariant of graphs defined by Negami [21]. Oxley

[23] shows that t^{−c(G)}f(G; t, x, y) is determined by the Tutte polynomial of M(G). This suffices to establish Corollary 1.8 below, but for completeness we sketch another proof.

For a minor-closed class ℭ of matroids, a Tutte-Grothendieck invariant on ℭ is an assignment M ↦ Ψ_{M} which associates to each matroid M in ℭ an element Ψ_{M} of some fixed commutative ring R (which depends only on Ψ), and satisfies the following properties: (α) If M ≃ N then Ψ_{M} = Ψ_{N}. (β) If e ∈ E(M) is a link then Ψ_{M} = Ψ_{M∖e} + Ψ_{M/e}. (γ) If M and N have disjoint ground-sets then Ψ_{M⊕N} = Ψ_{M}Ψ_{N}. For a graph G, let r(G) := n(G) − c(G) and let s(G) := m(G) − n(G) + c(G). Define a rational function Z̃_{G}(q, t) ∈ ℤ(q, t) by

Z̃_{G}(q, t) := \frac{Z_{G}(q, t)}{t^{c(G)}(1 − q)^{r(G)}q^{s(G)}} . (1.5)

Proposition 1.6. The assignment M(G) ↦ Z̃_{G}(q, t) is a (well-defined) Tutte-Grothendieck invariant on the class of graphic matroids.

Sketch of proof. Well-definedness is the main issue. Whitney [36] (see also Theorem 6.3.1 of [22]) proves that two graphs G and H are such that M(G) ≃ M(H) if and only if G and H are “2-isomorphic” (see the above references for the definition). If H is obtained from G by splitting at a cut-vertex or by twisting at a 2-vertex-cut then Proposition 1.1 and induction on m(G) can be used to show that Z_{G}(q, t) = Z_{H}(q, t). This suffices to show that if G and H are 2-isomorphic then Z_{G}(q, t) = Z_{H}(q, t), and it follows that M(G) ↦ Z̃_{G}(q, t) is well-defined. Property (α) is a consequence of well-definedness, (β) follows from Proposition 1.1, and (γ) follows from Proposition 1.2.

As mentioned in the introduction, T_{M}(x, y) is the universal Tutte-Grothendieck invariant (on the class of all matroids) in the following sense. Let L denote a oneelement matroid of rank zero, and let L^{∗} denote a one-element matroid of rank one; notice that T_{L^{∗}}(x, y) = x and T_{L}(x, y) = y. Proposition 1.7 is developed further in [10, 12, 25, 37].

Proposition 1.7. If ℭ is a minor-closed class of matroids and M ↦ Ψ_{M} is a Tutte-Grothendieck invariant on ℭ, then for all M in ℭ, Ψ_{M} = T_{M}(Ψ_{L^{∗}}, Ψ_{L}).

Sketch of proof. It follows from (α), (β), and (γ), by induction on #E(M), that the assignment M ↦ Ψ_{M} is determined by its values Ψ_{L^{∗}} and Ψ_{L}. Since x and y are independent indeterminates it follows that Ψ_{M} = T_{M}(Ψ_{L^{∗}}, Ψ_{L}) once it has been shown that M ↦ T_{M}(x, y) is itself a Tutte-Grothendieck invariant on 𝔐. Verification of this fact follows from the definition (1.4) as in Lemma 6.2.1 of [12], for example.

See [19, 25, 31] for more information related to Corollary 1.8.

Corollary 1.8. Let G be a graph, with graphic matroid M. Then

Z_{G}(q, t) = t^{c(G)}(1 − q)^{r(G)}q^{s(G)} T_{M}(\frac{qt + 1 − q}{1 − q} , \frac{1}{q}) .

Proof. One checks that Z̃_{L^{∗}}(q, t) = (qt + 1 − q)/(1 − q) and Z̃_{L} = 1/q, and the result follows from Propositions 1.6 and 1.7.

Corollary 1.8 allows us to generalize from the class of graphic matroids to the class of all matroids. However, c(G) can not be determined from M(G) alone, and so we define polynomials

Y_{G}(q, t) := t^{−c(G)}Z_{G}(q, t) (1.6)

for every graph G, and

Y_{M}(q, t) := (1 − q)^{ρ(E)}q^{σ(E)} T_{M}(\frac{qt + 1 − q}{1 − q} , \frac{1}{q}) (1.7)

for every matroid M = (E, ρ). Corollary 1.8 shows that these definitions agree for graphic matroids. From (α), (β), and (γ) we have the following. (α′) If M ≃ N then Y_{M}(q, t) = Y_{N}(q, t). (β′) If e ∈ E(M) is a link then Y_{M}(q, t) = qY_{M∖e}(q, t) + (1 − q)Y_{M/e}(q, t). (γ′) If M and N have disjoint ground-sets then Y_{M⊕N}(q, t) = Y_{M}(q, t)Y_{N}(q, t). If e is a loop of M then M ≃ (M ∖ e) ⊕ L; from (α), (β), and (1.7) we deduce that (β′′) If e ∈ E(M) is a loop then Y_{M}(q, t) = Y_{M∖e}(q, t). If e is a coloop of M then M ≃ (M/e) ⊕ L^{∗}; from (α), (β), and (1.7) we deduce that (β^{∗}) If e ∈ E(M) is a coloop then Y_{M}(q, t) = (qt + 1 − q)Y_{M/e}(q, t).

\begin{matrix}Y_{M} & 1 & p & p^{2} & p^{3} & p^{4} & p^{5} & p^{6} & p^{7} \\ 1 & 0 & 0 & 0 & 0 & 19 & −38 & 26 & −6 \\ t & 0 & 0 & 0 & 29 & −100 & 128 & −72 & 15 \\ t^{2} & 0 & 0 & 20 & −94 & 176 & −164 & 76 & −14 \\ t^{3} & 0 & 7 & −41 & 100 & −130 & 95 & −37 & 6 \\ t^{4} & 1 & −7 & 21 & −35 & 35 & −21 & 7 & −1 \end{matrix}

Figure 2. The polynomial Y_{M}(1 − p, t) for M(G) from Figure 1.

\begin{matrix}Ŷ_{M} & 1 & p & p^{2} & p^{3} & p^{4} & p^{5} & p^{6} & p^{7} \\ 1 & 0 & 0 & 0 & 0 & 19 & 38 & 26 & 6 \\ t & 0 & 0 & 0 & 29 & 81 & 90 & 46 & 9 \\ t^{2} & 0 & 0 & 20 & 65 & 95 & 74 & 30 & 5 \\ t^{3} & 0 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \end{matrix}

Figure 3. The polynomial Ŷ_{M}(p, t) for M(G) from Figure 1.

Let U_{m}^{0} be a matroid of rank zero on m elements; then T_{U_{m}^{0}}(x, y) = y^{m}, but Y_{U_{m}^{0}}(q, t) = 1 is independent of m. Generally, Y_{M}(q, t) is insensitive to the presence of loops, but this is the only information lost in specializing from T_{M}(x, y) to Y_{M}(q, t). To see this, invert (1.7) to yield

T_{M}(x, y) = \frac{y^{#E}}{(y − 1)^{ρ(E)}} Y_{M}(\frac{1}{y}, (x − 1)(y − 1)) . (1.8)

The degree of Y_{M}(q, t) in the variable t is ρ(E), and the degree of Y_{M}(q, t) in the variable q is the number of nonloop elements of M. Thus, given Y_{M}(q, t) and the number of loops of M, T_{M}(x, y) can be recovered.

2. The coefficients of Y_{M}(1 − p, t).

We now make the substitution p := 1−q and interpret the coefficients of Y_{M}(1−p, t) combinatorially. Figure 2 shows this form of the polynomial for the graph from Figure 1. One notices in this example a simple sign-alternation pattern, and the fact that evaluation at t = 1 yields Y_{M}(1−p, 1) = 1. This suggests examination of the rational function Ŷ_{M}(p, t) ∈ ℤ(p, t) defined by

Ŷ_{M}(p, t) := \frac{(−1)^{d(M)}Y_{M}(1 + p, −t) − t^{d(M)}}{1 + t} . (2.1)

Figure 3 shows Ŷ_{M}(p, t) for the example from Figures 1 and 2. For e ∈ E(M), define b(M, e) := ρ(E) − ρ(E ∖ e), so b(M, e) = 1 if e is a coloop of M and b(M, e) = 0 otherwise.

Lemma 2.1. Let M = (E, ρ) be a matroid and let e ∈ E be a link or a coloop. Then

Ŷ_{M}(p, t) = pt^{d(M)−1} + (1 + p)t^{b(M,e)}Ŷ_{M∖e}(p, t) + pŶ_{M/e}(p, t).

Consequently, for every matroid M, Ŷ_{M}(p, t) ∈ ℕ[p, t].

Proof. Let b := b(M, e) and d := d(M). From (β′) and (β^{∗}) and the fact that if e ∈ E is a coloop then M ∖ e ≃ M/e we see that

Y_{M}(q, t) = qt^{b}Y_{M∖e}(q, t) + (1 − q)Y_{M/e}(q, t).

Therefore,

Ŷ_{M}(p, t) = \frac{(−1)^{d}(1 + p)(−t)^{b}Y_{M∖e}(1 + p, −t)}{1 + t}

+\frac{(−1)^{d}(−p)Y_{M/e}(1 + p, −t) − t^{d}}{1 + t}

= (1 + p)t^{b}Ŷ_{M∖e}(p, t) + pŶ_{M/e}(p, t) + pt^{d−1},

as claimed. The second claim follows by induction on the number of nonloop elements of E; for the basis of induction d = 0 and Y_{M}(q, t) = 1, so that Ŷ_{M}(p, t) = 0.

Let M = (E, ρ) be a matroid of rank d ≥ 1. For each 0 ≤ i ≤ d − 1 let 𝒮_{i}^{M} be the set of all S ⊆ E such that ρ(S) ≥ d − i. Notice that 𝒮_{0}^{M} ⊂ 𝒮_{1}^{M} ⊂ ⋯ ⊂ 𝒮_{d−1}^{M}, and that if S ⊆ T ⊆ E and S ∈ 𝒮_{i}^{M} then T ∈ 𝒮_{i}^{M}. For example, if M = M(G) for a graph G then d = n(G) − c(G) and for 0 ≤ i ≤ d − 1, 𝒮_{i}^{M} consists of the edge-sets of all spanning subgraphs of G which have at most c(G) + i components. Order 𝒮_{i}^{M} partially by inclusion, and adjoin a new unique minimal element ˆ0 to 𝒮_{i}^{M} to obtain ℒ_{i}^{M} := {ˆ0} ⊕ 𝒮_{i}^{M}, which is in fact a graded lattice. The height of S ∈ 𝒮_{i}^{M} in ℒ_{i}^{M} is #S − d + 1 + i. Let μ_{i}^{M}(·, ·) denote the Möbius function of ℒ_{i}^{M} (see Rota [26]); we recall that μ_{i}^{M}(ˆ0, ˆ0) = 1 and that for S ∈ 𝒮_{i}^{M},

μ_{i}^{M}(ˆ0, S) = − ∑_{ˆ0≤T <S} μ_{i}^{M}(ˆ0, T). (2.2)

If S ⊆ E but S ∉ 𝒮_{i}^{M} then by convention we put μ_{i}^{M}(ˆ0, S) := 0. Throughout this paper the first argument of a Möbius function is always ˆ0, and we shall henceforth omit it from the notation, writing only μ_{i}^{M}(S).

Lemma 2.2. Let M = (E, ρ) be a matroid of rank d ≥ 1 and let e ∈ E. Then for all 0 ≤ i ≤ d − 1 and all S ∈ 𝒮_{i}^{M} with e ∈ S:

(a) if e is a loop then μ_{i}^{M}(S) = 0; (b) if e is a coloop then μ_{i}^{M}(S) = −μ_{i−1}^{M∖e}(S ∖ e) + μ_{i}^{M/e}(S/e);

(c) if e is a link then μ_{i}^{M}(S) = −μ_{i}^{M∖e}(S ∖ e) + μ_{i}^{M/e}(S/e).

Proof. We prove the claims by induction on #S. For the basis of induction notice that if S ∈ 𝒮_{i}^{M} then S contains an independent set of rank d − i, and so #S ≥ d − i. If e is a loop then this bound can not be attained, and the basis of induction is that S ∖ e ∈ ℐ(M) has rank d − i. Thus, the interval from ˆ0 to S in ℒ_{i}^{M} consists of the three elements {ˆ0 < S ∖ e < S}, and so μ_{i}^{M}(S) = 0, as required. If e is a coloop and S ∈ ℐ(M) has rank d − i then S ∖ e ∈ ℐ(M ∖ e) has rank (d − 1) − (i − 1) − 1, so S ∖ e ∉ 𝒮_{i−1}^{M∖e}, so μ_{i−1}^{M∖e}(S ∖ e) = 0. If e is a link and S ∈ ℐ(M) has rank d − i then S ∖ e ∈ ℐ(M ∖ e) has rank d − i − 1, so S ∖ e ∉ 𝒮_{i}^{M∖e}, so μ_{i}^{M∖e}(S ∖ e) = 0. In both these cases, S and S/e cover ˆ0 in ℒ_{i}^{M} and ℒ_{i}^{M/e}, respectively, so that μ_{i}^{M}(S) = μ_{i}^{M/e}(S/e) = −1, as required. This completes the basis of induction.

For the induction step apply (2.2) and separate the case e ∉ T from the case e ∈ T to obtain

μ_{i}^{M}(S) = − ∑_{T ≤S∖e}μ_{i}^{M}(T) − ∑_{e∈T <S} μ_{i}^{M}(T). (2.3)

The first sum on the right side of (2.3) is zero, since it is the sum of μ_{i}^{M}(T) over the interval [ˆ0, S ∖ e] of ℒ_{i}^{M}. We may apply the induction hypothesis to each term in the second sum. If e is a loop then each term of this sum is zero, proving part (a). If e is a coloop or a link then let b := b(M, e). By induction and (2.3) we have

μ_{i}^{M}(S) = − ∑_{e∈T <S} (−μ_{i−b}^{M∖e}(T ∖ e) + μ_{i}^{M/e}(T/e))
= ∑_{Q} μ_{i−b}^{M∖e}(Q) − ∑_{U} μ_{i}^{M/e}(U),

in which Q ranges over subsets of E ∖ e such that Q ∪ {e} ∈ ℒ_{i}^{M} and Q < S ∖ e, and U ranges over subsets of E/e such that U ∪ {e} ∈ ℒ_{i}^{M} and U < S/e. If i = d − 1 then Q = ∅ and U = ∅ arise, and can be identified with the terms for ˆ0 in ℒ_{i−b}^{M∖e} and in ℒ_{i}^{M/e}, respectively. If i ≤ d − 2 then these terms do not arise, but since μ_{i−b}^{M∖e}(ˆ0) − μ_{i}^{M/e}(ˆ0) = 0 we may include them without changing the sum. We obtain

μ_{i}^{M}(S) = ∑_{ˆ0≤Q<S∖e}μ_{i−b}^{M∖e}(Q) − ∑_{ˆ0≤U<S/e} μ_{i}^{M/e}(U)

= −μ_{i−b}^{M∖e}(S ∖ e) + μ_{i}^{M/e}(S/e),

by (2.2). This completes the induction step, and the proof.

Corollary 2.3. Let M = (E, ρ) be a matroid of rank d ≥ 1, let 0 ≤ i ≤ d − 1, and let S ∈ 𝒮_{i}^{M}. Then (−1)^{#S−d+1+i}μ_{i}^{M}(S) ≥ 0. Moreover, if S contains no loops of M then (−1)^{#S−d+1+i}μ_{i}^{M}(S) > 0.

Proof. Both claims follows from Lemma 2.2 by induction on #S.

Let M = (E, ρ) be a matroid of rank d ≥ 1, with #E = m and with ℓ loops. For 0 ≤ i ≤ d − 1 define polynomials W_{i}^{M}(p) ∈ ℤ[p] by

W_{i}^{M}(p) := ∑_{S∈𝒮_{i}^{M}} μ_{i}^{M}(S)(−p)^{#S−d+1+i}. (2.4)

The coefficients ω_{j}^{i,M} defined by W_{i}^{M}(p) = ∑_{j=1}^{m−d+1+i} ω_{j}^{i,M}p^{j} are the proper unsigned Whitney numbers of the first kind of ℒ_{i}^{M}; that is,

ω_{j}^{i,M} := (−1)^{j} ∑_{S∈𝒮_{i}^{M}: #S−d+1+i=j} μ_{i}^{M}(S) (2.5)

for each 0 ≤ i ≤ d − 1 and 1 ≤ j ≤ m − d + 1 + i. By convention we put ω_{j}^{i,M} := 0 in all remaining cases, and from Corollary 2.3 it follows that ω_{j}^{i,M} ≥ 0 for all i and j. By Lemma 2.2, μ_{i}^{M}(S) = 0 for all 0 ≤ i ≤ d − 1 whenever S ⊆ E contains a loop of M. From this, Corollary 2.3, and (2.4), it follows that deg W_{i}^{M}(p) = m − ℓ − d + 1 + i for all 0 ≤ i ≤ d − 1.

Lemma 2.4. Let M = (E, ρ) be a matroid of rank d ≥ 1 with #E = m and with ℓ loops. Then W_{d−1}^{M}(p) = (1 + p)^{m−ℓ} − 1.

Proof. By (2.4) and Lemma 2.2 we have

W_{d−1}^{M}(p) = ∑_{S∈𝒯}μ_{d−1}^{M}(S)(−p)^{#S},

in which 𝒯 is the set of all S ∈ 𝒮_{d−1}^{M} which do not contain any loops of M. One checks that 𝒯 is a downward-closed subset of 𝒮_{d−1}^{M} and is the set of all nonempty subsets of the set of nonloop elements of M. Thus {ˆ0} ⊕ 𝒯 is a Boolean lattice with m − ℓ atoms, and the result follows since μ_{d−1}^{M}(S) = (−1)^{#S} for all S ∈ 𝒯.

Lemma 2.5. Let M = (E, ρ) be a matroid of rank d ≥ 2, and let 0 ≤ i ≤ d − 2. If e ∈ E is a link or a coloop then

W_{i}^{M}(p) = (1 + p)W_{i−b(M,e)}^{M∖e}(p) + W_{i}^{M/e}(p).

Proof. Let b := b(M, e). Notice that {S ∈ 𝒮_{i}^{M} : e ∉ S} = {S ⊆ E(M ∖ e) : ρ(S) ≥ (d − b) − (i − b)} = 𝒮_{i−b}^{M∖e}. Also, for all S in this set μ_{i}^{M}(S) = μ_{i−b}^{M∖e}(S) since the intervals [ˆ0, S] in ℒ_{i}^{M} and in ℒ_{i−b}^{M∖e} are isomorphic. Since i ≤ d − 2 the singleton {e} is not an element of 𝒮_{i}^{M}. Hence, {S ∖ e : e ∈ S ∈ 𝒮_{i}^{M}} = {Q ⊆ E(M ∖ e) : ρ(Q) ≥ (d − b) − (i − b + 1)} = 𝒮_{i−b+1}^{M∖e} ⊃ 𝒮_{i−b}^{M∖e}. Also, μ_{i−b}^{M∖e}(Q) = 0 if Q ∈ 𝒮_{i−b+1}^{M∖e} ∖ 𝒮_{i−b}^{M∖e}. Finally, {S/e : e ∈ S ∈ 𝒮_{i}^{M}} = {U ⊆ E(M/e) : ρ(U) ≥ (d − 1) − i} = 𝒮_{i}^{M/e}. Thus, substituting Lemma 2.2 into (2.4) we obtain

W_{i}^{M}(p) = ∑_{e∉S∈𝒮_{i}^{M}} μ_{i}^{M}(S)(−p)^{#S−d+1+i}

+ ∑_{e∈S∈𝒮_{i}^{M}} (−μ_{i−b}^{M∖e}(S ∖ e) + μ_{i}^{M/e}(S/e)) (−p)^{#S−d+1+i}

= ∑_{S∈𝒮_{i−b}^{M∖e}} μ_{i−b}^{M∖e}(S)(−p)^{#S−(d−b)+1+(i−b)}

− ∑_{Q∈𝒮_{i−b+1}^{M∖e}} μ_{i−b}^{M∖e}(Q)(−p)^{(#Q+1)−(d−b)+1+(i−b)}

+ ∑_{U∈𝒮_{i}^{M/e}} μ_{i}^{M/e}(U)(−p)^{#U−(d−1)+1+i}

= W_{i−b}^{M∖e}(p) + pW_{i−b}^{M∖e}(p) + W_{i}^{M/e}(p),

as required.

Theorem 2.6. Let M = (E, ρ) be a matroid of rank d ≥ 0. Then

Ŷ_{M}(p, t) = ∑_{i=0}^{d−1} W_{i}^{M}(p)p^{d−1−i}t^{i}.

Proof. We prove, by induction on the number of nonloops of M, that for all 0 ≤ i ≤ d−1, [t^{i}]Ŷ_{M}(p, t) = W_{i}^{M}(p)p^{d−1−i}. If M has no nonloops then d(M) = 0, Ŷ_{M}(p, t) = 0, and the summation on the right side is empty; this establishes the basis of induction. For the induction step let e be a coloop or link of M, let b := b(M, e), and let M have ℓ loops and #E(M) = m. The induction hypothesis is that [t^{i}]Ŷ_{M∖e}(p, t) = W_{i}^{M∖e}(p)p^{(d−b)−1−i} for all 0 ≤ i ≤ d−b−1 and that [t^{i}]Ŷ_{M/e}(p, t) = W_{i}^{M/e}(p)p^{(d−1)−1−i} for all 0 ≤ i ≤ d − 2. For the case i = d − 1 Lemmas 2.1, 2.4, and the induction hypothesis imply that

[t^{d−1}]Ŷ_{M}(p, t) = p + (1 + p)[t^{(d−b)−1}]Ŷ_{M∖e}(p, t) + p[t^{d−1}]Ŷ_{M/e}(p, t)
= p + (1 + p) ((1 + p)^{m−1−ℓ} − 1) + p · 0
= (1 + p)^{m−ℓ} − 1 = W_{d−1}^{M}(p)p^{d−1−(d−1)},

as required. For the case 0 ≤ i ≤ d−2 Lemmas 2.1, 2.5, and the induction hypothesis imply that

[t^{i}]Ŷ_{M}(p, t) = (1 + p)[t^{i−b}]Ŷ_{M∖e}(p, t) + p[t^{i}]Ŷ_{M/e}(p, t)
= (1 + p)W_{i−b}^{M∖e}(p)p^{(d−b)−1−(i−b)} + pW_{i}^{M/e}(p)p^{d−2−i}
= ((1 + p)W_{i−b}^{M∖e}(p) + W_{i}^{M/e}(p)) p^{d−1−i}
= W_{i}^{M}(p)p^{d−1−i},

completing the induction step, and the proof.

Inverting (2.1), we see that

Y_{M}(1 − p, t) = t^{d(M)} + (1 − t)(−1)^{d(M)}Ŷ_{M}(−p, −t). (2.6)

Corollary 2.7 is an immediate consequence of Theorem 2.6 and (2.6).

Corollary 2.7. Let M = (E, ρ) be a matroid of rank d ≥ 1 with #E = m and with ℓ loops. For all 0 ≤ i ≤ d and 0 ≤ k ≤ m − ℓ,

[p^{k}t^{i}]Y_{M}(1 − p, t) = δ_{k0}δ_{id} + (−1)^{k+i−d} (ω_{k+i−d+1}^{i,M} + ω_{k+i−d}^{i−1,M}) ,

in which δ_{xy} is the Kronecker delta function, and [p^{k}t^{i}]Y_{M}(1 − p, t) = 0 for all other values of k and i.

Corollary 2.8. Let M = (E, ρ) be a matroid of rank d ≥ 1. For 0 ≤ k ≤ d, the number of k-element sets in ℐ(M) is [p^{k}t^{d−k}]Y_{M}(1 − p, t).

Proof. For each 1 ≤ i ≤ d − 1, the minimal elements of 𝒮_{i}^{M} are the sets S ∈ ℐ(M) such that #S = d − i. Since each such set has μ_{i}^{M}(S) = −1, (2.5) shows that the number of (d−i)-element sets in ℐ(M) is ω_{1}^{i,M} for each 1 ≤ i ≤ d−1. From Corollary 2.7 we obtain

[p^{k}t^{d−k}]Y_{M}(1 − p, t) = δ_{k0} + ω_{1}^{d−k,M} + ω_{0}^{d−k−1,M}

for all 0 ≤ k ≤ d, and the result follows.

For a matroid M, let 𝒦(M) denote the geometric lattice of closed sets (or “flats”) of M. The characteristic polynomial of M is

χ_{M}(t) := ∑_{S∈𝒦(M)} μ_{𝒦} (S)t^{d(M)−ρ(S)}.

See Rota [26] for more information. In particular, χ_{L}(t) = 1 and χ_{L^{∗}}(t) = t − 1, if e ∈ E(M) is a link then χ_{M}(t) = χ_{M∖e}(t) − χ_{M/e}(t), and if M and N have disjoint ground-sets then χ_{M⊕N}(t) = χ_{M}(t)χ_{N}(t). From this it follows by induction on m := #E(M) that if M has ℓ loops and rank d, then

χ_{M}(t) = [q^{m−ℓ}]Y_{M}(q, t) = (−1)^{m−ℓ+d}[p^{m−ℓ}]Y_{M}(1 − p, t).

Corollary 2.9 follows directly from (2.6).

Corollary 2.9. Let M = (E, ρ) be a matroid of rank d ≥ 1 with #E = m and with no loops. The characteristic polynomial of M is

χ_{M}(t) = (−1)^{d}(1 − t) ∑_{i=0}^{d−1} ω_{m−d+1+i}^{i,M}(−t)^{i}.

3. Whitney homology of upside-down matroids.

For this section we assume familiarity with the basic concepts of algebraic topology applied to combinatorics, as surveyed by Björner [8]. The order complex of a bounded partial order P with ˆ0 ≠ ˆ1 is the set Δ(P) of all totally-ordered subsets of P ∖{ˆ0, ˆ1}, partially ordered by inclusion; Δ(P) is an abstract simplicial complex. The (integral reduced simplicial) homology groups of a g-dimensional simplicial complex Δ with coefficients in ℤ are denoted by H̃_{∗}(Δ; ℤ) = ⨁_{j=−1}^{g} H̃_{j}(Δ; ℤ). The Betti numbers of Δ are β_{j}(Δ) := rank H̃_{j}(Δ; ℤ) for −1 ≤ j ≤ g. (For Δ ≠ ∅, β_{−1}(Δ) = 0; also β_{−1}(∅) = 1 and β_{j}(∅) = 0 for j > 0.) Philip Hall’s Theorem and the Euler-Poincaré Formula relate the Möbius funtion of P to the (reduced) Euler characteristic of Δ(P):

μ_{P} (ˆ1) = χ̃(Δ(P)) = −β_{−1} + β_{0} − β_{1} + ⋯ + (−1)^{g}β_{g}.

For a partial order P with ˆ0 the Whitney homology WH_{∗}(P; ℤ) of P was defined by Baclawski [1]. Theorem 5.1 of Björner [6] shows that WH_{∗}(P; ℤ) = ⨁_{j=0}^{g} WH_{j}(P; ℤ) in which

WH_{j}(P; ℤ) = ⨁_{ˆ0<σ∈P} H̃_{j−1}(Δ([ˆ0, σ]); ℤ)

for each 0 ≤ j ≤ g.

Interest in Whitney homology of geometric lattices arose as it provides an interpretation for the coefficients of the characteristic polynomial of a matroid; see [1, 6, 7]. Also, Theorem 9 of Stanley [28] implicitly uses Whitney homology of the opposite partial order of a geometric lattice to describe the Betti numbers of the minimal free resolution of the face-ring of a matroid; see also Eagon and Reiner [15]. Here we interpret the coefficients of Ŷ_{M}(p, t) as the ranks of the Whitney homology groups of the lattices ℒ_{i}^{M}, which are in general atomic but not semimodular.

Given a matroid M = (E, ρ) of rank d ≥ 1, an index 0 ≤ i ≤ d − 1, and a set S ∈ 𝒮_{i}^{M}, let Γ_{i}(S) := {S ∖ T : T ∈ 𝒮_{i}^{M} and T ⊆ S}; this simplicial complex depends only upon i and the restriction submatroid M|_{S} := M ∖ (E ∖ S) of M. In fact, denoting by N_{i} the matroid dual to the i-th truncation of M, we have Γ_{i}(S) = ℐ(N_{i}/(E ∖ S)). On the other hand, the interval [ˆ0, S] in ℒ_{i}^{M} is isomorphic to the partial order opposite to Γ_{i}(S) ⊕ {ˆ1}, and hence Δ([ˆ0, S]_{ℒ_{i}^{M}} ) is the barycentric subdivision of Γ_{i}(S). This gives us enough information to understand the Whitney homology of the lattices ℒ_{i}^{M} for 0 ≤ i ≤ d − 1.

Theorem 3.1. Let M = (E, ρ) be a matroid of rank d ≥ 1 with #E = m and with no loops. For all 0 ≤ i ≤ d − 1 and 1 ≤ j ≤ m − d + 1 + i,

[p^{d−1−i+j}t^{i}]Ŷ_{M}(p, t) = ω_{j}^{i,M} = rank WH_{j−1}(ℒ_{i}^{M}; ℤ).

Proof. For each 0 ≤ i ≤ d − 1 let N_{i} be the matroid dual to the i-th truncation of M, as above. For each S ∈ 𝒮_{i}^{M}, N_{i}/(E ∖ S) is a matroid, and so Γ_{i}(S) = ℐ(N_{i}/(E ∖ S) is a shellable simplicial complex (Theorem 7.3.3 of [7]). Hence, only the highestdimensional homology group of Γ_{i}(S) may be nonzero, and it is torsion-free (Theorem 7.8.1 of [7]); this highest dimension is #S − d + i − 1. Since Δ([ˆ0, S]_{ℒ_{i}^{M}} ) is the barycentric subdivision of Γ_{i}(S) we have

H̃_{∗}(Δ([ˆ0, S]_{ℒ_{i}^{M}} ); ℤ) = H̃_{∗}(Γ_{i}(S); ℤ).

It follows that

μ_{i}^{M}(S) = χ̃(Δ([ˆ0, S]_{ℒ_{i}^{M}} )) = (−1)^{#S−d+i−1}rank H̃_{#S−d+i−1}(Δ([ˆ0, S]_{ℒ_{i}^{M}} ); ℤ).

Therefore, for each 1 ≤ j ≤ m − d + 1 + i,

[p^{d−1−i+j}t^{i}]Ŷ_{M}(p, t) = ω_{j}^{i,M} = (−1)^{j} ∑_{S∈𝒮_{i}^{M}: #S−d+1+i=j} μ_{i}^{M}(S)

= ∑_{S∈𝒮_{i}^{M}: #S−d+1+i=j} rank H̃_{j−2}(Δ([ˆ0, S]_{ℒ_{i}^{M}} ); ℤ)

= rank ⨁_{S∈𝒮_{i}^{M}} H̃_{j−2}(Δ([ˆ0, S]_{ℒ_{i}^{M}} ); ℤ)
= rank WH_{j−1}(ℒ_{i}^{M}; ℤ),

completing the proof.

Corollary 3.2. Let M = (E, ρ) be a matroid of rank d ≥ 1 with #E = m and with no loops. For each 0 ≤ i ≤ d − 1 let N_{i} be the matroid dual to the i-th truncation of M. The characteristic polynomial of M is

χ_{M}(t) = (−1)^{d}(1 − t) ∑_{i=0}^{d−1} rank H̃_{m−d+i−1}(ℐ(N_{i}); ℤ)(−t)^{i}.

Proof. In view of Corollary 2.9 and Theorem 3.1, it suffices to notice that for 0 ≤ i ≤ d − 1, WH_{m−d+i}(ℒ_{i}^{M}; ℤ) = H̃_{m−d+i−1}(Γ_{i}(E); ℤ) (since E is the only set S ∈ 𝒮_{i}^{M} with #S − d + 1 + i = m − d + 1 + i) and that Γ_{i}(E) = ℐ(N_{i}).

References

[1] K. Baclawski, Whitney numbers of geometric lattices, Advances in Math. 16 (1975), 125-138.

[2] M.O. Ball and J.S. Provan, Bounds on the reliability for shellable independence systems, S.I.A.M. J. Alg. Discrete Meth. 3 (1982), 166-181.

[3] R.J. Baxter, Exactly Solved Models in Statistical Mechanics, Academic Press, New York, 1982.

[4] G. Berman, The dichromate and orientations of a graph, Canad. J. Math. 29 (1977), 947-956.

[5] N. Biggs, Interaction Models, London Math. Soc. Lecture Notes Ser. 30, Cambridge Univ. Press, London and New York, 1977.

[6] A. Björner, On the homology of geometric lattices, Algebra Universalis 14 (1982), 107-128.

[7] A. Björner, Homology and shellability of matroids and geometric lattices, in: Matroid Applications, (N. White, ed.), Cambridge Univ. Press, Cambridge, 1992.

[8] A. Björner, Topological methods, in: Handbook of Combinatorics (R.L. Graham, M. Grötschel, L. Lovász, eds.), Elsevier Science B.V. and the MIT Press, Amsterdam and Cambridge, 1995.

[9] T.H. Brylawski, The Tutte-Grothendieck ring, Algebra Universalis 2 (1972), 375-388.

[10] T.H. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171, (1972), 235-282.

[11] T.H. Brylawski, Intersection theory for graphs, J. Combin. Theory Ser. B, 30 (1980), 233-246.

[12] T.H. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, in: Matroid Applications, (N. White, ed.), Cambridge Univ. Press, Cambridge, 1992.

[13] C.J. Colbourn, The Combinatorics of Network Reliability, Oxford Univ. Press, New York, 1987.

[14] H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1970), 211-229.

[15] J.A. Eagon and V. Reiner, Resolutions of Stanley-Reisner rings and Alexander duality, preprint dated May 1996.

[16] I.M. Gessel and B.E. Sagan, The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electronic J. Combin. 3 (1996), #R9 (36 pages).

[17] F. Jaeger, Spin models for link invariants, in: Surveys in Combinatorics, 1995 (P. Rowlinson, ed.) London Math. Soc. Lecture Notes Ser. 218, Cambridge Univ. Press, Cambridge, 1995.

[18] F. Jaeger, D.L. Vertigan, and D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Camb. Phil. Soc. 108 (1990), 35-53.

[19] P.W. Kasteleyn and C.M. Fortuin, J. Phys. Soc. Japan Suppl. 26 (1969), 11-14.

[20] L.H. Kauffman, Statistical mechanics and the Jones polynomial, in: Braids, Contemporary Math. 78, Amer. Math. Soc., Providence, 1988.

[21] S. Negami, Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987), 601-622.

[22] J.G. Oxley, Graphs and series-parallel networks, in: Theory of Matroids (N. White, ed.), Cambridge Univ. Press, Cambridge, 1986.

[23] J.G. Oxley, A note on Negami’s polynomial invariants for graphs, Discrete Math. 76 (1989), 279-281.

[24] J.G. Oxley, Matroid Theory, Oxford Univ. Press, London and New York, 1992.

[25] J.G. Oxley and D.J.A. Welsh, The Tutte polynomial and percolation, in: Graph Theory and Related Topics, (J.A. Bondy and U.S.R. Murty, eds.) Academic Press, New York, 1979.

[26] G.-C. Rota, On the foundations of combinatorial theory I: Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340-368.

[27] J.R. Silvester, Introduction to Algebraic K-theory, Chapman and Hall, London and New York, 1981.

[28] R.P. Stanley, Cohen-Macaulay complexes, in: Higher Combinatorics (M. Aigner, ed.), D. Reidel, Dordrecht and Boston, 1977.

[29] W.T. Tutte, A ring in graph theory, Proc. Camb. Phil. Soc. 43 (1947), 26-40.

[30] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80-91.

[31] W.T. Tutte, On dichromatic polynomials, J. Combin. Theory 2 (1967), 301-320.

[32] D.G. Wagner, Zeros of reliability polynomials and f-vectors of matroids, preprint available

    at http://www.uwaterloo.ca/~dgwagner/Publications.html

[33] D.J.A. Welsh, Matroid Theory, London Math. Soc. Monographs 8, Academic Press, New York, 1976.

[34] D.J.A. Welsh, Percolation and related topics, Sci. Progr. (London) 64 (1977), 67-85.

[35] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), 572-579.

[36] H. Whitney, 2-isomorphic graphs, Amer. J. Math. 55 (1933), 245-254.

[37] Zaslavski, Strong Tutte functions of matroids and graphs, Trans. Amer. Math. Soc. 334, (1992), 317-347.

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

E-mail address: dgwagner@math.uwaterloo.ca