On sums over partially ordered sets

Klaus Dohmen Institut für Informatik Humboldt-Universität zu Berlin Unter den Linden 6 D-10099 Berlin, Germany

                   e-mail: dohmen@informatik.hu-berlin.de

Submitted: March 4, 1999; Accepted: July 13, 1999. AMS Classification: 05A15, 05A19, 05B35, 06A15

Abstract

We establish a general theorem for reducing sums of type ∑_{y≥x} g(y) where g is a mapping from a partially ordered set into an abelian group. Conclusions concern the Möbius function, the principle of inclusionexclusion, the Tutte polynomial and Crapo’s beta invariant.

1. Introduction

Sums over partially ordered sets frequently occur in combinatorics and related fields. Each application of the principle of inclusion-exclusion, for instance, gives rise to such a sum. From a computational point of view, the question wether such a sum can be reduced by excluding mutually cancelling terms is of fundamental importance, e.g., when computing the probability content of a convex polyhedron [8] or when assessing the reliability of a network [6, 12]. The difficulty lies in the circumstance that collections of mutually cancelling terms might not be disjoint, whence in general such terms cannot be removed without affecting the value of the sum.

In this paper, we establish a very general theorem that offers the possibility of reducing sums of the specified type. After dualizing the theorem and deducing some corollaries, the results are applied to the Möbius function of a partially ordered set and the principle of inclusion-exclusion, thus rediscovering several recent results. Finally, some conclusions to the Tutte polynomial and Crapo’s beta invariant are drawn.

2. Sums over partially ordered sets

We assume that the reader is familiar with partially ordered sets, which are subsequently referred to as posets. Most order-theoretic terminologies and notations are standard and can be looked up in the text book of Stanley [13]. Some less standard terminologies are reviewed now.

A poset P is called upper-finite if {y ∈ P | y ≥ x} is finite for any x ∈ P. Dually, P is called lower-finite if {y ∈ P | y ≤ x} is finite for any x ∈ P. A closure operator on P (cf. Rota [10, Section 2]) is a mapping c : P → P such that for any x, y ∈ P,

i) x ≤ c(x) (extensionality),
ii) x ≤ y ⇒ c(x) ≤ c(y) (monotonicity),
iii) c(c(x)) = c(x) (idempotence).

Dually, a kernel operator on P is a mapping k : P → P such that for any x, y ∈ P,

i) k(x) ≤ x (intensionality),
ii) x ≤ y ⇒ k(x) ≤ k(y) (monotonicity),
iii) k(k(x)) = k(x) (idempotence).

An element x ∈ P is referred to as c-closed if c(x) = x and as k-open if k(x) = x.

Lemma. Let P be a poset, k a kernel operator on P and x_{0} a k-open element of P. Then, all minimal elements of {y ∈ P | k(y) > x_{0}} are k-open.

Proof. Assume that y is not k-open and k(y) > x_{0}. It follows that k(y) < y and k(k(y)) > x_{0}, thus showing that y is not minimal in {y ∈ P | k(y) > x_{0}}. □

Our main result is the following:

Theorem 2.1. Let P be an upper-finite poset, f and g mappings from P into an abelian group such that f(x) = ∑_{y≥x} g(y) for any x ∈ P. Let k be a kernel operator on P, x_{0} a k-open element of P and f(x) = 0 for any k-open x > x_{0}. Then,

f(x_{0}) = ∑_{y: k(y)=x_{0}} g(y) .

Subsequently, we give two proofs of our main result. The first proof, which is due to an anonymous referee, uses downward induction on x_{0}, while the second proof, which is due to the author, uses the principle of inclusion-exclusion and additionally requires that P is an upper semilattice.

First Proof. We have to show that ∑_{y: k(y)>x_{0}} g(y) = 0. Evidently, if x_{0} is maximal in P, then this sum is empty, and hence the statement trivially holds. We proceed by downward induction on x_{0}. In this way, we obtain

∑_{y: k(y)>x_{0}} g(y) = ∑_{{x>x_{0} \atop x k-open}} ∑_{y: k(y)=x} g(y) = ∑_{{x>x_{0} \atop x k-open}} f(x) = 0 ,

where the second equality comes from the induction hypothesis and the third from the hypothesis of the theorem. □

Second Proof. Again, it suffices to show that ∑_{y: k(y)>x_{0}} g(y) = 0. Let Y_{0} consist of all minimal elements of {y ∈ P | k(y) > x_{0}}. By the principle of inclusion-exclusion,

∑_{y: k(y)>x_{0}} g(y) = ∑_{{y ≥ z for \atop some z ∈ Y_{0}}} g(y) = ∑_{Z⊆Y_{0}, Z≠∅}(−1)^{|Z|−1} ∑_{{y ≥ z for \atop all z ∈ Z}} g(y)

= ∑_{Z⊆Y_{0}, Z≠∅}(−1)^{|Z|−1} ∑_{y≥sup Z} g(y) = ∑_{Z⊆Y_{0}, Z≠∅}(−1)^{|Z|−1}f(sup Z) .

By the preceding lemma, any z ∈ Z is k-open and hence, sup Z is k-open. Since moreover sup Z > x_{0}, the requirements give f(sup Z) = 0, whence the result. □

Dualizing Theorem 2.1 we obtain

Theorem 2.1′. Let P be a lower-finite poset, f and g mappings from P into an abelian group such that f(x) = ∑_{y≤x} g(y) for any x ∈ P. Let c be a closure operator on P, x_{0} a c-closed element of P and f(x) = 0 for any c-closed x < x_{0}. Then,

f(x_{0}) = ∑_{y: c(y)=x_{0}} g(y) .

Some corollaries of Theorem 2.1 are now deduced:

Corollary 2.2. Let P be a finite poset with minimum ˆ0, f and g mappings from P into an abelian group such that f(x) = ∑_{y≥x} g(y) for any x ∈ P, and X a supremum-closed subset of P such that x > ˆ0 and f(x) = 0 for any x ∈ X. Then,

f(ˆ0) = ∑_{y: y≱x ∀ x∈X} g(y) . (∗)

Proof. For any y ∈ P define k(y) := ⋁ {x ∈ X | x ≤ y}, where ⋁ ∅ := ˆ0. Then, y is k-open if and only if y ∈ X or y = ˆ0, and k(y) = ˆ0 if and only if y ≱ x for any x ∈ X. Now, the corollary follows from Theorem 2.1. □

Corollary 2.3. Let P be a finite lattice with minimum ˆ0, f and g mappings from P into an abelian group such that f(x) = ∑_{y≥x} g(y) for any x ∈ P. Let c : P → P be an extensional mapping and X ⊆ P such that {c(x) | x ∈ X} is a chain in P and such that x > ˆ0 and f|_{[x,c(x)]} ≡ 0 for any x ∈ X. Then, (∗) holds.

Proof. We apply Corollary 2.2 with X′ := {⋁ I | ∅ ≠ I ⊆ X} instead of X. Then, X′ is supremum-closed and for any x′ ∈ X′ the chain assumption implies

x′ = ⋁ {x | x ∈ X, x ≤ x′} ≤ ⋁ {c(x) | x ∈ X, x ≤ x′} = c(x_{0})

for some x_{0} ∈ X, x_{0} ≤ x′. Therefore, x′ ∈ [x_{0}, c(x_{0})] and hence, f(x′) = 0. □

As a first application of the preceding results, we deduce a prominent result of Rota [10, Section 5, Proposition 4] on the Möbius function of a lower-finite poset, which in turn specializes to Weisner’s theorem [14] in the particular case where the poset is a lattice having minimum ˆ0 and the closure operator is given by c(y) = y ∨ a for some fixed a > ˆ0. Recall that the Möbius function of a lower-finite poset P having minimum ˆ0 is the unique ℤ-valued function μ_{P} on P such that ∑_{y≤x} μ_{P} (y) = δ_{ˆ0x} for any x ∈ P, where δ is the usual Kronecker delta.

Corollary 2.4 (Rota). Let P be a lower-finite poset with minimum ˆ0, and let c be a closure operator on P such that ˆ0 is not c-closed. Then, for any x_{0} ∈ P,

∑_{y: c(y)=x_{0}} μ_{P} (y) = 0 .

Proof. For x ∈ P define f(x) := ∑_{y≤x} μ_{P} (y) = δ_{ˆ0x}. There is nothing to prove if x_{0} is not c-closed. Otherwise, x_{0} ≠ ˆ0 and hence, f(x_{0}) = 0. By the same argument, f(x) = 0 for any c-closed x < x_{0}. Thus, Rota’s result follows from Theorem 2.1′. □

As a second application, we deduce a recent result of Blass and Sagan [1] on the Möbius function of a finite lattice. As pointed out in [1], it generalizes a particular case of Rota’s broken circuit theorem on geometric lattices [10] as well as a prior generalization of that particular case due to Sagan [11].

Corollary 2.5 (Blass-Sagan). Let L be a finite lattice, whose set of atoms A(L) is given a partial order, which is denoted by ⊴ to distinguish it from the partial order ≤ in L. Let 𝒳 consist of all non-empty subsets X of A(L) such that for any x ∈ X there is some a ∈ A(L) satisfying a ◁ x and a < ⋁ X. Then, for any y ∈ L,

μ_{L}(y) = ∑_{Y ⊆A(L), ⋁Y =y ; Y ⊉X (∀X∈𝒳)}(−1)^{|Y |} .

Proof. By a particular case of Rota’s crosscut theorem [10, Theorem 3],

μ_{L}(y) = ∑_{Y ⊆A(L)} ε_{y}(Y) ,

where ε_{y}(Y) := (−1)^{|Y |} if ⋁ Y = y and ε_{y}(Y) := 0 otherwise. Since 𝒳 turns out to be union-closed, by Corollary 2.2 it suffices to show that for any X ∈ 𝒳,

(1)  ∑_{Y : X⊆Y ⊆A(L)}ε_{y}(Y) = 0 .

Let a_{X} be ⊴-minimal in {a ∈ A(L) | a < ⋁ X}. Then, a_{X} ∉ X since otherwise a ◁ a_{X} and a < ⋁ X for some a ∈ A(L), contradicting the definition of a_{X}. ¿From a_{X} < ⋁ X and a_{X} ∉ X we conclude that Y ↦ Y △ {a_{X}}, where △ denotes symmetric difference, is a sign-reversing involution on {Y | X ⊆ Y ⊆ A(L), ⋁ Y = y}, whence (1) is shown. □

3. Principle of inclusion-exclusion

The principle of inclusion-exclusion, which is also known as the sieve formula or the formula of Poincare or Sylvester, plays a significant role in many areas of mathematics. For any Boolean algebra of sets A, any modular function μ from A into an abelian group satisfying μ(∅) = 0 and any finite family {A_{v}}_{v∈V} ⊆ A it states that

μ ( ⋂_{v∈V} ∁A_{v}) = ∑_{I⊆V} (−1)^{|I|} μ ( ⋂_{i∈I} A_{i}) , (IE)

where for any set A, ∁A denotes the complement of A in ⋃ A, and ⋂_{i∈∅} A_{i} = ⋃ A. Recall that a function μ from A into an abelian group is called modular if

μ(A ∩ B) + μ(A ∪ B) = μ(A) + μ(B)

for any A, B ∈ A. In particular, any measure on A is modular. For abbreviation, we refer to (Ω, A, μ) as a generalized measure space if A is a Boolean algebra of sets whose union is Ω and if μ is a modular function from A into an abelian group such that μ(∅) = 0. Thus, any measure space is a generalized measure space.

Let’s apply the results of Section 2 to this setting. For any X, Y ⊆ V define

f(X) := (−1)^{|X|} μ ( ⋂_{x∈X} A_{x} ∩ ⋂_{v∉X} ∁A_{v}) ; g(Y) := (−1)^{|Y |} μ ( ⋂_{y∈Y} A_{y}) .

The principle of inclusion-exclusion, applied to the function μ_{X} := μ(⋂_{x∈X} A_{x} ∩ ·), shows that f(X) = ∑_{Y ⊇X} g(Y) for any subset X of V. Note that the latter identity coincides with (IE) if X = ∅. In this way, the following results on the principle of inclusion-exclusion directly follow from the corresponding results of Section 2. (More precisely, 2.1 ⇒ 3.1, 2.2 ⇒ 3.2, 2.3 ⇒ 3.3; also note that 3.1 ⇒ 3.2 ⇒ 3.3.)

Theorem 3.1. Let (Ω, A, μ) be a generalized measure space, {A_{v}}_{v∈V} a finite family of sets in A and k a kernel operator on the power set of V such that ⋂_{x∈X} A_{x} ⊆ ⋃_{v∉X} A_{v} for any non-empty and k-open subset X of V. Then,

μ ( ⋂_{v∈V} ∁A_{v}) = ∑_{I : k(I)=∅}(−1)^{|I|} μ ( ⋂_{i∈I} A_{i}) . (∗∗)

Corollary 3.2. Let (Ω, A, μ) be a generalized measure space, {A_{v}}_{v∈V} a finite family of sets in A and 𝒳 a union-closed set of non-empty subsets of V such that ⋂_{x∈X} A_{x} ⊆ ⋃_{v∉X} A_{v} for any X ∈ 𝒳. Then,

μ ( ⋂_{v∈V} ∁A_{v}) = ∑_{I : I⊉X ∀ X∈𝒳}(−1)^{|I|} μ ( ⋂_{i∈I} A_{i}) . (∗ ∗ ∗)

Corollary 3.3. Let (Ω, A, μ) be a generalized measure space, {A_{v}}_{v∈V} a finite family of sets in A, c an extensional mapping from the power set of V into itself and 𝒳 a set of non-empty subsets of V such that {c(X) | X ∈ 𝒳} is a chain and ⋂_{x∈X} A_{x} ⊆ ⋃_{v∉c(X)} A_{v} for any X ∈ 𝒳. Then, (∗ ∗ ∗) holds.

As a further corollary, a recent improvement of the inclusion-exclusion principle [4, 5] is deduced. As noted in [4, 5, 6], it generalizes Narushima’s inclusion-exclusion variant for posets [9], Shier’s chain formula for the reliability of a network [12, Section 6.3] and Whitney’s broken circuit theorem on chromatic polynomials [16].

Corollary 3.4. Let (Ω, A, μ) be a generalized measure space, {A_{v}}_{v∈V} a finite family of sets in A, where V is equipped with a linear ordering relation, and 𝒳 a set of non-empty subsets of V such that ⋂_{x∈X} A_{x} ⊆ ⋃_{v>max X} A_{v} for any X ∈ 𝒳. Then, (∗ ∗ ∗) holds.

Proof. Corollary 3.4 follows from Corollary 3.3 by using the extensional mapping X ↦ c(X) where c(X) := {v ∈ V | v ≤ max X} if X ≠ ∅ and c(∅) := ∅. □

Bonferroni-like inequalities corresponding to (∗∗) and (∗ ∗ ∗) will appear in [3].

4. Tutte polynomial and Crapo’s beta invariant

Before stating our results on the Tutte polynomial and Crapo’s beta invariant, we briefly review some basic notions of matroid theory. For details, see Welsh [15].

A matroid is a pair M = (E, r) consisting of a finite set E and a ℤ-valued function r on 𝒫(E) (= power set of E) such that for any A, B ⊆ E,

i) 0 ≤ r(A) ≤ |A|,
ii) A ⊆ B ⇒ r(A) ≤ r(B),
iii) r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B).

For instance, if G is a finite graph having vertex-set V and edge-set E and r(A) is the number of vertices of G minus the number of connected components of the subgraph having vertex-set V and edge-set A, then M(G) = (E, r) is a matroid.

For any matroid M = (E, r) and any X ⊆ E, the contraction of X from M is given by M/X := (E \ X, r_{X}) where r_{X}(I) := r(X ∪ I) − r(X) for any I ⊆ E \ X.

The Tutte polynomial T (M; a, b) of a matroid M = (E, r) is defined by

T (M; a, b) := ∑_{I⊆E} (a − 1)^{r(E)−r(I)}(b − 1)^{|I|−r(I)} ,

where a and b are independent variables over some commutative ring with unity.

Theorem 4.1. Let M = (E, r) be a matroid and k a kernel operator on 𝒫(E) such that T (M/X; a, b) = 0 for any non-empty, k-open subset X of E. Then,

T (M; a, b) = ∑_{I : k(I)=∅}(a − 1)^{r(E)−r(I)}(b − 1)^{|I|−r(I)} .

Proof. For any X ⊆ E define f(X) := ∑_{I⊇X}(a − 1)^{r(E)−r(I)}(b − 1)^{|I|−r(I)}. Then, by Theorem 2.1, it suffices to prove that f(X) = 0 for any non-empty, k-open subset X of E. With \overline{X} denoting the complement of X in E we obtain

f(X) = ∑_{I⊆\overline{X}} (a − 1)^{r(E)−r(X∪I)}(b − 1)^{|X∪I|−r(X∪I)}
= (a − 1)^{r(E)−r(X)−r_{X}(\overline{X})}(b − 1)^{|X|−r(X)} ∑_{I⊆\overline{X}}(a − 1)^{r_{X}(\overline{X})−r_{X}(I)}(b − 1)^{|I|−r_{X}(I)}
= (a − 1)^{r(E)−r(X)−r_{X}(\overline{X})}(b − 1)^{|X|−r(X)} T (M/X; a, b) = 0 . □

By employing an appropriate kernel operator on the power set of E we now prove the following corollary, which is due to Heron [7, Theorem 1.10] and which generalizes Whitney’s broken circuit theorem [16] from graphs to matroids. Recall that the characteristic polynomial of a matroid M = (E, r) is defined by

χ(M; λ) := (−1)^{r(E)} T (M; 1 − λ, 0) = ∑_{I⊆E} (−1)^{|I|} λ^{r(E)−r(I)}

and that a circuit of a matroid M = (E, r) is a non-empty subset C of E such that r(C \ {c}) = |C| − 1 = r(C) for any c ∈ C. If E is linearly ordered and C is a circuit of M, then C \ {max C} is referred to as a broken circuit of M.

Corollary 4.2 (Heron). Let M = (E, r) be a matroid, where E is equipped with a linear ordering relation. Then,

χ(M; λ) = ∑_{k=0}^{|E|} (−1)^{k} b_{k}(M) λ^{r(E)−k}

where b_{k}(M) is the number of k-subsets of E which do not include a broken circuit of M. In particular, the coefficients of χ(M; λ) alternate in sign.

Proof. It is easy to see (cf. Lemma 1.4 of Heron [7]) that, in general,

(†) χ(M; λ) = 0 if M contains a loop (= circuit of cardinality 1).

For any subset I of E let k(I) denote the union of all broken circuits included by I. Then, k is a kernel operator on the power set of E, where k(I) = ∅ if and only if I includes no broken circuit, and where X is k-open if and only if X is a union of broken circuits. In the latter case, X ∪ {e} includes a circuit for some e > max X and hence, r(X ∪ {e}) = r(X), or equivalently, r_{X}({e}) = 0. Therefore, e is a loop of M/X and hence by (†), χ(M/X; λ) = 0. By applying Theorem 4.1 and using the fact that r(I) = |I| for any I including no broken circuit we obtain χ(M; λ) = ∑_{I : k(I)=∅}(−1)^{|I|}λ^{r(E)−|I|}. Now, by collecting powers of λ the corollary follows. □

Results similar to Theorem 4.1 and Corollary 4.2 can also be obtained for Crapo’s beta invariant [2], which for every matroid M = (E, r) is defined by

β(M) := (−1)^{r(E)} ∑_{I⊆E} (−1)^{|I|} r(I) .

Recall that a matroid M = (E, r) is disconnected if and only if there is a pair of distinct elements of E that are not jointly contained by a circuit of M.

Theorem 4.3. Let M = (E, r) be a matroid, and let k be a kernel operator on the power set of E such that E is not k-open and M/X is disconnected or a loop for any non-empty, k-open subset X of E. Then,

β(M) = (−1)^{r(E)} ∑_{I : k(I)=∅}(−1)^{|I|} r(I) .

Proof. By Lemma II of Crapo [2], β(M) = 0 if M is disconnected or a loop. By this and the assumptions, β(M/X) = 0 for any non-empty, k-open subset X of E. By Theorem 2.1 it suffices to prove that f(X) = 0 for each such X, where f(X) := ∑_{I⊇X}(−1)^{|I|}r(I). Since the assumptions entrain \overline{X} ≠ ∅, we obtain

f(X) = ∑_{I⊆\overline{X}}(−1)^{|X∪I|}r(X ∪ I) ≐ ∑_{I⊆\overline{X}}(−1)^{|I|} (r_{X}(I) + r(X)) ≐ β(M/X) = 0 ,

where ≐ means equality up to sign. □

Corollary 4.4. Let M = (E, r) be a matroid, where E is equipped with a linear ordering relation. Then,

β(M) = (−1)^{r(E)} ∑_{k=1}^{|E|} (−1)^{k} k b_{k}(M)

the electronic journal of combinatorics 6 (1999), #R34 9 where again b_{k}(M) is the number of k-subsets of M including no broken circuit.

Proof. Corollary 4.4 can be deduced from Theorem 4.3 in the same way as Corollary 4.2 is deduced from Theorem 4.1. Alternatively, consider the identity

β(M) = (−1)^{r(E)−1} \frac{dχ(M; λ)}{dλ}|_{λ=1}

and apply Corollary 4.2. □

References

[1] A. Blass and B.E. Sagan, Möbius Functions of Lattices, Adv. Math. 127 (1997), 94–123.

[2] H.H. Crapo, A higher invariant for matroids, J. Comb. Theory 2 (1967), 406–417.

[3] K. Dohmen, Improved Bonferroni inequalities via union-closed set systems, J. Comb. Theory Ser. A, accepted for publication.

[4] K. Dohmen, An improvement of the inclusion-exclusion principle, Arch. Math. 72 (1999), 298–303.

[5] K. Dohmen, Improved inclusion-exclusion identities and inequalities based on a particular class of abstract tubes, Electron. J. Probab. 4 (1999), paper # 5.

[6] K. Dohmen, Inclusion-exclusion and network reliability, Electron. J. Comb. 5 (1998), paper # R36.

[7] A.P. Heron, Matroid polynomials, In: D.J.A. Welsh and D.R. Woodall (Eds.), Combinatorics, The Institute of Mathematics and Its Applications, Southendon-Sea, 1972.

[8] D.Q. Naiman and H.P. Wynn, Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling, Ann. Statist. 25 (1997), 1954–1983.

[9] H. Narushima, Principle of inclusion-exclusion on partially ordered sets, Discrete Math. 42 (1982), 243–250.

[10] G.C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie Verw. Geb. 2 (1964), 340–368.

[11] B.E. Sagan, A generalisation of Rota’s NBC Theorem, Adv. Math. 111 (1995), 195–207.

[12] D.R. Shier, Network reliability and algebraic structures, Clarendon Press, Oxford, 1991.

[13] R.P. Stanley, Enumerative Combinatorics, 2nd ed., Vol. I, Cambridge University Press, Cambridge, 1997.

[14] L. Weisner, Abstract theory of inversion of finite series, Trans. Amer. Math. Soc. 38 (1935), 474–484.

[15] D.J.A. Welsh, Matroid Theory, Academic Press, New York, 1976.

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