Graph Coloring and Symmetric Functions in Noncommuting

Variables

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 sagan@math.msu.edu www.math.msu.edu/~sagan

0. History

1. Chromatic Polynomials

2. Stanley’s Symmetric Function

3. Noncommuting Variables

4. Basis Change à la Doubilet

5. MacMahon and Schur Symmetric Functions 0. History

1932  H. Whitney
1936  M. C. Wolf
1969  G M. Bergman & P. M. Cohn
1981  M.-P. Schützenberger

& A. Lascoux

1994 & 1995  R. P. Stanley
1995  I. M. Gelfand, D. Krob,

A. Lascoux, B. Leclerc, V. Retakh, & J.-I. Thibon

1998  S. Fomin & C. Greene
2000 & 2001  D. Gebhard & BES
2002  M. Rosas & BES

1. Chromatic Polynomials

Let G = (V, E) be a graph with vertices V and edges E. Loops and multiedges are permitted. A proper coloring of G is c : V → {1, 2, …, n} such that

uv ∈ E ⇒ c(u) ≠ c(v).

The chromatic polynomial of G is

P (G) = P (G, n) := # of proper c : V → {1, 2, …, n}.

Ex. The path P_{3}.

[figure: P_{3} =; w; v; u]

P (G, n) = (# of ways to color u )

·(# of ways to then color v ) ·(# of ways to then color w )

= n(n − 1)(n − 1)
= n^{3} − 2n^{2} + n.

1a. Deletion/Contraction If e ∈ E then let

G \ e = G with e deleted,
G/e = G with e contracted to a point.

Ex. Deletion and contraction in a specific graph.

[figure: G =; e; G \ e =; G/e =]

Lemma 1 (Deletion-Contraction) If e ∈ E then

P (G) = P (G \ e) − P (G/e).

Proof If e = uv then

P (G \ e) = (# of colorings with c(u) ≠ c(v)  )

+(# of colorings with c(u) = c(v) )

= P (G) + P (G/e).

1b. Whitney’s Theorem If F ⊆ E then let F also stand for the subgraph of G with vertices V and edges F. Ex. The two meanings of F.

[figure: G =; e; f; g; h; F = {f, h} =; f; h]

Theorem 2 (Whitney, 1932) We have

P (G) = _{F ⊆E}^{∑}(−1)^{|F |} n^{k(F)}

where |F | is the cardinality of F, and k(F) is the number of connected components of F. Ex. The path P_{3}.

[figure: F; :]
∑(−1)^{|F |} n^{k(F)} = n^{3} − n^{2} − n^{2} + n
= n^{3} − 2n^{2} + n.

2. Stanley’s Symmetric Function Let V = {v_{1}, …, v_{d}} and let x = {x_{1}, x_{2}, …} be a set of commuting variables. Define

X(G) = X(G, x) := ∑ x_{c(v_{1})}x_{c(v_{2})} ⋯ x_{c(v_{d})} where the sum is over all proper c : V → {1, 2, …}. Ex. The path P_{3}.

\underbrace{6}  \underbrace{6}
[figure: c; :; 1; 2; 1; 2; 1; 2; ⋯; 3; 2; 1; ⋯; 1; 2; 3; 4; 2; 1; ⋯; 1; 2; 4; ⋯]
X(G) = x_{1}^{2}x_{2} + x_{1}x_{2}^{2} + ⋯ + 6x_{1}x_{2}x_{3} + 6x_{1}x_{2}x_{4} + ⋯

Notes.

1. Suppose that we let x_{1} = x_{2} = ⋯ = x_{n} = 1 and

x_{i} = 0 for i > n, denoted x = 1^{n}, then

X(G, 1^{n}) = ∑ ; c proper^{c:V →{1,2,...,n}} 1 = P (G, n).

2. X(G, x) is a symmetric function.

2a. Symmetric Functions

Let S_{m} be the symmeteric group on {1, 2, …, m} and let ℚ[[x]] denote the algebra of formal power series in x over ℚ. Now g ∈ S_{m} acts of f(x) ∈ ℚ[[x]] by

gf(x_{1}, x_{2}, …) = f(x_{g1}, x_{g2}, …)

where gi = i for i > m. Then f is symmetric if

gf = f for all g ∈ S_{m} and all m ≥ 1.

An integer partition of d, λ ⊢ d, is a weakly decreasing sequence of positive integers λ = (λ_{1}, λ_{2}, …, λ_{k}) such that ∑_{i} λ_{i} = d. The associated monomial symmetric function is

m_{λ} = sum of all monomials with exponent λ .

Ex. If λ = (3, 3, 1) then

m_{(3,3,1)} = x_{1}^{3}x_{2}^{3}x_{3} + x_{1}^{3}x_{2}x_{3}^{3} + x_{1}x_{2}^{3}x_{3}^{3} + x_{1}^{3}x_{2}^{3}x_{4} + ⋯

The algebra of symmetric functions is

Λ = Λ(x) = span {m_{λ} : all λ}.

Another basis for Λ consists of the power sum symmetric functions, p_{λ}, defined as follows:

p_{d} = x_{1}^{d} + x_{2}^{d} + x_{3}^{d} + ⋯  for d a positive integer,
p_{λ} = p_{λ_{1}}p_{λ_{2}} ⋯ p_{λ_{k}}  for λ = (λ_{1}, λ_{2}, …, λ_{k}).

\begin{aligned}Ex. & p_{(3,3,1)} & = & p_{3} p_{3} p_{1} \\ & & = & (x_{1}^{3} + x_{2}^{3} + ⋯)^{2}(x_{1} + x_{2} + ⋯). \end{aligned}

Theorem 3 (Stanley, 1995) We have

X(G) = _{F ⊆E}^{∑}(−1)^{|F |} p_{λ(F)}

where λ(F) = (λ_{1}, λ_{2}, …, λ_{k}), λ_{i} being the number of vertices in the ith component of F.

Ex. If G = P_{3} then

∑(−1)^{|F |} p_{λ(F)} = p_{(1,1,1)} − p_{(2,1)} − p_{(2,1)} + p_{(3)}^{[figure: F; :]}

Stanley implies Whitney: Substituting x = 1^{n}

p_{d}(1^{n}) = \overbrace{1 + 1 + ⋯ + 1}^{n} = n and
p_{λ}(1^{n}) = \overbrace{n · n ⋯ n}^{k(F)} = n^{k(F)}.

3. Noncommuting Variables Let x_{1}, x_{2}, … be noncommuting and let ℚ⟨⟨x⟩⟩ be the corresponding ring of formal power series. Fix a total order v_{1}, v_{2}, …, v_{d} on V and define

Y (G) = Y (G, x) := ∑ x_{c(v_{1})}x_{c(v_{2})} ⋯ x_{c(v_{d})} where the sum is over all proper c : V → {1, 2, …}. Define an operation of induction, ↑, by

x_{i_{1}}x_{i_{2}} ⋯ x_{i_{d}} ↑ = x_{i_{1}}x_{i_{2}} ⋯ x_{i_{d}}x_{i_{d}}

and linear extension to ℚ⟨⟨x⟩⟩. Ex. x_{2}^{3}x_{1}x_{3}^{2} ↑ = x_{2}^{3}x_{1}x_{3}^{3}. Lemma 4 (Gebhard-S, 2000) If v_{d−1}v_{d} ∈ E then

Y (G) = Y (G \ e) − Y (G/e) ↑ .

3a. Symmetric Functions in Noncommuting Variables

The action of S_{m} on ℚ⟨⟨x⟩⟩ is the same as on ℚ[[x]]. The symmetric functions in noncommuting variables have bases indexed by partitions of [d] := {1, 2, …}.

A set partition of [d], π ⊢ [d], is a collection of sets π = B_{1}/B_{2}/ … /B_{k} such that ⊎_{i}B_{i} = [d]. The B_{i} are called the blocks of the set partition. The type of π is the integer partition

λ(π) = (|B_{1}|, |B_{2}|, …, |B_{k}|).

Ex. π = 143/268/57 ⊢ [8] is of type λ(π) = (3, 3, 2).

The associated monomial symmetric function is

m_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{d}} where
i_{j} = i_{k} iff j, k are in the same block of π.

Ex. m_{13/2} = x_{1}x_{2}x_{1} + x_{2}x_{1}x_{2} + x_{1}x_{3}x_{1} + · · · .

The algebra of symmetric functions in noncommuting variables is

Π = Π(x) = span {m_{π} : all π}.

The power sum symmetric function basis for Π(x) is

p_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{d}} where
i_{j} = i_{k} if j, k are in the same block of π.

Ex. p_{13/2} = m_{13/2} + x_{1}^{3} + x_{2}^{3} + · · · .

An integer partition λ = (λ_{1}, λ_{2}, …, λ_{k}) ⊢ d can be written

λ = (1^{m_{1}}, 2^{m_{2}}, …, d^{m_{d}})

where m_{i} is the multiplicity of i in λ. Define

λ! = λ_{1}!λ_{2}! ⋯ λ_{k}!
λ^{!} = m_{1}!m_{2}! ⋯ m_{d}!

Let ρ : ℚ⟨⟨x⟩⟩ → ℚ[[x]] be the forgetful map.

ρ(m_{π}) = λ(π)^{!}m_{λ(π)} and ρ(p_{π}) = p_{λ(π)}.

Theorem 5 (Gebhard-S, 2000) If V = [d] then

Y (G) = _{F ⊆E}^{∑}(−1)^{|F |} p_{π(F)}

where π(F) = B_{1}/B_{2}/ … /B_{k}, B_{i} being the vertices in the ith component of F.

3b. The (3+1)-Free Conjecture

Let C_{n} denote a totally ordered set on n elements. A poset (partially ordered set) P is (n+m)-free if it contains no induced subposet isomorphic to C_{n}⊎C_{m}. The incomparability graph of a poset P is G_{P} where V = P with an edge from u to v if u and v are not related in P. Let {e_{λ} : all λ} be the elementary symmetric function basis for Λ.

Conjecture 6 (Stanley and Stembridge, 1993) If P is (3+1)-free and X(G_{P}) = ∑_{λ} c_{λ}e_{λ} then c_{λ} ≥ 0 for all λ. (We say that X(G_{P}) is e-positive.)

The indifference graphs are the G_{P} where P is both (3 + 1)-free and (2 + 2)-free. They can also be characterized as follows. Let I = (I_{1}, I_{2}, …, I_{k}) be a sequence of intervals I_{j} ⊆ [d]. The corresponding indifference graph, G_{I}, has vertex set V = [d] with a complete graph on the vertices of I_{j} for each j. WLOG, there is no containment among the I_{j} and they are listed in order of increasing left endpoint.

Theorem 7 (Gebhard and S, 2000) If we have |I_{j} ∩ I_{j+1} | ≤ 1 for all j, then X(G_{I}) is e-positive.

4. Basis Change à la Doubilet

A basis b_{λ} for Λ(x) is multiplicative if it’s defined by

1. defining b_{d} for positive integers d,

2. defining b_{λ} = b_{λ_{1}}b_{λ_{2}} ⋯ b_{λ_{k}} for λ = (λ_{1}, λ_{2}, …, λ_{k}). The following bases are multiplicative: the power sum symmetric functions

p_{d} = x_{1}^{d} + x_{2}^{d} + ⋯,

the elementary symmetric functions e_{d} = sum of all square-free monomials of degree d , the complete homogeneous symmetric functions

h_{d} = sum of all monomials of degree d , Ex. We have

p_{(3,3,1)} = (x_{1}^{3} + x_{2}^{3} + ⋯)^{2}(x_{1} + x_{2} + ⋯)
e_{(3,3,1)} = (x_{1}x_{2}x_{3} + x_{1}x_{2}x_{4} + ⋯)^{2}(x_{1} + x_{2} + ⋯)
h_{(3,3,1)} = (x_{1}^{3} + x_{1}^{2}x_{2} + x_{1}x_{2}x_{3} + ⋯)^{2}(x_{1} + x_{2} + ⋯)

Note that the monomial symmetric fuctions

m_{λ} = sum of all monomials with exponent λ do not form a multiplicative basis.

In Π(x) we have corresponding bases

p_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{d}} where

i_{j} = i_{k} if j, k are in the same block of π,

and

e_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{d}} where

i_{j} ≠ i_{k} if j, k are in the same block of π.

Recall also

m_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{d}} where

i_{j} = i_{k} iff j, k are in the same block of π.

Ex. We have

m_{13/2} = x_{1}x_{2}x_{1} + x_{2}x_{1}x_{2} + x_{1}x_{3}x_{1} + ⋯,
p_{13/2} = x_{1}x_{2}x_{1} + x_{2}x_{1}x_{2} + ⋯ + x_{1}^{3} + x_{2}^{3} + ⋯
= m_{13/2} + m_{123} ,
e_{13/2} = x_{1}x_{1}x_{2} + ⋯ + x_{1}x_{2}x_{2} + ⋯ + x_{1}x_{3}x_{2} + ⋯
= m_{12/3} + m_{1/23} + m_{1/2/3} .

If ρ : ℚ⟨⟨x⟩⟩ → ℚ[[x]] is the forgetful map.

\begin{aligned}ρ(m_{π}) & = & λ(π)^{!}m_{λ(π)} \\ ρ(p_{π}) & = & p_{λ(π)} \\ ρ(e_{π}) & = & λ(π)!e_{λ(π)}. \end{aligned}

4a. The Partition Lattice and Möbius Inversion

Let Π_{d} be the poset of all π ⊢ [d] ordered by refinement, i.e., if π = B_{1}/ … /B_{k} and σ = C_{1}/ … /C_{l} then π ≤ σ if each B_{i} is contained in some C_{j}.

Ex. We have

[figure: Π_{3} =; 1/2/3; 12/3; 13/2; 1/23; 123]

Π_{d} is a lattice, meaning every pair π, σ ∈ Π_{d} has

π ∧ σ = greatest lower bound or meet of π and σ  ,
π ∨ σ = least upper bound or join of π and σ .

So Π_{d} has a unique minimal element ˆ0 = 1/2/ … /d. Immediately from the definitions

p_{π} = _{σ≥π}^{∑} m_{σ} and e_{π} = _{σ∧π=ˆ0}^{∑} m_{σ}.

To invert these sums, define the Möbius function of a finite poset P to be μ : P × P → ℤ such that

μ(a, b) = \{ \begin{matrix}1 & if a = b, \\ − _{a≤c<b}^{∑} μ(a, c) & else. \end{matrix}

Ex.

[figure: μ(ˆ0, π) :; 1/2/3; 12/3; 13/2; 1/23; 123]

In general, μ(ˆ0, B_{1}/ … /B_{k}) = _{i}^{∏}(−1)^{|B_{i}|−1}(|B_{i}|−1)!

Theorem 8 (Möbius Inversion, Rota, 1964) Let P be a finite poset and G be an additive group. If f, g : P → G then

f(a) = _{b≥a}^{∑} g(b) for all a ∈ P

iff g(a) = _{b≥a}^{∑} μ(a, b)f(b) for all a ∈ P.

Corollary 9 (Doubilet, 1972) We have

m_{π} = _{σ≥π}^{∑} μ(π, σ)p_{σ}, m_{π} = _{σ≥π}^{∑} \frac{μ(π, σ)}{μ(ˆ0, σ)} _{τ≤σ}^{∑} μ(τ, σ)e_{τ}.

What about h_{π}? A function f : D → R has kernal ker f ⊢ D whose blocks are the nonempty sets among the f^{−1}(r) for r ∈ R. Also, f : [d] → x has associated monomial

M_{f} = f(1)f(2) ⋯ f(d).

Then

m_{π} = _{ker f=π}^{∑} M_{f}.

Ex. If π = 13/2 then

\begin{aligned}f & : & \begin{matrix}f(13) = x_{1}, \\ f(2) = x_{2} \end{matrix} & & \begin{matrix}f(13) = x_{2}, \\ f(2) = x_{1} \end{matrix} & & … \\ ∑ M_{f} & = & x_{1}x_{2}x_{1} & + & x_{2}x_{1}x_{2} & + & ⋯ \end{aligned}

Define

h_{π} = _{(f,L)}^{∑} M_{f}

where f : [d] → x and L is a linear ordering of the elements of each block of ker f ∧ π. Then

ρ(h_{π}) = λ(π)!h_{λ(π)}.

Ex. If π = 13/2 then

\begin{aligned}(f, L) & : & \begin{matrix}f(13) = x_{1}, \\ f(2) = x_{1} \end{matrix} & & \begin{matrix}f(31) = x_{1}, \\ f(2) = x_{1} \end{matrix} & & … \\ ∑ M_{f} & = & x_{1}^{3} & + & x_{1}^{3} & + & ⋯ \end{aligned}

5. MacMahon and Schur Symmetric Functions

Consider the d sets of variables x′ = {x′_{1}, x′_{2}, …}, x′′ = {x′′_{1}, x′′_{2}, …}, …, x^{(d)} = {x_{1}^{(d)}, x_{2}^{(d)}, …}. Let g ∈ S_{m} act on f(x′, x′′, …, x^{(d)}) ∈ ℚ[[x′, x′′, …, x^{(d)}]] diagonally:

gf(x′_{1}, x′′_{1}, …, x′_{2}, x′′_{2}, …) = f(x′_{g1}, x′′_{g1}, …, x′_{g2}, x′′_{g2}, …).

The monomial

x_{1}^{′a_{1}}x_{1}^{′′b_{1}} ⋯ x_{1}^{(d)c_{1}} x_{2}^{′a_{2}}x_{2}^{′′b_{2}} ⋯ x_{2}^{(d)c_{2}} ⋯

has multiexponent

\begin{aligned}λ⃗ & = & \{λ^{1}, λ^{2}, …\} \\ & := & \{(a_{1}, b_{1}, …, c_{1}), (a_{2}, b_{2}, …, c_{2}), …\} \end{aligned}

as well as multidegree

\begin{aligned}n⃗ & = & (n_{1}, n_{2}, …, n_{d}) \\ & := & (a_{1}, b_{1}, …, c_{1}) + (a_{2}, b_{2}, …, c_{2}) + ⋯ \end{aligned}

and we write λ⃗ ⊢ n⃗. The associated monomial MacMahon symmetric function is

mλ⃗ = sum of all monomials with multiexponent λ⃗ .

Ex. m_{{(2,1),(3,0)}} = x_{1}^{′2}x′′_{1}x_{2}^{′3} + x_{1}^{′3}x_{2}^{′2}x′′_{2} + ⋯

The algebra of MacMahon symmetric functions is

M = M(x′, x′′, …, x^{(d)}) = span {mλ⃗ : all λ⃗}.

Consider

M_{(1^{d})} = span \{mλ⃗ : all λ⃗ ⊢ (\overbrace{1, 1, …, 1}^{d}) \}.

Now there exists an isomorphism of vector spaces ϕ : _{d≥0}^{⨁} M_{(1^{d})} → Π given by

x′_{i}x′′_{j} ⋯ x_{k}^{(d)} ↦ x_{i}x_{j} ⋯ x_{k}

and linear extension. Also, under this isomorphism mλ⃗ ↦ m_{π} where λ_{i} is the characteristic vector of B_{i}.

Ex. m_{{(1,0,1,1,0),(0,1,0,0,1)}} ↦ m_{134/25} .

Notes 1. This is not an isomorphism of algebras as _{d≥0}^{⨁} M_{(1^{d})} is commutative.

2. The multiplicative bases of Λ have analogs in M. For example, hλ⃗ = h_{{λ^{1}}}h_{{λ^{2}}} ⋯ where h_{{(n_{1},n_{2},...,n_{d})}} has the generating function

\begin{matrix}_{n_{1},n_{2},...,n_{d}≥0}^{∑} h_{\{(n_{1},n_{2},...,n_{d})\}}r^{n_{1}}s^{n_{2}} ⋯ t^{n_{d}} \\ = _{i≥1}^{∏} \frac{1}{1 − x′_{i}r − x′′_{i}s − ⋯ − x_{i}^{(d)} t}. \end{matrix}

5a. Schur Functions

A partition λ = (λ_{1}, λ_{2}, …, λ_{k}) has a shape, also denoted λ, consisting of k left-justified rows with λ_{i} dots in row i.

Ex. Partition λ = (3, 3, 2, 1) has Ferrers diagram

λ = \begin{matrix}• & • & • \\ • & • & • \\ • & • \\ • \end{matrix} .

A (semistandard) Young tableau T of shape λ, written λ(T) = λ, is obtained by replacing each dot of the shape of λ with a positive integer so that rows weakly increase and columns strictly increase.

Ex. A Young tableau of shape (3, 3, 2, 1) is

T = 1 1 3 2 2 5 3 6 5 .

The Schur function, s_{λ}, is

s_{λ} = _{λ(T)=λ}^{∑} M_{T} where M_{T} = _{i∈T}^{∏} x_{i}.

Ex. if λ = (2, 1) then

\begin{aligned}T & : & 1 1 2 & , & 1 2 2 & , & … & , & 1 2 3 & , & 1 3 2 & , & … \\ s_{(2,1)} & = & x_{1}^{2}x_{2} & + & x_{1}x_{2}^{2} & + & ⋯ & + & x_{1}x_{2}x_{3} & + & x_{1}x_{2}x_{3} & + & ⋯ \end{aligned}

If λ, n⃗ ⊢ d then a primed Young tableau T′ of shape λ and multidegree n⃗ is obtained from T by putting primes on n_{1} elements of T, double primes on n_{2} elements of T, etc. The corresponding MacMahon Schur function is

Sn⃗ ; λ = _{λ(T′)=λ}^{∑} M_{T′} where M_{T′} = _{i^{(j)}∈T}^{∏} x_{i}^{(j)} .

Ex. if λ = (2, 1) and μ = (1, 1, 1) then

\begin{aligned}T & : & \begin{matrix}1′ & 1′′ \\ 2′′′ \end{matrix} & , & \begin{matrix}1′′ & 1′ \\ 2′′′ \end{matrix} & , & … & , & \begin{matrix}1′′′ & 1′′ \\ 2′ \end{matrix} & , & … \\ S_{(2,1)}^{(1,1,1)} & = & x′_{1}x′′_{1}x′′′_{2} & + & x′_{1}x′′_{1}x′′′_{2} & + & ⋯ & + & x′′_{1}x′′′_{1}x′_{2} & + & ⋯ \end{aligned}

The MacMahon Schur functions have many of the same properties as do the regular Schur functions.

Theorem 10 (Jacobi-Trudi Determinant) For the partition λ = (λ_{1}, λ_{2}, …, λ_{k}), we have

s_{λ} = |h_{λ_{i}−i+j} |.

Define m⃗ ≤ n⃗ to be the componentwise partial order on vectors of length d.

Theorem 11 (Rosas-S,2001) Given two partitions λ, n⃗ ⊢ d, we have

Sn⃗ ; λ = | ∑_{{m⃗≤n⃗ \atop m⃗⊢λi−i+j}} hm⃗|

with the convention that if the product of two monomials does not have multidegree n⃗ then that product is zero.