Monomial Bases for NBC Complexes

Jason I. Brown Department of Mathematics and Statistics Dalhousie University Halifax, NS B3H 3J5, CANADA

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

1. Complexes and chromatic polynomials

2. NBC complexes

3. Stanley-Reisner rings and hsop’s

4. Monomial ideals

5. Comments 1. Complexes and chromatic polynomials

Let Δ be a simplicial complex on a finite set E, so Δ is a family of subsets of E satisfying

S ∈ Δ and T ⊆ S implies T ∈ Δ.

The S ∈ Δ are called faces. We assume Δ is pure of rank r meaning that |S| = r for all maximal faces S ∈ Δ. For 0 ≤ i ≤ r, let

f_{i} = f_{i}(Δ) = # of faces S ∈ Δ with |S| = i .

The f-polynomial of Δ is

f(x) = f_{0} + f_{1}x + f_{2}x^{2} + ⋯ + f_{r}x^{r}.

The h-polynomial of Δ is

h(x) = (1 − x)^{r}f (\frac{x}{1 − x} )
= f_{0}(1 − x)^{r} + f_{1}x(1 − x)^{r−1} + ⋯ + f_{r}x^{r}.

and let

h_{i} = h_{i}(Δ) = coefficient of x^{i} in h(x).

Let G = (V, E) be a graph with |V | = p and |E| = q. A proper coloring of G is c : V → {1, 2, …, λ} such that

vw ∈ E implies c(v) ≠ c(w).

The chromatic polynomial of G is

P (G) = P (G; λ) = # of such proper colorings.

Example. Let

[figure: G =; t; w; u; v]
P (G) = # ways to color t, then u, then v, then w
= λ(λ − 1)(λ − 2)(λ − 2)
= λ^{4} − 5λ^{3} + 8λ^{2} − 4λ.

Proposition 1 Let K_{p} be the edgeless graph and let T be a tree on p vertices. Then

P (K_{p}; λ) = λ^{p} and P (T; λ) = λ(λ − 1)^{p−1}.

Let G be a graph and e ∈ E. Let

G \ e = G with e deleted,
G/e = G with e contracted.

Example. Let

[figure: G =; w; v; e]

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

Theorem 2 (Deletion-Contraction) For e ∈ E

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

Proof. If e = vw then

P (G \ e) = (# proper c for G \ e s.t. c(v) ≠ c(w))

+(# proper c for G \ e s.t. c(v) = c(w))

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

Corollary 3 For any graph G:

1. P (G; λ) is a monic polynomial in λ.

2. deg P (G; λ) = p = |V |.

3. Coefficients of P (G; λ) alternate in sign.

2. NBC complexes

Define coefficients f_{i} by

P (G; λ) = f_{0}λ^{p} − f_{1}λ^{p−1} + ⋯

and coefficients h_{i} by

P (G; λ) = h_{0}λ(λ − 1)^{p−1} − h_{1}λ(λ − 1)^{p−2} + · · · .

Let

C = C(G) = set of cycles/circuits of G.

Let G be ordered meaning that E has been given a total order e_{1} < e_{2} < … < e_{q}. Then each C ∈ C has broken circuit

C = C − min C.

The NBC complex of G is

Δ = Δ(G) = {S ⊆ E : S contains no C }.

Then Δ(G) is a pure simplicial complex.

Theorem 4 Let P (G; λ) have coefficients f_{i} and h_{i} as defined above. Then for 0 ≤ i ≤ p

f_{i} = f_{i}(Δ(G)) and h_{i} = h_{i}(Δ(G)).

[figure: G =; 5; 1; 2; 3; 4; C(G) =; 5; 2; 3; 1; 3; 4; 5; 1; 2; 4]

C̄(G) = {35, 34, 245}
Δ(G) = {∅} ∪ {1, 2, 3, 4, 5}

∪{12, 13, 14, 15, 23, 24, 25, 45}

∪{123, 124, 125, 145}
(f_{i}(Δ)) = (1, 5, 8, 4, 0).

P (G; λ) = λ(λ − 1)(λ − 2)^{2} = λ^{4} − 5λ^{3} + 8λ^{2} − 4λ.

P ([figure]; λ) = P ([figure]; λ) − P ( [figure]; λ)

= P ([figure]; λ) − P ([figure]; λ) − P ([figure]; λ) + P ( [figure] ; λ)

= λ(λ − 1)^{3} − λ(λ − 1)^{2} − λ(λ − 1)^{2} + λ(λ − 1)

= λ(λ − 1)^{3} − 2λ(λ − 1)^{2} + λ(λ − 1)

(h_{i}(Δ)) = (1, 2, 1, 0, 0)

3. Stanley-Reisner rings and hsop’s

Let F [x] be the polynomial ring over field F with variables x = {x_{1}, …, x_{q}}. If E = {e_{1}, …, e_{q}} then S ⊆ E has monomial

x^{S} = _{e_{i}∈S}^{∏} x_{i}.

Simplicial complex Δ has Stanley-Reisner ring

F (Δ) = F [x]/(x^{S} : S ∉ Δ).

In particular, for an ordered graph G we let

F (G) = F (Δ(G)) = F [x]/(x^{C} : C ∈ C(G)).

Now F (G) has a homogeneous system of parameters (hsop) of degree one θ_{1}, …, θ_{t}, i.e.,

1. θ_{i} is linear without constant term for all i,

2. θ_{1}, …, θ_{t} are algebraically independent,

3. F (G)/(θ_{1}, …, θ_{t}) is finite dim. over F.

Brown gave an explicit hsop for F (G). WLOG G is connected and let T be a spanning tree of G. If e ∈ E(T) then e has fundamental disconnecting set

D_{e} = D_{e}(G) = {f ∈ E(G) : T − e + f connected }

and hsop element (when F = ℤ_{2})

θ_{e} = _{e_{i}∈D_{e}}^{∑} x_{i}.

Example

[figure: G =; 1; 2; 3; 4; 5; 6; 7; T =; 3; 4; 5; 6; 7] C(G) = {13467, 2345, 12567}
ℤ_{2}(G) = ℤ_{2}[x_{1}, …, x_{7}]/(x_{3}x_{4}x_{6}x_{7}, x_{3}x_{4}x_{5}, x_{2}x_{5}x_{6}x_{7})

[figure: 1; 2; 3; 4; 5; 6; 7; θ_{3} = x_{3} + x_{1} + x_{2}; 1; 2; 3; 4; 5; 6; 7; θ_{4} = x_{4} + x_{1} + x_{2}; 2; 3; 4; 5; 6; 7; θ_{5} = x_{5} + x_{2}; 1; 3; 4; 5; 6; 7; θ_{6} = x_{6} + x_{1}; 1; 3; 4; 5; 6; 7; θ_{7} = x_{7} + x_{1}]

4. Monomial ideals

If F (Δ) has an hsop θ_{1}, …, θ_{t} we let

R(Δ) = F (Δ)/(θ_{1}, …, θ_{t}).

Consider

Mon (k) = set of monomials in F [x_{1}, …, x_{k}].

A subset L ⊆ Mon (k) is a lower order ideal if

m ∈ L and n|m imples n ∈ L .

The lower order ideal generated by S ⊆ Mon (k) is

L(S) = {m ∈ Mon (k) : m|n for some n ∈ S }.

Upper ideal and U(S) are defined dually.

Theorem 5 (Macaulay, Stanley) Suppose Δ is a simplicial complex and that the ring F (Δ) is Cohen-Macaulay. Then R(Δ) has a basis, L, which is a lower order ideal of monomials and

h_{i}(Δ) = # of monomials of total degree i in L.

For a graph G, F (G) is Cohen-Macaulay. We have a conjectured construction of a basis for R(G).

An ordering e_{1} < … < e_{q} is standard if the last p−1 edges form a tree. Let k = |E(G) − E(T)|. We can pick the monomial basis for R(G) inside Mon (k) since Brown’s θ_{i} can be used to eliminate the other variables, replacing each x^{C} by a polynomial p_{C}.

Example. In our running example, k = 2 and

\begin{matrix}ℤ_{2}(G) = ℤ_{2}[x_{1}, …, x_{7}]/(x_{3}x_{4}x_{6}x_{7}, x_{3}x_{4}x_{5}, x_{2}x_{5}x_{6}x_{7}). \\ θ_{3} = x_{3} + x_{1} + x_{2}, θ_{4} = x_{4} + x_{1} + x_{2}, θ_{5} = x_{5} + x_{2}. \end{matrix}

So, picking one of the broken circuit monomials

x^{C} = x_{3}x_{4}x_{5} becomes p_{C} = (x_{1} + x_{2})^{2}x_{2}.

For 1 ≤ i ≤ k, the graph T + e_{i} has a unique fundamental circuit C_{i}.

Conjecture 6 Let G be connected. Then there is a standard ordering of E such that R(G) has basis

L(G) = Mon (k) − U(m_{C} : C ∈ C(G))

where

m_{C} = \{ \begin{matrix}x_{i}^{#C_{i}} & if C = C_{i} fundamental, \\ min p_{C} & else. \end{matrix}

Here min p picks out the lexicographically smallest monomial in p.

[figure: G =; 1; 2; 3; 4; 5; 6; 7; T =; 3; 4; 5; 6; 7]

Fundamental cycles:

[figure: 1; 3; 4; 5; 6; 7; C_{1} = {1, 3, 4, 6, 7}; m_{C_{1}} = x_{1}^{4}; 2; 3; 4; 5; 6; 7; C_{2} = {2, 3, 4, 5}; m_{C_{2}} = x_{2}^{3}]

Nonfundamental cycle:

[figure: 1; 2; 3; 4; 5; 6; 7] \begin{aligned}C_{3} & = & \{1, 2, 5, 6, 7\} \\ x^{C^{3}} & = & x_{2}x_{5}x_{6}x_{7} \\ p_{C_{3}} & = & x_{2}x_{2}x_{1}x_{1} \end{aligned}  m_{C_{3}} = x_{1}^{2}x_{2}^{2}

So R(G) has basis L(G) = Mon (2) − U(x_{1}^{4}, x_{2}^{3}, x_{1}^{2}x_{2}^{2}).

5. Comments

A graph with a standard ordering satisfying the conjecture is said to have a broken circuit basis.

a. (Generalized) theta graphs and phi graphs have broken circuit bases.

b. By only considering the fundamental circuits:

Proposition 7 If G has a broken circuit basis and c_{i} = |C_{i}| for 1 ≤ i ≤ k, then R(G) is spanned by

L (_{1≤i≤k}^{∏} x_{i}^{c_{i}−2} ) .

Stanley showed that the number of acyclic orientations of G is given by P (G; −1). So one can use this proposition to estimate their number.

c. The results we have about broken circuit bases are proved by deletion/contraction. It is hoped that together with the ear decomposition of a block we will be able to prove the full conjecture.

d. The conjecture may even be true for representable matroids.