Möbius Functions of Embedding Orders

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 sagan@math.msu.edu www.math.msu.edu/˜ sagan and Vincent R. Vatter Department of Mathematics Rutgers University Frelinghuysen Rd Piscataway, NJ 08854-8019 vatter@math.rutgers.edu

1. Möbius functions

2. Subword order

3. Layered permutations

4. Further work 1. Möbius functions

Let (P, ≤) be a finite poset (partially ordered set). Let Int P be the set of closed intervals in P:

[x, z] = {y ∈ P | x ≤ y ≤ z}.

The incidence algebra of P is the set

I(P) = {ϕ | ϕ : Int P → ℂ}

under the operations

\begin{aligned}(ϕ + ψ)(x, z) & = & ϕ(x, z) + ψ(x, z), \\ (cϕ)(x, z) & = & cϕ(x, z), c ∈ ℂ, \\ (ϕ ∗ ψ)(x, z) & = & _{x≤y≤z}^{∑} ϕ(x, y)ψ(y, z). \end{aligned}

Then I(P) is an algebra with unit the Kronecker delta δ(x, z) since δ ∗ ϕ = ϕ ∗ δ = ϕ, e.g.,

(δ ∗ ϕ)(x, z) = _{x≤y≤z}^{∑} δ(x, y)ϕ(y, z) = ϕ(x, z).

Element ϕ ∈ I(P) has convolution inverse ϕ^{−1} iff ϕ(x, x) ≠ 0 for all x ∈ P. The zeta function of P is ζ(x, z) = 1 for all x, z ∈ P. The Möbius function of P is μ = ζ^{−1} so ζ ∗ μ = δ or ∑_{x≤y≤z} μ(y, z) = δ(x, z) or

μ(x, z) = \{ \begin{matrix}1 & if x = z, \\ − _{x<y≤z}^{∑} μ(y, z) & if x < z. \end{matrix}

μ(x, z) = \{ \begin{matrix}1 & if x = z, \\ − _{x<y≤z}^{∑} μ(y, z) & if x < z. \end{matrix}

Ex. Let B_{n} be the Boolean algebra of all subsets of [n] = {1, …, n} ordered by inclusion. We compute μ(x, [3]) in B_{3}, putting the value to the right of x in the following Hasse diagram.

[figure: ∅; {1}; {2}; {3}; {1, 2}; {1, 3}; {2, 3}; [3]]

Theorem 1 (Möbius Inversion Thm) Given any two functions f, g : P → ℂ, then

\begin{matrix}f(z) = _{x≤z}^{∑} g(x) ∀z ∈ P \\ ⟺ g(z) = _{x≤z}^{∑} μ(x, z)f(x) ∀z ∈ P. \end{matrix}

This Theorem has as corollaries the Principle of Inclusion-Exclusion (for P = B_{n}), the Fundamental Theorem of the Difference Calculus (for P a chain), and the Möbius Inversion Theorem of Number Theory (for P a divisor lattice).

2. Subword order

Let A be an alphabet with 0 ∉ A. Partially order

A^{∗} = {w | w a finite word over A }

by v ≤ w iff v is a subword of w.

Ex. If w = a a b b b a b a then v = a b b a is a subword as is shown by the green letters in w = a a b b b a b a.

Word ϵ = ϵ(1) … ϵ(n) ∈ (A ∪ 0)^{∗} has support

Supp ϵ = {i | ϵ(i) ≠ 0}.

An expansion of v ∈ A^{∗} is ϵ_{v} ∈ (A ∪ 0)^{∗} such that if one restricts ϵ_{v} to its support one obtains v. An embedding of v into w = w(1) … w(n) is an expansion ϵ_{v} = ϵ_{v}(1) … ϵ_{v}(n) of v such that

ϵ_{v}(i) = w(i) for all i ∈ Supp ϵ_{v} .

Note that v ≤ w in A^{∗} iff there is an embedding ϵ_{v} of v into w.

Ex. In the previous example, the expansion of v corresponding to the given subword of w is just ϵ_{v} = a 0 b 0 0 0 b a.

Given a word w = w(1) … w(n) then a run of a’s in w is a maximal interval of indices [r, s] such that

w(r) = w(r + 1) = ⋯ = w(s) = a.

Ex. w = a a b b b a b a has runs of a’s: [1, 2], [6, 6], [8, 8]; and runs of b’s: [3, 5] and [7, 7].

An embedding ϵ_{v} of v into w is normal if for every a ∈ A and every run [r, s] of a’s we have

(r, s] ⊆ Supp ϵ_{v}.

Ex. In w = a a b b b a b a any normal embedding must contain the elements in blue. So there are two normal embeddings of v = a b b a, namely ϵ_{v} = 0 a 0 b b a 0 0 and ϵ_{v} = 0 a 0 b b 0 0 a.

Theorem 2 (Björner) In A^{∗} we have

μ(v, w) = (−1)^{|w|−|v|}\binom{w}{v}_{n}

where |w| is the length of w and \binom{w}{v}_{n} is the number of normal embeddings of v in w.

Ex. We have

μ(abba, aabbbaba) = (−1)^{8−4} · 2 = 2.

3. Layered permutations

Let ℙ denote the positive integers. Let 𝔖_{n} denote the symmetric group on [n]. Then π ∈ 𝔖_{n} is layered if π has the form

π = a (a − 1) … 1 b (b − 1) … (a + 1) …

Let 𝔏 be the set of layered permutations partially ordered by pattern containment. Then there is a bijection 𝔏 ↔ ℙ^{∗} given by π ↔ p = p(1) … p(k) where the p(i) are the layer lengths of π. Under this bijection, the partial order becomes p ≤ q iff there is an expansion ϵ_{p} of p which has length |q| and satisfies

ϵ_{p}(i) ≤ q(i) for all 1 ≤ i ≤ |q| .

Call such an expansion an embedding of p in q.

Ex. If π = 3 2 1 5 4 and σ = 4 3 2 1 6 5 8 7 then one occurrence of π in σ is given by the green numbers in σ = 4 3 2 1 6 5 8 7 . In ℙ^{∗} we have π and σ corresponding to p = 3 2 and q = 4 2 2, respectively. And the occurrence of p in q corresponds to ϵ_{p} = 3 0 2.

An embedding ϵ_{p} of p in q ∈ 𝔖_{n} is normal if

1. For all i, 1 ≤ i ≤ n, we have ϵ_{p}(i) = q(i), q(i) − 1, or 0.

2. For every k ∈ ℙ and every run [r, s] of k’s

(a) (r, s] ⊆ Supp ϵ_{p} if k = 1,

(b) r ∈ Supp ϵ_{p} if k > 1.

Ex. In q = 2 2 1 1 1 3 3 then any normal embedding must support the elements in blue. So there are two normal embeddings of p = 2 1 1 1 3, namely ϵ_{p} = 2 1 0 1 1 3 0 and ϵ_{p} = 2 0 1 1 1 3 0.

The sign of a normal embedding ϵ_{p} of p in q is

(−1)# of i where ϵ^{p}(i) = q(i) − 1 .

The exponent is the defect d(ϵ_{p}).

Theorem 3 (S-V) In 𝔏 we have

μ(p, q) = _{ϵ_{p}}^{∑}(−1)^{d(ϵ_{p})}

summed over all normal embeddings ϵ_{p} of p in q.

Ex. We have

μ(21113, 2211133) = (−1)^{2} + (−1)^{0} = 2.

4. Further work

A. Topology of 𝔏. If P is a poset then [x, z] ⊆ P has order complex

Δ(x, z) = {c | c a chain in (x, z) }.

So Δ(x, z) is a simplicial complex with reduced Euler characteristic

χ̃(Δ(x, z)) := _{i≥−1}^{∑}(−1)^{i} rk H̃_{i}(Δ(x, z)) = μ(x, z).

Theorem 4 (Björner) In A^{∗}, the interval [v, w] is lexicographically shellable for all v, w. And

rk H̃_{i}(Δ(v, w)) = \{ \begin{matrix}\binom{w}{v}n & if i = |w| − |v| − 2, \\ 0 & else. \end{matrix}

In 𝔏, [p, q] is not always shellable. But Forman developed a discrete analogue of Morse Theory to compute the homology of any CW-complex by collapsing it onto a subcomplex of critical cells. Babson & Hersh showed how any lexicographic ordering of the maximal chains of an interval gives rise to the critical cells of a Morse function.

Conjecture 5 In L there is a Morse function for [p, q] with a single critical cell of dimension d(ϵ_{p}) for each normal embedding ϵ_{p} of p in q.

B. Embedding orders. Let P be any poset. Take 0 ∉ P and set 0 < x for all x ∈ P. Partially order P^{∗} by p ≤ q in P^{∗} iff there is an expansion ϵ_{p} of length |q| with

ϵ_{p}(i) ≤ q(i) for all 1 ≤ i ≤ |q| .

Call this the embedding order on P^{∗}.

Call P a rooted forest if each component of the Hasse diagram of P is a tree with a unique minimal element. Then there is a notion of normal embedding in P^{∗} where minimal elements play the role of q(i) = 1, nonminimal elements play the role of q(i) > 1, and the element adjacent to q(i) on then unique q(i)-root path plays the role of q(i) − 1.

Conjecture 6 Let P be a rooted forest. Then in P^{∗} we have

μ(p, q) = _{ϵ_{p}}^{∑}(−1)^{d(ϵ_{p})}

summed over all normal embeddings ϵ_{p} of p in q.

Note that if this conjecture is true then the theorems for A^{∗} or 𝔏 are the special cases where P is an antichain or a chain, respectively.

C. Other orders. Let 𝔖 be the set of all permutations ordered by pattern containment. What is μ(p, q) for p, q ∈ 𝔖?

What about P^{∗} for any poset P (not just rooted forests)? The simplest such poset is

[figure: a; b; c; Λ =]

Let a^{j} denote the word in Λ^{∗} consisting of j copies of a and similarly for the other elements of Λ. Let T_{n}(x) denote the nth Chebyshev polynomial of the first kind.

Conjecture 7 If j, k ≥ 0 then μ(a^{j}, c^{k}) is the coefficient of x^{k−j} in T_{k+j} (x).