Möbius Functions of Lattices

Andreas Blass University of Michigan and Bruce E. Sagan Michigan State University

1. The NBB theorem

2. Comparison with NBC and Crosscut Theorems 3. Applications

4. LL Lattices and Supersolvability

5. Remarks THE NBB THEOREM

Let (L, ≤) be a finite lattice with minimum ˆ0 and maximum ˆ1. Let μ : L → Z be L’s Möbius function which is the unique function satisfying

_{y≤x}^{∑} μ(y) = δ_{ˆ0x}.

Let A(L) be the atom set of L and put an arbitrary partial order ⊴ on A(L). Then D ⊆ A(L) is bounded below (BB) if, for every d ∈ D there is an a ∈ A(L) such that

a ⊲ d  and
a < ⋁ D.

Then B ⊆ A(L) is an NBB base of x if x = ⋁ B and B does not contain any D which is BB.

Theorem 1 Let L be any finite lattice and let ⊴ be any partial order on A(L). Then for all x ∈ L

μ(x) = _{B}^{∑}(−1)^{|B|}

where the sum is over all NBB bases B of x.

D ⊆ A(L) is BB if ∀d ∈ D ∃a ∈ A(L) such that

a ⊲ d  and  a < ⋁ D.

NBB Theorem. For all x ∈ L μ(x) = _{B}^{∑}(−1)^{|B|}

where the sum is over all NBB bases B of x.

[figure: (L, ≤) =; ˆ1; x; a; ˆ0; c; y; b; (A(L), ⊴) =; a; b; c]

Ex. Note that from the definition of BB

1. No set containing a min. element of ⊴ is BB.

2. No single element set is BB. So for L and ⊴ in the figure, the only possible BB set is {a, c}. It is since b ⊲ a, c and b < ⋁{a, c} = ˆ1.

x  ˆ0  a  x  ˆ1
NBB bases  ∅  a  ab none
μ(x)  (−1)^{0} (−1)^{1} (−1)^{2}  0

NBB Theorem. For all x ∈ L

μ(x) = _{B}^{∑}(−1)^{|B|}

where the sum is over all NBB bases B of x.

Pf. Let μ̃(x) = _{B}^{∑}(−1)^{|B|} & show _{y≤x}^{∑} μ̃(y) = δ_{ˆ0x}.

x = ˆ0: NBB base B = ∅ & ∑_{y≤ˆ0} μ̃(y) = (−1)^{0} = 1.

x > ˆ0: want signed S & sign-reversing involution ι.

S := {B an NBB base for some y ≤ x}
ϵ(B) := (−1)^{|B|}
_{y≤x}^{∑} μ̃(y) = _{B∈S}^{∑} ϵ(B).
ι(B) := B △ a_{0}

where △ is the symmetric difference operator and a_{0} ≤ x is ⊴-min. Suffices to show ι(B) is still NBB.

ι(B) = B \ a_{0}: clear. If ι(B) = B ∪ a_{0} := B′ ⊇ D where D is BB then a_{0} ∈ D. Let a be the element guaranteed for a_{0} from the definition of BB. Then a ⊲ a_{0} and a < ⋁ D ≤ ⋁ B′ ≤ x, contradicting the definition of a_{0}.

COMPARISON WITH NBC AND CROSSCUT

Let L be geometric with rank function ρ. So for any B ⊆ A(L) we have ρ(⋁ B) ≤ |B|. Say B is independent if ρ(⋁ B) = |B|. A minimal dependent set C is a circuit. If ⊴ is a total order on A(L) then C′ = C \ min C is a broken circuit (BC). An NBC base B for x has ∨B = x and B contains no BC.

Theorem 2 (Rota) 1. (NBC) Let L be geometric, ⊴ total. If x ∈ L:

μ(x) = (−1)^{ρ(x)}(number of NBC bases of x ).

2. (Crosscut) Let L be any finite lattice. If x ∈ L:

μ(x) = _{B}^{∑}(−1)^{|B|}

where the sum is over all B ⊆ A(L) with ⋁ B = x.

If L is geometric and ⊴ is total than the NBC and NBB bases are the same. Further, all bases of x have size ρ(x). If L is arbitrary and ⊴ is total incomparability then the NBB bases are all B with ⋁ B = x. Thus our theorem interpolates between NBC and Crosscut.

APPLICATION 1: SHUFFLE POSETS

A subword of x = x_{1} … x_{m} is word x′ = x_{i_{1}} … x_{i_{k}} with i_{1} < … < i_{k}. A shuffle of x and y = y_{1} … y_{n} where x ∩ y = ∅ is s = s_{1} … s_{m+n} having x and y as subwords denoted s_{x} and s_{y}

Fix x = x_{1} … x_{m}, y = y_{1} … y_{n}. Greene’s poset of shuffles has as elements all shuffles w of a subword of x and a subword of y with v ≤ w iff v_{x} ⊇ w_{x} and v_{y} ⊆ w_{y}.

A(W_{m,n}): An a-atom, resp. b-atom, is gotten from x by deleting a letter of x, resp. inserting a letter of y. Let A_{a} = set of a-atoms, A_{b} = set of b-atoms. Define ⊴ by a ⊲ b iff a ∈ A_{a} and b ∈ A_{b}

Theorem 3 1. Let s be a shuffle of x, y and let

B_{s} = A_{a} ∪ {b ∈ A_{b} : b ≤ s}.

Then the NBB bases of y ∈ W_{m,n} under the given partial order are exactly the B_{s}.

2. [Greene] μ(W_{m,n}) = (−1)^{m+n} \binom{m+n}{m}.

[figure: de; de; d; e; Dde; dDe; deD; ∅; Dd; De; dD; eD; D; W_{2,1}; d; e; Dde; dDe; deD; (A(W_{2,1} ), ⊴)]

Example W_{2,1} : A_{a} = {d, e}, A_{b} = {Dde, dDe, deD}

\begin{matrix}s & Dde & dDe & deD \\ B_{s} & \{d, e, Dde\} & \{d, e, dDe\} & \{d, e, deD\} \end{matrix}

D = {Dde, dDe} is BB: ⋁ D = De so e < ⋁ D and e ⊲ Dde, dDe.

B = {d, e, Dde} is NBB: Take D ⊆ B. No D with d ∈ D is BB (d is ⊴-min) nor with |D| ≤ 1. So check D = {e, Dde}: ⋁ D = De and e in ⊴-min under De so D is not BB.

2: NON-CROSSING PARTITIONS

Arrange the numbers in [n] = {1, …, n} in order around a circle. Partition π = B_{1}/ … /B_{k} of [n] is non-crossing if, when replacing each block by a complete graph, no edge of B_{i} crosses an edge of B_{j}. Let NC_{n} be the lattice of non-crossing partitions ordered by refinement.

Each atom of NC_{n} is an edge rs. A set of atoms is non-crossing if its graph contains no pair of crossing edges. Define ⊴ to be the ranked poset with rank r− 1 being {rs : r > s} and all possible covers between ranks.

Theorem 4 1. The NBB bases of NC_{n} are those non-crossing forests obtained by picking at most one atom from each rank of (A(NC_{n}), ⊴).

2. [Kreweras] μ(ˆ1) = (−1)^{n−1}C_{n−1} where C_{n−1} is a Catalan number.

Examples.

[figure: noncrossing partition; 8/7651/432:; 6; 5; 7; 4; 8; 3; 1; 2; crossing partition; 87/652/431:; 6; 5; 7; 4; 8; 3; 1; 2]

The poset (A(NC_{4}), ⊴):  [figure: 21; 31; 32; 41; 42; 43]

Some BB and NBB sets in A(NC_{4}):

1. D = {31, 32} is BB (atoms from the same rank) since we have 21 ⊲ 31, 32 and 21 < ⋁ D = 321.

2. D = {31, 42} is BB (crossing atoms) since we have 21 ⊲ 31, 42 and 21 < ⋁ D = 4321.

3. B = {32, 42} is NBB since if b = 32 then a ⊲ b implies a = 21. But 21 is not ⊲ ⋁ B = 432.

LL LATICES & SUPERSOLVABILITY

Let Δ : ˆ0 = x_{0} < x_{1} < … < x_{n−1} < x_{n} = ˆ1 be a maximal chain of L. It induces both levels

A_{i} = {a ∈ A | a ≤ x_{i} but a ≰ x_{i−1}}

and ⊴ by a ⊲ b iff a ∈ A_{i} and b ∈ A_{j} with i < j.

ρ(x) := #{i : A_{i} contains an atom ≤ x }.

The level condition is

⊴ is induced & a ⊲ b_{1} ⊲ b_{2} ⊲ … ⊲ b_{k} ⇒ a ≰ ⋁_{i=1}^{k} b_{i}.

An element x ∈ L is left-modular if for all z ≤ y:

z ∨ (x ∧ y) = (z ∨ x) ∧ y

Chain Δ/lattice L are left-modular if all the elements x_{i} are left-modular. An LL lattice has a leftmodular Δ satisfying the level condition.

Proposition 5 The following implications hold for L but not their converses.

1. semimodular ⇒ level condition

2. supersolvable ⇒ left-modular.

[figure: de; d; e; Dde; dDe; deD; ∅; Dd; De; dD; eD; D; W_{2,1}; d; e; Dde; dDe; deD; (A(W_{2,1} ), ⊴)]

Example W_{2,1} : Let Δ : de < d < ∅ < D of length 3. This induces

A_{1} = {d}, A_{2} = {e}, A_{3} = {Dde, dDe, deD}

and the partial order in the figure. Bases for ˆ1:

{d, e, Dde}, {d, e, dDe}, {d, e, deD}

Characteristic polynomial

χ(W_{2,1} , t) := _{x∈W_{2,1}}^{∑} μ(x)t^{3−ρ(x)}
= (t − 1)^{2}(t − 3)
= (t − |A_{1}|)(t − |A_{2}|)(t − |A_{3}|)

Theorem 6 Let (L, Δ) be LL with Δ of length n and ⊴ induced. Then

1. The NBB bases of L are those taking ≤ 1 atom from each A_{i} and B an NBB base of x ⇒ |B| = ρ(x).

2. χ(L, t) := ∑_{x∈L} μ(x)t^{n−ρ(x)} = ∏_{i=1}^{n} (t − |A_{i}|).

Proof We will show 1 ⇒ 2. By the NBB Theorem:

χ(L, t) = _{x∈L}^{∑} _{⋁{B:NBB }=x}^{∑} (−1)^{|B|}t^{n−ρ(x)}
= _{|B∩A_{i}|≤1}^{∑}(−1)^{|B|}t^{n−|B|}

= n ; ∏ ; i=1 (t − |A_{i}|).

Corollary 7 Consider the shuffle posets W_{m,n} with x = x_{1} … x_{m}, y = y_{1} … y_{n}.

1. [Greene] There is a left-modular chain

Δ : x < x_{2} … x_{n} < … < ∅ < y_{1} < y_{1}y_{2} < … < y

2. If n = 1 then Δ satifies the level condition so

χ(W_{m,1}, t) = (t − 1)^{m}(t − m − 1).

For general n > 2, Δ does not satisfy the level condition and χ does not factor.

REMARKS

Topology and algebra. Segev has shown that the NBB complex is homotopic to the order complex. This can be used to rederive results of Kahn, Linusson, Edelman and Reiner. Liu and S have shown that left-modular lattices are shellable. Can NBB sets be used to define an Orlik-Solomon algebra?

Perfect orders. When computing μ(x) it is simplest to have the minimum number of bases, namely |μ(x)|, all of the same parity. Call ⊴ perfect if this happens for alll x ∈ L. If ⊴ is perfect then so is any linear extension, however it is often clearer combinatorially to use ⊴ with as few relations as possible. There are also posets with no perfect order. Can one characterize which posets have a perfect order?

Spliting χ. Stanley has proved that if x ∈ L with x modular and L geometric then

χ(L, t) = χ(L_{x}, t) _{y:y∧x=ˆ0}^{∑} μ(y)t^{n−ρ(x)−ρ(y)}

where L_{x} is the lower order ideal generated by x. An analog of this result is currently being investigated by Liu and S.