Tractable Partially Ordered Sets Derived from Root Systems and Biased Graphs

by

Phil Hanlon^{∗} University of Michigan Ann Arbor, Michigan 48109-1003

Thomas Zaslavsky^{†} Binghamton University Binghamton, New York 13902-6000

October 1993 Revised February 1997

∗ Partially supported by the NSF, the NSA, and the Cray Research Foundation.

† Supported by SGPNR grant 9109BCW747 and NSF grant DMS-9200472.

Abstract

We study new posets Q obtained by removing from a geometric lattice L of a biased graph certain flats indexed by a simplicial complex C. (One example of L is the lattice of flats of the vector matroid of a root system B_{n}.) We study the structure and compute the characteristic polynomial of Q. With certain choices of L and C, including ones for which Q is a lattice interpolating between those of B_{n} and D_{n}, we observe curious relationships among the roots of the characteristic polynomials of Q, L, and C.

1. Introduction

We introduce a new kind of finite partially ordered set, derived from a certain type of geometric lattice via an indexing simplicial complex, whose Möbius function satisfies a simple reduction formula that in examples with high symmetry leads to exact evaluations.

Our posets originated in an attempt to understand the relationship between the exponents of the root systems B_{n} and D_{n} in ℝ^{n}. These root systems are defined by D_{n} = {±u_{i} ± u_{j} : 1 ≤ i < j ≤ n} and B_{n} = D_{n} ∪ {±u_{i} : i ∈ [n]}, where u_{i} is the i^{th} unit coordinate vector and [n] = {1, 2, …, n}. Associated to each root system R of rank n there are n positive integers called its exponents. There are many ways to define them, some very combinatorial and some very algebraic. Best for our purposes is a definition in terms of Lat R, the lattice of flats spanned by subsets of R. The exponents of R are the roots of the characteristic polynomial of Lat R. (Those who are unfamiliar with this definition of exponents should see [9, 13] for a proof that it is equivalent to more familiar definitions.) One can check that the exponents of B_{n} and D_{n} are given by these lists:

\begin{matrix}B_{n} : & 1, 3, 5, ⋯, 2n − 3, 2n − 1; \\ D_{n} : & 1, 3, 5, ⋯, 2n − 3, n − 1. \end{matrix}

We see that removal of all the basis vectors ±u_{i} from B_{n} changes only the last exponent and changes that exponent by n. The original motivation for this work was a desire to understand why this should be so. Given our definition of exponents, we must understand why only one root of the characteristic polynomial of Lat B_{n} changes when the lines generated by the u_{i} are removed.

We will consider a more general situation in which certain flats, indexed by an abstract simplicial complex, are removed from Lat B_{n} or more generally from matroids called “bias matroids of full biased graphs”. Our results concern the characteristic polynomials of the partially ordered sets obtained in that way and, for certain matroids and indexing complexes, the behavior of their roots.

An example will give the flavor of our results. Let F be a field and ζ_{M} a primitive M^{th} root of unity in F, where M ≥ 1. Define

D_{n}(M) = {ζ_{M}^{k}u_{i} − ζ_{M}^{l}u_{j} : i, j ∈ [n], i ≠ j, k, l ∈ ℤ} ⊆ F^{n}

and

B_{n}(M) = D_{n}(M) ∪ {ζ_{M}^{k}u_{i} : i ∈ [n], k ∈ ℤ}.

For R ⊆ F^{n} let Lat R be the lattice of all flats generated by subsets of R. (Then Lat B_{n}(M) is the Dowling lattice of the cyclic group ℤ_{M}.) If t is a subspace of F^{n} define V_{0}(t) = {i ∈ [n] : u_{i} ∈ t}. For n, M ≥ 0 we call the falling factorial with step M the polynomial

(y)_{n,M} = y(y − M) ⋯ (y − (n − 1)M), with (y)_{0,M} = 1.

Now, let C be an abstract simplicial complex on vertex set [n], containing ∅ but (to keep the theorem simple) not [n], and set N_{i}(C) = #{X ∈ C : |X| = i}. The set of C -restricted flats of B_{n}(M) is

Q = Q(B_{n}(M), C) = {t ∈ Lat B_{n}(M) : V_{0}(t) ∉ C\{∅}},

partially ordered as in Lat B_{n}(M). Q has zero element ˆ0 = {0} and top element ˆ1 = F^{n}. Its characteristic polynomial is defined to be

p_{Q}(λ) = ∑_{t∈Q}μ_{Q}(ˆ0, t)λ^{n−dim t},

where μ_{Q} is the Möbius function of Q.

Theorem 1.1. With C and Q as above, Q has rank function r_{Q}(t) = dim t, characteristic polynomial

p_{Q}(λ) = (λ − 1)_{n,M} + ∑_{i=1}^{n}(−1)^{i−1}N_{i}(C)(M(i − 1) − 1)_{i−1,M}(λ − 1)_{n−i,M},

and Möbius invariant

μ_{Q}(ˆ0, ˆ1) = (−1)^{n} {(M(n − 1) + 1)_{n,M} − ∑_{i=1}^{n}N_{i}(C)(M(i − 1) − 1)_{i−1,M}(M(n − i − 1) + 1)_{n−i,M}} .

Moreover, if M ≥ 2 then (−1)^{n}μ_{Q}(ˆ0, ˆ1) > 0 and the coefficients of p_{Q}(λ) are all nonzero and alternate in sign.

For the proof see Section 4. Examples obtained by choosing C wisely include B_{n}, D_{n}, and all intermediate sets D_{n}∪{u_{1}, …, u_{k}} for k = 1, 2, …, n−1. For details on particular examples see Example 6.1.

Theorem 1.1 is a very special case of the main theorem, Theorem 4.1. Observe that, remarkably, although Q(B_{n}(M), C) is not necessarily a lattice or even a semilattice, still we can give a very explicit formula for its characteristic polynomial and (in Example 4.1) its Möbius function μ_{Q}(s, t).

A brief outline: Section 2 provides background information, especially the definitions of the characteristic polynomial of an extrinsically graded poset Q̃ and those of a biased graph Ω and its geometric lattice. Section 3 defines the poset Q̃(Ω, C) and investigates its structure. (The definition is all that is needed to understand Theorem 4.1, our main theorem.) Section 4 treats the computational aspect of the poset Q̃(Ω, C) when Ω is “full” and Section 5 treats non-full Ω. In Section 6 we examine numerous examples. Sections 7 and 8 discuss some problems suggested by our work.

We should mention that this article is a highly generalized version of the manuscript [7], which has been cited a few times in the literature.

2. Background definitions.

All our partially ordered sets (or “posets”), graphs, etc. are finite. For basics of posets we refer to [12], for matroids to [5], for graphs and biased graphs to [18] (but for the special case of signed graphs one may consult [15-17]).

For ready reference we list standard notations, some of which will be defined later in this section. We write ℙ = {1, 2, 3, …}, ℕ = {0, 1, 2, 3, …}, and [n] = {1, …, n} for n ∈ ℕ. Also, Ω denotes a biased graph of order n > 0 with vertex set V and edge set E, Lat Ω the lattice of flats of its bias matroid, r the rank function of the latter, and C an abstract simplicial complex on vertex set V .

2A. Set Posets and Simplicial Complexes. An (abstract) simplicial complex on vertex set V is a nonvoid class C ⊆ P(V) such that W ⊂ X ∈ C ⇒ W ∈ C. C can be said to have any vertex set that contains its support, supp C = ⋃ C. However, we need to know V in order to define the complement, C^{c} = P(V)\C.

A poset of sets, D, on vertex set V is a subclass of P(V) to which ∅ belongs. We write D^{∗} = D\{∅}. The induced subclass on W ⊆ V is D: W = {X ∈ C : X ⊆ W }. The contraction D/π, by a partition π of a subset of V , is {τ ⊆ π : ⋃ τ ∈ D}.

2B. Posets. Consider a poset Q with bottom element ˆ0. Each element x has a height, h(x) = length of a longest chain from ˆ0 to x. The height of Q is h(Q) = max h(x). If for each x every maximal chain from ˆ0 to x has length h(x), we call Q ranked, h(x) the rank of x, and h(Q) the rank of Q. The notation Q/x means {y ∈ Q : y ≥ x}. We write x ⋖ y to mean that y covers x.

An extrinsically graded poset is a triple Q̃ = (Q, h̃, h̃(Q)) where Q is a poset with ˆ0, h̃ is a strictly increasing function Q → ℕ such that h̃(ˆ0) = 0 (called the extrinsic grading), and h̃(Q) is an integer at least as large as the largest h̃(x). By Q̃/x we mean Q/x with extrinsic grading h̃_{Q̃/x}(y) = h̃(y) − h̃(x) and with h̃(Q/x) = h̃(Q) − h̃(x). We adopt the convention that a poset Q written without a tilde is “extrinsically graded” by its height function h (one might call this the intrinsic grading), while a tilde means there is an arbitrary extrinsic grading h̃.

One way to construct an extrinsically graded poset is to take a ranked poset P, such as a geometric lattice, and let Q be any subset containing ˆ0_{P} , extrinsically graded by the rank function of P. Our posets are examples of this construction. (Another such example is the intersection lattice of an arbitrary arrangement of subspaces in a vector space, ordered by reverse inclusion and graded by codimension.)

Recall that the Möbius function of a poset Q is the function μ_{Q} : Q × Q → ℤ defined by

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

The characteristic polynomial of Q̃ is

pQ̃(λ) = ∑_{x∈Q}μ_{Q}(ˆ0, x)λ^{h̃(Q)−h̃(x)}.

For instance, p_{Q}(λ) is the characteristic polynomial associated with the height function h. If Q has ˆ1, we call μ_{Q}(ˆ0, ˆ1) the Möbius invariant of Q; it equals pQ̃(0) if h̃(Q) = h̃(ˆ1).

2C. Graphs and Biased Graphs. A biased graph Ω = (Γ, B) is a graph Γ = (V, E) together with a subclass B of its polygons such that, if in a theta subgraph two polygons belong to B, so does the third. In biased graphs we allow four kinds of edges: links (two distinct endpoints), loops (two coincident endpoints), half edges (one endpoint), and loose edges (no endpoints). (Neither of the latter can belong to a polygon. In matroid theory a loose edge behaves like a balanced loop and a half edge like an unbalanced one, but for technical reasons it is helpful to allow all four types of edge.)

A subgraph or edge set is balanced if it contains no half edge and any polygon in it belongs to B. For S ⊆ E we let π(S) [or, respectively, π_{b}(S)] be the partition of V whose blocks are the vertex sets of the components [respectively, balanced components] of (V, S), let V_{0}(S) (or just V_{0}S) be the union of vertex sets of unbalanced components of (V, S), and set c(S) = |π(S)|, b(S) = |π_{b}(S)|. We write c(Ω) = c(E), b(Ω) = b(E), etc.

The bias matroid G(Ω) is the matroid on E whose rank function is r(S) = n − b(S). For the lattice of closed sets (or flats) we write Lat Ω, and Lat^{b} Ω for the subclass of balanced closed sets.

The complete lift matroid L_{0}(Ω) is the matroid on E ∪{e_{0}}, where e_{0} is a new element, whose rank function is n − c(S) − ε(S) where ε(S) = 0 if S is a balanced edge set and 1 otherwise.

Besides these basic ideas we need a number of technical definitions about graphs and biased graphs.

Let Γ be a graph (V, E). The set of endpoints of an edge e is V (e). The degree of a vertex is the number of incident edges. (A loop in this article counts once, not twice as in some other works.) For W ⊆ V and S ⊆ E we write W^{c} = V \W, S^{c} = E\S, and Γ|S = (V, S). An induced subgraph of Γ is Γ: W = (W, E: W) where W ⊆ V and E: W = {e ∈ E : ∅ ≠ V (e) ⊆ W }. W is stable if E: W = ∅. We denote by [Γ] the biased graph whose underlying graph is Γ and in which every polygon is balanced. If Γ has no loose or half edges, G([Γ]) is the usual polygon matroid of Γ.

We call a biased graph Ω simply biased if it has no loose edges, balanced loops, balanced digons, or pairs of unbalanced edges at the same vertex. We let

U(Ω) = {v ∈ V : v supports an unbalanced edge}

and we call Ω full if U(Ω) = V . If W ⊆ V, Ω^{(W)} denotes Ω with a half edge added at each vertex in W \U(Ω). We write Ω^{•} for Ω^{(V)} . By Ω^{∗} we mean Ω with unbalanced edges removed; E^{∗} is E(Ω^{∗}). If S ⊆ E, then Ω: W, Ω|S, etc., denote subgraphs of Γ with balance of polygons the same as in Ω. The contraction Ω/S is the biased graph whose vertex set is π_{b}(S) and whose edge set is S^{c} with the endpoints of an edge e modified as follows: an endpoint v is eliminated if v ∈ V_{0}(S) and is replaced by the block of π_{b}(S) containing it if v ∉ V_{0}(S). A polygon C in Ω/S is balanced if there is a balanced polygon C′ ⊆ C ∪ S such that C = C′\S. If S ∈ Lat Ω, then Lat (Ω|S) = [ˆ0, S]_{Lat Ω} and Lat (Ω/S) = (Lat Ω)/S.

Disjoint union is written Ω_{1} ∪ · Ω_{2} ; the balance of a polygon is the same as in Ω_{1} or Ω_{2} , whichever it is that contains the polygon.

2D. Gain Graphs and Coloring. A gain graph can be defined in the following way (simplified from [18, Section I.5]). Take a group 𝔊 of order M ≥ 1. On vertex set [n] construct a graph with edges (i, j; g) for all distinct i, j ∈ [n] and g ∈ 𝔊, but identify the edge (i, j; g) with (j, i; g^{−1}). This is the gain graph 𝔊K_{n}. We call g the gain of (i, j; g) in the direction from i to j and we write φ(i, j; g) = g. Calling a polygon {(i_{0}, i_{1}; g_{1}), (i_{1}, i_{2}; g_{2}), ⋯, (i_{k−1}, i_{k}; g_{k})}, where i_{0} = i_{k}, balanced when g_{1}g_{2} ⋯ g_{k} = 1 determines a biased graph [𝔊K_{n}]. Adding an unbalanced edge (say, a half edge) to each vertex gives 𝔊K_{n}^{•}. A gain graph Φ = (V, E, φ) with gain group 𝔊 and gain function φ is any subgraph of 𝔊K_{n}^{•}, φ being the restriction to E of the gain function of 𝔊K_{n}^{•}; [Φ] denotes the corresponding biased graph and G(Φ), Lat Φ, etc., the associated bias matroid G([Φ]), lattice Lat [Φ], and so forth. If Δ ⊆ K_{n}, then 𝔊Δ consists of all edges (i, j; g) of 𝔊K_{n} such that ij ∈ E(Δ), and 𝔊Δ^{•} is the same with an unbalanced edge at each vertex. We call 𝔊Δ the 𝔊-expansion of Δ and 𝔊Δ^{•} the full 𝔊-expansion. The lattice Lat 𝔊K_{n}^{•} is the well known Dowling lattice of 𝔊 of rank n [6, 12].

A signed graph is a gain graph whose gain group is the sign group {+, −}. Lat (±K_{n}^{•}) is the lattice of the root system B_{n} and Lat (±K_{n}) is that of D_{n}.

A k -coloring of Φ is a mapping κ : V → ([k] × 𝔊) ∪ {0}, where 0 ∉ 𝔊. The set of improper edges of κ is

I(κ) = (E: κ^{−1}(0)) ∪ {(i, j; g) ∈ E : κ(j) = κ(i)g ≠ 0},

where if κ(i) = (k, h) then κ(i)g = (k, hg), while if κ(i) = 0 then κ(i)g = 0. We call κ proper if I(κ) = ∅. When 𝔊 is finite there is a polynomial χ_{Φ}(λ), called the chromatic polynomial, which has the property that χ_{Φ}(kM +1) is the number of proper k -colorings of Φ. There is also a zero-free (or balanced) chromatic polynomial χ_{Φ}^{b}(λ) such that χ_{Φ}^{b}(kM) is the number of proper k -colorings not using the color 0. These polynomials satisfy χ_{Φ}(λ) = λ^{b(Φ)}p_{Lat Φ}(λ) and χ_{Φ}^{b}(λ) = λ^{c(Φ)}p_{Lat^{b}Φ}(λ). Because of these identities we define

χ_{Ω}(λ) = λ^{b(Ω)}p_{Lat Ω}(λ) and χ_{Ω}^{b}(λ) = λ^{c(Ω)}p_{Lat^{b}Ω}(λ)  (2.1)

for any biased graph. (See [18, Theorems III.5.1 and III.5.3].) When Ω is balanced, χ_{Ω}(λ + 1) = χ_{Ω}^{b}(λ) = χ_{Γ}(λ), the chromatic polynomial of the underlying graph Γ. When Ω is full, χ_{Ω}(λ) = p_{LatΩ}(λ). 2E. Formulas. A biased graph obeys convolution identities

\begin{matrix}χ_{Ω}(λ + μ) = ∑_{W ⊆V} χ_{Ω:W}^{b} (λ)χ_{Ω:W^{c}}(μ), \\ χ_{Ω}^{b}(λ + μ) = ∑_{W ⊆V} χ_{Ω:W}^{b} (λ)χ_{Ω:W^{c}}^{b}(μ) \end{matrix}  (2.2)

(see [18, Formula (III.6.1b)]). The former with μ = 1 reduces to

χ_{Ω}(λ) = ∑_{\begin{matrix}W ⊆V \\ W^{c} stable \end{matrix}} χ_{Ω:W}^{b} (λ − 1),  (2.3a)

which simplifies for full Ω to

χ_{Ω}(λ) = χ_{Ω}^{b}(λ − 1).  (2.3b)

For 𝔊-expansions there is a nice formula [18, Example III.4.6]:

χ_{𝔊Δ}^{b}(λ) = M^{n}χ_{Δ} (\frac{λ}{M} ) .  (2.4)

Combining with (2.3) and setting Δ = K_{n}, we get Dowling’s formula

p_{Lat 𝔊K_{n}^{•}}(λ) = χ_{𝔊K_{n}^{•}}(λ) = χ_{𝔊K_{n}}^{b}(λ − 1) = (λ − 1)_{n,M}.  (2.5)

Hence we can say that Lat 𝔊K_{n}^{•} has characteristic roots

1, M + 1, 2M + 1, …, (n − 1)M + 1.

2F. Vector Representations. Suppose Φ is a full gain graph on V = [n] whose gain group 𝔊 is a subgroup of the multiplicative group of a field F. Then LatΦ is canonically isomorphic to the lattice of flats of the vector set x(Φ) = {u_{i} : i ∈ [n]} ∪ {u_{i} − gu_{j} : (i, j; g) ∈ E(Φ)} in F^{n}. (See [15, Theorem 8B.1] for a proof when |𝔊| = 2, [6, proof of Theorem 10] or [18, Theorem IV.2.1] for a general proof.) Thus for example ℤ_{M}K_{n}^{•} has a vector representation in ℂ^{n}.

3. The poset and its structure.

The subject of our main results is an extrinsically graded poset Q̃(Ω, C) constructed from a full biased graph Ω and an indexing simplicial complex C on vertex set V . The definition makes sense, however, even when Ω is not full and C is not a simplicial complex. The poset is

Q(Ω, C) = {A ∈ L(Ω) : V_{0}A ∉ C^{∗}}.  (3.1)

We call its members the C -constrained flats of G(Ω). The grading h̃ is that inherited from Lat Ω:

h̃(A) = r(A) = n − b(A) and h̃(Q(Ω, C)) = n.  (3.2)

Evidently, Q̃(Ω, C) has ˆ0 = clos ∅ and, if V ∉ C, ˆ1 = E.

As extreme instances, for any biased graph Ω we have Q̃(Ω, {∅}) = Lat Ω and Q̃(Ω, P(V)) = Lat^{b}Ω, so that p_{Q̃(Ω,{∅})}(λ) = χ_{Ω}(λ) and p_{Q̃(Ω,P(V))}(λ) = χ_{Ω}^{b}(λ).

One naturally wonders whether Q = Q(Ω, C) may be a lattice or ranked, whether r (that is, h̃) coincides with the height function h of Q, etc. We shall not attempt to determine exactly when Q is a lattice or a ranked poset, but we do characterize the circumstances in which h = r, h(Q) = n, or Q is ranked with h = r. These questions are germane because, for instance, if h = r and h(Q) = n then pQ̃(λ) equals the intrinsic characteristic polynomial p_{Q}(λ), while if h ≠ r, pQ̃(λ) and p_{Q}(λ) should be significantly different. (But just how different they might be is unknown.) Example 3.1. Q need not be a lattice or even a semilattice. Let Ω = [±K_{4}^{•}] and C = P([2]). Take B_{1} = {+12} and B_{2} = {−12}, where εij denotes the edge ij with sign ε, and A_{1} = E: {1, 2, 3}, A_{2} = E: {1, 2, 4}. Then A_{1} and A_{2} cover B_{1} and B_{2} in Q, so Q has neither meets nor joins, not even of pairs that have lower or upper bounds in Q. ■

Lemma 3.2. Suppose A, B ∈ Q = Q(Ω, C) and B < A in Lat Ω. Then B ⋖ A in Q if and only if either:

(i) V_{0}A = ∅, and B ⋖ A in Lat Ω; or (ii) V_{0}B ∉ C, and B ⋖ A in Lat Ω; or (iii) V_{0}B = ∅ ⊂ V_{0}A ∉ C, and A and B satisfy these properties: B: (V_{0}A)^{c} =

A: (V_{0}A)^{c}, B: V_{0}A is a maximal element of Lat^{b}(Ω: V_{0}A), and for every X ∈ π(Ω: V_{0}A) we have (V_{0}A)\X ∈ C.

Proof. Assume B ⋖ A in Q. If A is balanced or B is not, the entire interval [B, A]_{Lat Ω} lies in Q, so A ⋗ B in Q.

Henceforth let V_{0}B = ∅ and V_{0}A ∉ C. Set A_{0} = A: V_{0}A and B_{0} = B: V_{0}A. Then B_{0} ⊂ A_{0} . Since A′ = A_{0} ∪ (B\B_{0}) is a flat of G(Ω) and has V_{0}A′ = V_{0}A ∉ C, A′ is in Q and A ≥ A′ > B. Thus A′ = A; that is, A and B are the same except that B_{0} ⊂ A_{0} . Furthermore, B_{0} and A_{0} are in Q and [B_{0}, A_{0}] ≅ [B, A], both in Q and in Lat Ω.

If B_{0} were not a maximal balanced flat in G(Ω: V_{0}A) = G(Ω)|A_{0} , then it could be enlarged to a balanced flat B′_{0} and we would have A_{0} > B′_{0} > B_{0} in Q. So B_{0} is maximal.

If there were X ∈ π(Ω: V_{0}A) such that Y = (V_{0}A)\X ∉ C, then A_{0} > (B: X)∪(E: Y) > B_{0} in Q, contrary to assumption.

We have proved the necessity of the conditions of the lemma.

Now we assume the conditions hold and we prove A ⋗ B in Q. Again the nontrivial case is (iii), where B but not A is balanced, and again [B, A] ≅ [B_{0}, A_{0}]. Suppose A_{0} > F > B_{0} in Q. Then F cannot be balanced, or it would equal B_{0} . Since π(B_{0}) = π(Ω: V_{0}A) = π(A_{0}), π(F) must equal π(Ω: V_{0}A), whence V_{0}(F) is a union of blocks of π(Ω: V_{0}A). But then V_{0}F, if not in C^{∗}, equals ∅ or V_{0}A, whence F = B or A, a contradiction. Thus A ⋗ B. ■

Lemma 3.3. Suppose B ⋖ A in Q̃ = Q̃(Ω, C). The step length r(A) − r(B) of the interval [B, A] is one except that when B is balanced and A is not, it equals c(Ω: V_{0}A).

Proof. With notation as in the preceding proof, note that [B, A] and [B_{0}, A_{0}] have the same step length in Q̃. Moreover, b(A_{0}) and b(B_{0}), calculated in Ω: V_{0}A, respectively equal 0 and c(Ω: V_{0}A). Therefore r(A_{0}) − r(B_{0}) = c(Ω: V_{0}A), as claimed. ■

Lemma 3.4. Let A ∈ Q = Q(Ω, C). There exists B ∈ Q such that A ⋗ B in Lat Ω if and only if either

(i) A ⊃ E: V_{0}A, or (ii) A = E: W where b(Ω: W) = 0, and there exist X ∈ π(Ω: W) and Y ⊆ X such

that c(Ω: Y) = 1, b(Ω: (X\Y)) = 0, and W \Y ∉ C^{∗}.

Proof. First we show the conditions are sufficient. If A ⊃ E: V_{0}A, then A has a nontrivial balanced component A: X, where |X| > 1. Let D be a cutset of A: X and B = A\D. Then V_{0}B = V_{0}A so B ∈ Q, while b(B) = b(A) + 1 so r(B) = r(A) − 1, whence A ⋗ B in Lat Ω.

If A = E: W where b(Ω: W) = 0 (so W = V_{0}A), let B_{Y} be a maximal balanced flat in Ω: Y and let B = E: (W \Y)∪B_{Y} . Thus r(B) = |W |−b(B: W) = |W |−b(B_{Y}) = |W |−1. Thus B ⋖ A in Lat Ω. The fact that W \Y ∉ C^{∗} implies B ∈ Q.

To prove necessity we assume B exists. Let W = V_{0}A. If we are not in case (i), then V_{0}B ⊂ W and A = E: W. Set Y = W \V_{0}B. Thus r(B) = |W | − b(B: Y) − b(B: V_{0}B) = |W | − b(B: Y). The covering relation A ⋗ B in Lat Ω implies that b(B: Y) = 1, whence we conclude that c(Ω: Y) = 1, so that Y is contained in a block X of π(Ω: W). The fact that V_{0}B = W \Y implies that b(Ω: (X\Y)) = 0 and W \Y ∉ C^{∗}. ■

The case of full Ω is much simpler:

Lemma 3.5. Let Ω be full and A ∈ Q = Q(Ω, C). There exists B ∈ Q such that A ⋗ B in Lat Ω if and only if

(i) A ⊃ E: V_{0}A, or

(ii) A = E: V_{0}A and either c(Ω: V_{0}A) = 1 or V_{0}A is not minimal in C^{c}.

Proof. In Lemma 3.4(ii), for any singleton Y ⊆ W we have c(Ω: Y) = 1 and b(Ω: (X\Y)) = 0 because Ω is full.

If V_{0}A is nonminimal in C^{c} we can find Y to make W \Y ∉ C^{∗}. If c(Ω: W) = 1 then Y = X = W makes W \Y ∉ C^{∗}.

Conversely, suppose Y exists as in Lemma 3.4(ii). If Y = W then c(Ω: W) = 1 so B exists. If Y ⊂ W, Y is nonvoid because c(Ω: Y) = 1 so we can choose y ∈ Y . Then W \{y} ∉ C because W \Y ∉ C. ■

Now we can answer questions about height in Q when Ω is full.

Theorem 3.6. Suppose Ω full. For Q(Ω, C) to have height n it is necessary and sufficient that π(Ω) ⊈ C.

Proof. If there is an X ∈ π(Ω)\C, one easily constructs a chain of length n from ˆ0 to E in Q(Ω, C).

Suppose contrariwise that such a chain exists, say ˆ0 = A_{0} ⋖ A_{1} ⋖ ⋯ ⋖ A_{n} = E. There is some index k for which A_{k} is unbalanced but A_{k−1} is balanced. Thus V_{0}A_{k} ∉ C. By Lemma 3.3, Ω: V_{0}A is connected. It therefore lies in a component Ω: X of Ω, and X cannot belong to C. ■

Corollary 3.7. If Ω is full and connected, then Q(Ω, C) has height n if and only if V ∉ C. ■

The criterion of Corollary 3.7 obviously fails to be sufficient if Ω is disconnected.

We call C disconnection-closed with respect to Ω if, whenever X and Y are disjoint members of C and no edge of Ω joins a vertex in X to one in Y , then X ∪ Y ∈ C.

Theorem 3.8. Supposing Ω full, the following properties are equivalent.

(i) Q(Ω, C) has height function h equal to r = r_{Lat Ω} .

(ii) For every minimal member W of C^{c}, Ω: W is connected.

(iii) C is disconnection-closed with respect to Ω.

(iv) For every W ∈ C^{c}, π(Ω: W) ⊈ C.

Proof. We show (iv) is equivalent to each other property.

That (i) ⇔ (iv) is an easy consequence of Theorem 3.6.

Obviously (iv) ⇒ (ii). To prove the converse assume (ii) and choose a minimal W ∉ C such that π(Ω: W) ⊆ C, if any such W exists. W cannot be minimal in C^{c} because of (ii). Therefore we can strip off a vertex w ∈ W so that W \w ∉ C, but clearly π(Ω: (W \w)) ⊆ C, contradicting the minimality of the counterexample.

That (iii) ⇔ (iv) is easy to prove by induction on c(Ω: (X ∪ Y)). ■

Theorem 3.9. Let Ω be any biased graph. For Q(Ω, C) to be a ranked poset with rank function r it is necessary and sufficient that, whenever W ∈ C^{c} is such that b(Ω: W) = 0, then either Ω: W is connected or there is an X ∈ π(Ω: W) for which W \X ∉ C.

Proof. Every maximal element of Q has the same extrinsic height because there is only one such element unless C = P(V), and then Q = Lat^{b}Ω, in which every maximal element F has r(F) = n − c(Ω) (from [18, Theorem II.2.1(j)]).

Now, the key to the proof is that Q is ranked with h = r if and only if every covering interval has step length 1. Lemmas 3.2 and 3.3 imply that step length 1 is equivalent to the criterion of our theorem. ■

Corollary 3.10. Suppose Ω complete. Then Q(Ω, C) is ranked with rank function r. ■

In the rest of this section we develop three lemmas that describe order filters and intervals in Q̃(Ω, C), for use in calculating the Möbius function in Section 4. The lemmas remain valid with any poset of sets in place of the simplicial complex C.

Lemma 3.11. Let A ∈ Q(Ω, C). The interval [ˆ0, A] in Q̃(Ω, C) equals Q̃(Ω|A, C) and is canonically isomorphic to

Q̃(Ω: V_{0}A, C: V_{0}A) × ×_{Z∈π_{b}(A)}Lat((Ω|A): Z).

The proof is immediate. The canonical isomorphism is that by which (B_{0}, B_{1}, …, B_{b(A)}), an element of the Cartesian product set, corresponds to B_{0} ∪ B_{1} ∪ ⋯ ∪ B_{b(A)} ∈ Lat Ω. Note that (Ω|A): Z is the biased graph of the balanced component A: Z of A, and its underlying graph is (Z, A: Z). ■

Lemma 3.12. Let A ∈ Q(Ω, C). The order filter Q̃(Ω, C)/A is canonically isomorphic to Q̃(Ω/A, C/π_{b}(A)).

Proof. The isomorphism here is that induced by the canonical partial function V → π_{b}(A), which carries v ∈ V to the block X ∈ π_{b}(A) such that v ∈ X, if v ∈ ⋃ π_{b}(A), and is undefined otherwise.

We know from [18, Theorem II.2.5] that (Lat Ω)/A ≅ Lat(Ω/A); it follows that the extrinsic grading of Q̃(Ω, C)/A equals that of Q̃(Ω/A, C/π_{b}(A)). We need to prove that C/π_{b}(A) is the correct indexing complex. A flat F ≥ A in Lat Ω is excluded from Q̃(Ω, C)/A when V_{0}(F) ∈ C. The corresponding flat F′ ∈ Lat(Ω/A) satisfies V_{0}(F′) = {X ∈ π_{b}(A) : X ⊆ V_{0}(F)}, by [18, Lemma I.4.4]. The desired conclusion follows at once. ■

Combining these two results gives the main lemma:

Lemma 3.13. Let A_{1} ≤ A_{2} in Q(Ω, C) and let W = V_{0}A_{2} . For Z ∈ π_{b}(A_{2}), let Γ_{Z} = (Z, A_{2}: Z)/(A_{1}: Z), the underlying graph of (Ω|A_{2}): Z contracted by A_{1}: Z. The interval [A_{1}, A_{2}] in Q̃(Ω, C) is canonically isomorphic to

Q̃((Ω: W)/(A_{1}: W), (C: W)/π_{b}(A_{1}: W)) × ×_{Z∈π_{b}(A_{2})}Lat(Γ_{Z}). ■

4. Characteristic polynomial and Möbius function

Here at last is the centerpiece of our work. For the theorem, note that χ_{∅}(λ) = χ_{∅}^{b}(λ) = 1.

Theorem 4.1. Let Ω be a full biased graph without loose edges or balanced loops and let C be an abstract simplicial complex on vertex set V . The characteristic polynomial of Q̃ = Q̃(Ω, C) is given by

pQ̃(λ) = ∑_{W ∈C}χ_{Ω:W}^{b} (1)χ_{Ω:W^{c}}^{b}(λ − 1).  (4.1)

If V ∉ C, the Möbius invariant of Q̃ is

μQ̃(ˆ0, ˆ1) = ∑_{W ∈C}χ_{Ω:W}^{b} (1)μ_{L(Ω:W^{c})}(ˆ0, ˆ1).  (4.2)

We have written χ_{Ω:W}^{b} (1) and χ_{Ω:W^{c}}^{b}(λ − 1) but because Ω is full those quantities equal χ_{Ω:W} (2) and χ_{Ω:W^{c}}(λ), by the identity (2.3b). Sometimes one form is preferable, sometimes the other. For nonempty W, moreover,

χ_{Ω:W}^{b} (1) = (−1)^{|W |−c(Ω:W)}β(L_{0}(Ω^{∗}: W))  (4.3)

by [18, Theorem III.5.2], where β denotes Crapo’s invariant, which is nonnegative [4].

We do not know any enumerative interpretation of pQ̃(λ). It would be quite interesting if there is one. Proof. The form of the characteristic polynomial makes Möbius inversion the natural choice for proving Theorem 4.1. The model is the proof by counting colorings (see [10, p. 362]) that the chromatic polynomial of a graph equals the characteristic polynomial of its polygon matroid (up to a factor of a power of λ). We face two difficulties. One is that the function to be inverted is relatively complicated. The other is that we can color only when Ω has gains in a finite group. Thus we give two proofs: one depends on counting colorings to set up the Möbius inversion; the second is an algebraic adaptation of the first that permits us to dispense with coloring and be completely general.

We write Q for Q(Ω, C).

Coloring Proof. We assume Ω = [Φ], the biased graph of a gain graph Φ whose gain group 𝔊 is finite. Write M = |𝔊|. A C -restricted coloring of Φ is a coloring κ whose zero set κ^{−1}(0) is not in C^{∗}.

Step 1. We set up a Möbius inversion. Let k ∈ ℕ and λ = kM +1. For A ∈ L let f(A) be the number of C -restricted k -colorings κ with I(κ) ≥ A and let g(A) be the number with I(κ) = A. Obviously,

f(A) = ∑_{A′≥A}g(A′),  (4.4)

the sum being taken indifferently in Q or Lat Ω since g(A′) = 0 if A′ ∉ Q. It is also clear that g(∅) is the number of proper k -colorings of Φ; that is, g(∅) = χ_{Ω}(λ).

Before inverting (4.4) we need an explicit formula for f. When we color so that I(κ) ≥ A there are three points to remember: we must color 0 on V_{0}(A), the coloring of each block X ∈ π_{b}(A) is determined by the color on one vertex, and each such block is all zero or all non-zero. If V_{0}(A) ∉ C, then f(A) = λ^{b(A)} , the number of k -colorings with I(κ) ≥ A. If V_{0}(A) = ∅, f(A) equals λ^{b(A)} less the number of k -colorings (with I(κ) ≥ A) whose zero set is in C^{∗}. To evaluate the latter number, let ζ ⊆ π_{b}(A) be the set of zero-colored blocks. Then there are kM = λ − 1 ways to color each of the remaining blocks, so

f(A) = \{ \begin{matrix}λ^{b(A)}  if V_{0}(A) ∉ C, \\ λ^{b(A)} − ∑_{\begin{matrix}ζ⊆π_{b}(A) \\ ⋃ ζ∈C^{∗} \end{matrix}}(λ − 1)^{b(A)−|ζ|}  if V_{0}(A) = ∅. \end{matrix}  (4.5)

Step 2. Now we invert (4.4), regarded as a sum over Q, employing (4.5) to evaluate f. The inversion yields

g(A′) = ∑_{A≥A′}μ_{Q}(A′, A)f(A),

from which we conclude that

g(∅) = ∑_{A∈Q}μ_{Q}(∅, A)λ^{b(A)} − ∑_{\begin{matrix}A∈Q \\ V_{0}(A)=∅ \end{matrix}} ∑_{\begin{matrix}ζ⊆π_{b}(A) \\ ⋃ ζ∈C^{∗} \end{matrix}}μ_{Q}(∅, A)(λ − 1)^{b(A)−|ζ|}.  (4.6)

The first sum equals pQ̃(λ). To simplify the second we write Z = ⋃ ζ and sum over Z ∈ C^{∗}: then for each Z we sum over A ∈ Lat^{b}Ω such that Z is a union of blocks of π_{b}(A). Thus ζ is determined: ζ = {X ∈ π_{b}(A) : X ⊆ Z}. We further split A into A_{1} = A: Z and A_{2} = A: Z^{c}. Since (V, A) = (Z, A_{1})∪ · (Z^{c}, A_{2}), the Möbius function factors and the whole sum becomes

∑_{Z∈C^{∗}} ∑_{A_{1}∈Lat^{b}(Ω:Z)} ∑_{A_{2}∈Lat^{b}(Ω:Z^{c})}μ(∅, A_{1})μ(∅, A_{2})(λ − 1)^{b(A_{2})}

= ∑_{Z∈C^{∗}}χ_{Ω:Z}^{b}(1)χ_{Ω:Z^{c}}^{b}(λ − 1).

Substituting this expression for the double sum in (4.6) and recalling that g(∅) = χ_{Ω}(λ), we easily deduce (4.1).

Step 3. To prove (4.2) we set λ = 0 in (4.1). ■

Algebraic Proof. To generalize the first proof to any biased graph Ω we distill the algebraic essence of f and g. For A ∈ Lat Ω let us redefine

f(A) = \{ \begin{matrix}λ^{b(A)}  if V_{0}(A) ∉ C, \\ λ^{b(A)} − ∑_{Z∈C^{∗}} ∑_{\begin{matrix}ζ⊆π_{b}(A) \\ V_{0}A∪⋃ ζ=Z \end{matrix}}(λ − 1)^{b(A)−|ζ|}  if V_{0}(A) ∈ C, \end{matrix}

and

g(A) = \{ \begin{matrix}χ_{Ω/A}(λ) = χ_{Ω/A}^{b}(λ − 1) & if V_{0}(A) ∉ C^{∗}, \\ 0 & if V_{0}(A) ∈ C^{∗}. \end{matrix}

Once we prove that (4.4) holds we can proceed as in Steps 2 and 3 of the first proof.

First, suppose V_{0}(A) ∉ C. Then in (4.4) we are summing over A′ in Lat Ω. Bearing in mind that Lat(Ω/A′) ≅ [A′, E]_{LatΩ} , we have

\begin{aligned}∑_{A′≥A}g(A′) & = ∑_{A′≥A}χ_{Ω/A′}(λ) = ∑ ∑_{A≤A′≤A′′}μ(A′, A′′)λ^{b(A′′)} \\ & = λ^{b(A)} = f(A). \end{aligned}

Now assume V_{0}(A) ∈ C. Again summing over A′ in Lat Ω, we have

\begin{aligned}∑_{A′≥A}g(A′) & = ∑_{A′≥A}χ_{Ω/A′}(λ) − ∑_{\begin{matrix}A′≥A \\ V_{0}A′∈C^{∗} \end{matrix}}χ_{Ω/A′}(λ) \\ & = λ^{b(A)} − ∑_{Z∈C^{∗}} ∑_{\begin{matrix}A′≥A \\ V_{0}A′=Z \end{matrix}}χ_{Ω/A′}^{b}(λ − 1). \end{aligned}

Therefore,

f(A) − ∑_{A′≥A}g(A′) = ∑_{Z∈C^{∗}} \{ ∑_{\begin{matrix}A′≥A \\ V_{0}A′=Z \end{matrix}}χ_{Ω/A′}^{b}(λ − 1) − ∑_{\begin{matrix}ζ⊆π_{b}(A) \\ V_{0}A∪⋃ ζ=Z \end{matrix}}(λ − 1)^{b(A)−|ζ|}\} .

We wish to show that the quantity in braces equals zero.

If Z is not the union of V_{0}(A) and ⋃ ζ for some ζ ⊆ π_{b}(A), then no A′ ≥ A can have V_{0}(A′) = Z, so both sums are empty.

If Z is such a union, then ζ is unique so the second sum equals (λ − 1)^{b(A:Z^{c})} . As for the first sum, let A′_{0} = E: Z, A′_{1} = A′: Z^{c}, and A_{1} = A: Z^{c}. Then A′ = A′_{0} ∪ A′_{1} , and A_{1} ≤ A′_{1} in Lat^{b}(Ω: Z^{c}). By the definition of contraction, Lat^{b}(Ω/A′) ≅ Lat^{b}((Ω: Z^{c})/A′_{1}); thus χ_{Ω/A′}^{b}(λ − 1) = χ_{(Ω:Z^{c})/A′_{1}}(λ − 1). It follows that

∑_{\begin{matrix}A′≥A in Lat Ω \\ V_{0}A′=Z \end{matrix}}χ_{Ω/A′}^{b}(λ − 1) = ∑_{A_{1}≤A′_{1}∈Lat^{b}(Ω:Z^{c})}χ_{(Ω:Z^{c})/A′_{1}}^{b}(λ − 1)

= ∑_{\begin{matrix}A_{1}≤A′_{1}≤A′′_{1} \\ ∈Lat^{b}(Ω:Z^{c}) \end{matrix}} ∑ μ(A′_{1}, A′′_{1})(λ − 1)^{b(A′′_{1})}

= (λ − 1)^{b(A_{1})} = (λ − 1)^{b(A:Z^{c})}.

The two sums in the braces are consequently equal.

Hence (4.4) is valid and the proof can continue through Steps 2 and 3. ■

Quite a different proof can be given, depending on guessing the correct formula, induction, the convolution identities (2.2), and intricate calculations. (This was essentially Hanlon’s original proof in [7] of a form of Theorem 1.1 for B_{n}.) We omit it because we feel that the inversion proofs are more natural and illuminating.

Proof of Theorem 1.1. By Section 2F, Q(B_{n}(M), C) is canonically isomorphic to Q̃(ℤ_{M}K_{n}^{•}, C), in which h = h̃ = r (by Theorem 3.8; also easy to check directly). The characteristic polynomial of the latter is evaluable by Theorem 4.1 and Equation (2.5). The sign properties follow from the continuation of Example 4.1, after Corollary 4.7. ■

We present next two variations on Theorem 4.1: the first one elementary, the second an intriguing formula that expresses pQ̃(λ) in terms of principal simplicial complexes though at the cost of having to compute a new Möbius function. The first variation is useful when C is very large. Corollary 4.2. If Ω is full, then

p_{Q̃(Ω,C)}(λ) = χ_{Ω}^{b}(λ) − ∑_{W ∉C}χ_{Ω:W}^{b} (1)χ_{Ω:W^{c}}^{b}(λ − 1).

Proof. Rewriting (4.1) slightly,

pQ̃(λ) = ∑_{W ⊆V} χ_{Ω:W}^{b} (1)χ_{Ω:W^{c}}^{b}(λ − 1) − ∑_{W ∉C}χ_{Ω:W}^{b} (1)χ_{Ω:W^{c}}^{b}(λ − 1).

The former sum equals χ_{Ω}^{b}(λ) by (2.2). ■

Given C, let M(C) consist of all intersections of one or more maximal elements of C and let M̂(C) = M(C) ∪ {ˆ1} where ˆ1 is not in M(C). Corollary 4.3. If Ω is full, then

p_{Q̃(Ω,C)}(λ) = − ∑_{W ∈M(C)}μ_{M̂(C)}(W, ˆ1)p_{Q̂(Ω,P(W))}(λ).

Proof. The right-hand side expands to

\begin{matrix}− ∑ ∑_{X⊆W ∈M(C)}μ(W, ˆ1)χ_{Ω:X}^{b}(1)χ_{Ω:X^{c}}^{b}(λ − 1) \\ = ∑_{X∈C}χ_{Ω:X}^{b}(1)χ_{Ω:X^{c}}^{b}(λ − 1) \{− ∑_{X⊆W ∈M(C)}μ(W, ˆ1)\} . \end{matrix}

Let X̄ be the intersection of all maximal elements of C that contain X. Then X̄ ∈ M(C), so the quantity in braces reduces to μ(ˆ1, ˆ1) = 1. Then by Theorem 4.1 the outer sum equals pQ̃(λ). ■

Knowing the formula (4.2) for the Möbius invariant of Q(Ω, C), we can write an expression for the Möbius function of any interval [A_{1}, A_{2}] using the notation of Lemmas 3.11 – 13.

Corollary 4.4. Let Ω be a full biased graph and let A_{1} ≤ A_{2} in Q(Ω, C). Setting W = V_{0}A_{2}, Q′ = Q((Ω: W)/(A_{1}: W), C/π_{b}(A_{1}: W)), and Γ_{Z} = (Z, A_{2}: Z)/(A_{1}: Z) for Z ∈ π_{b}(A_{2}), we have

μ_{Q}(A_{1}, A_{2}) = μ_{Q′}(ˆ0, ˆ1) ∏_{Z∈π_{b}(A)}μ_{Lat Γ_{Z}} (ˆ0, ˆ1).

Proof. We appeal to Lemma 3.13 for the structure of [A_{1}, A_{2}]. ■

Example 4.1. We show how Corollary 4.4 applies to Ω = [𝔊K_{n}^{•}]. That gives the Möbius function of B_{n}(M) if we take group ℤ_{M}. As usual, we set M = |𝔊|.

Let Q = Q(𝔊K_{n}^{•}, C) and let A_{1} ≤ A_{2} in Q. Let Z_{1}, Z_{2}, …, Z_{k} be the balanced components of (V, A_{2}), let Z_{0} = V_{0}(A_{2})\V_{0}(A_{1}), and let n_{i} be the number of components of (V, A_{1}) contained in Z_{i}. Thus, n_{0} is the number of balanced components of (V, A_{1}) that are contained in V_{0}(A_{2}), and n_{0} + n_{1} + ⋯ + n_{k} − k = r(A_{2}) − r(A_{1}). Then

μ_{Q}(A_{1}, A_{2}) = (−1)^{n_{0}+n_{1}+···+n_{k}−k}(n_{1} − 1)! ⋯ (n_{k} − 1)!

· {(M(n_{0} − 1) + 1)_{n_{0},M}

− ∑_{i=1}^{n}N_{i}(C/π_{b}(A_{1}: Z_{0}))(M(i − 1) − 1)_{i−1,M}(M(n_{0} − i − 1) + 1)_{n_{0}−i,M}}.

(4.7)

Proof. In Corollary 4.4, (Ω: W)/(A_{1}: W) simplifies, by elimination of multiple unbalanced edges and multiple links having the same gain, to [𝔊K_{n_{0}}^{•}], and Γ_{Z_{i}} simplifies to K_{n_{i}} for i ≥ 1. Then Theorem 1.1 gives μ_{Q′}(ˆ0, ˆ1). (That μ_{LatK_{n}}(ˆ0, ˆ1) = (−1)^{n−1}(n − 1)! is a well known theorem of Schutzenberger and of Frucht and Rota; see [10, p. 359].) ■

See the continuation of this example following Corollary 4.7.

One would like to determine the sign of μ_{Q}(ˆ0, ˆ1). This seems difficult, but in many cases we can show that (−1)^{n}μ_{Q}(ˆ0, ˆ1) is positive or at least non-negative. We begin with some examples.

Example 4.2. If C = {∅} or C = P(V)\{V }, then (−1)^{n}μ_{Q}(ˆ0, ˆ1) ≥ 0; it is positive except when C = P(V)\{V } and Ω^{∗} has a balanced block.

Proof. In the former case Q = Lat Ω. We know the sign of μ by Rota’s theorem [10, p. 357, Theorem 4].

In the latter case, μ_{Q}(ˆ0, ˆ1) = −χ_{Ω}^{b}(1) = (−1)^{n}β(L_{0}(Ω^{∗})), where β is known to be nonnegative always and positive if and only if L_{0}(Ω^{∗}) is inseparable [4]. Inseparability holds if and only if Ω has no balanced block [18, Theorem II.3.8]. ■

Example 4.3. Suppose T is a tree of order n and Ω = [T^{•}]. The sign of μ_{Q}(ˆ0, ˆ1) is very sensitive to the choice of simplicial complex. Since Ω^{∗} is balanced, χ_{Ω:Y}^{b} (λ) = χ_{T:Y} (λ) = λ^{c(T:Y)}(λ − 1)^{|E(T:Y)|}. We conclude that χ_{Ω:W}^{b} (1) = 1 if W is stable in T and 0 otherwise. Thus from Theorem 4.1 we deduce that

μ_{Q}(ˆ0, ˆ1) = ∑_{W ∈C ; stable in T}(−1)^{|W^{c}|}2^{|E(T:W^{c})|}.

Since W is stable, |E(T: W^{c})| = n − 1 − d_{T} (W), where d_{T} means degree in T and d_{T} (W) = ∑_{v∈W} d_{T} (v). Therefore,

(−1)^{n}μ_{Q}(ˆ0, ˆ1) = 2^{n−1} ∑_{W ∈C ; stable in T}(−1)^{|W |}2^{−d_{T} (W)}.  (4.8)

We can now produce an indexing complex for which (−1)^{n}μ_{Q}(ˆ0, ˆ1) is negative. Take C = C_{V} = {∅, {v} : v ∈ V } and assume n ≥ 3. Because at least two vertices have degree one, (4.8) becomes negative.

For instance, if T is a star then (−1)^{n}μ_{Q}(ˆ0, ˆ1) = −(n − 3)2^{n−2} − 1. ■

We can predict non-negativity if Ω meets some rather stringent conditions. Theorem 4.5. Assume that Ω is full, V ∉ C, and, for every W ∈ C^{c}, Ω: W is connected. Then (−1)^{n}μ_{Q(Ω,C)}(ˆ0, ˆ1) ≥ 0.

Furthermore, (−1)^{n}μ_{Q(Ω,C)}(ˆ0, ˆ1) > 0 if supp C ≠ V or if Ω^{∗}: W has no balanced blocks for some W ∈ C^{c} (in particular, if Ω^{∗} has no balanced blocks). Proof. First we establish a lemma.

Lemma 4.6. Let Ω be full and V ∉ C. Then

(−1)^{n}μ_{Q(Ω,C)}(ˆ0, ˆ1) = ∑_{W ∈C^{c}}(−1)^{c(Ω:W)−1}β(L_{0}(Ω^{∗}: W))|μ_{Lat(Ω:W^{c})}(ˆ0, ˆ1)|.  (4.9)

Proof. From Corollary 4.2 and Equation (4.3) we obtain

μ_{Q}(ˆ0, ˆ1) = 0 − ∑_{W ∉C}(−1)^{|W |−c(Ω:W)}β(L_{0}(Ω: W))μ_{Lat(Ω:W^{c})}(ˆ0, ˆ1).

Since Lat(Ω: W^{c}) is a geometric lattice of rank |W^{c}|, we know the Möbius invariant has sign (−1)^{|W^{c}|}. The lemma follows. ■

Now it is clear that, assuming c(Ω: W) = 1 for all W ∉ C, the right-hand side of (4.9) is non-negative. Under the same assumption, it is positive if any one Ω^{∗}: W has no balanced block or, since β(∅) = 1, if there is a vertex v such that {v} ∉ C. ■ Corollary 4.7. If Ω is full and complete and Ω^{∗} is unbalanced, then (−1)^{n}μ_{Q(Ω,C)}(ˆ0, ˆ1) > 0 for every indexing complex C. ■

It seems that Theorem 4.5 is far from covering all cases in which one would expect (−1)^{n}μ_{Q}(ˆ0, ˆ1) to be nonnegative. It does not apply to Example 4.2, for instance.

Example 4.1, continued. If Ω = [𝔊K_{n}^{•}], where |𝔊| ≥ 2, then sgn μ_{Q(Ω,C)}(A_{1}, A_{2}) = (−1)^{n_{0}+n_{1}+···+n_{k}−k} = (−1)^{r(A_{2})−r(A_{1})} . Proof. Referring back to Lemma 3.13, we see that the task is to show that sgn μ_{Q′}(ˆ0, ˆ1) = (−1)^{n_{0}} , where Q′ is as in Corollary 4.4. But Ω: W = [𝔊K_{|W |}^{•}]; contracting by A_{1}: W and neglecting multiple edges as in the proof of (4.7), we see that Q′ = Q(Ω′, C′) for Ω′ = [𝔊K_{n_{0}}^{•}] and suitable C′. Now Corollary 4.7 applies (unless n = 1, which is trivial). ■

It follows that, if w_{i} denotes the coefficient of λ^{n−i} in pQ̃(λ), then

|w_{i}| = (−1)^{i}w_{i} = ∑_{\begin{matrix}A∈Q(Ω,C) \\ r(A)=i \end{matrix}} |μ_{Q}(ˆ0, A)|.

Thus the coefficients of pQ̃(λ) alternate in sign, and they are all nonzero if C ⊂ P (V). In particular,

(−1)^{n}μ_{Q}(ˆ0, ˆ1) > 0 if C ⊂ P(V).

(If C = P(V), then Q = Lat^{b}(𝔊K_{n}^{•}), which has rank n−1. Thus w_{n} = 0 but the other w_{i} are all nonzero.) These observations complete the proof of Theorem 1.1, which concerns the case in which 𝔊 = ℤ_{M}. ■

We have one more topic to develop in this section: a deletion-contraction identity. Theorem 4.8. Suppose Ω is full and e is a link in Ω. Then

p_{Q̃(Ω,C)}(λ) = p_{Q̃(Ω\e,C)}(λ) − p_{Q̃(Ω/e,C/π_{b}(e))}(λ).

Proof. In the formula of Theorem 4.1 there are three kinds of sets W ∈ C: those for which W ⊇ V (e), those for which W^{c} ⊇ V (e), and the rest. In the former cases let W̄ denote the element of C/π_{b}(e) that corresponds to W. We apply the balanced deletion-contraction identity of [18, Corollary III.3.3], which says that χ_{Ω}^{b}(λ) = χ_{Ω\e}^{b}(λ) − χ_{Ω/e}^{b}(λ).

If V (e) ⊆ W, then the W term of (4.1) expands to

χ_{(Ω\e):W}^{b} (1)χ_{Ω:W^{c}}^{b}(λ − 1) − χ_{(Ω/e):W̄}^{b} (1)χ_{Ω:W^{c}}^{b}(λ − 1).

But Ω: W^{c} = (Ω\e): W^{c} and also = (Ω/e): W̄^{c}, so we get

χ_{(Ω\e):W}^{b} (1)χ_{(Ω\e):W^{c}}^{b}(λ − 1) − χ_{(Ω/e):W̄}^{b} (1)χ_{(Ω/e):W̄^{c}}^{b}(λ − 1).

Similarly, the term corresponding to W for which V (e) ⊆ W^{c} transforms to

χ_{(Ω\e):W}^{b} (1)χ_{(Ω\e):W^{c}}^{b}(λ − 1) − χ_{(Ω/e):W̄}^{b} (1)χ_{(Ω/e):W̄^{c}}^{b}(λ − 1).

The term of a set W of the third type can be rewritten as

χ_{(Ω\e):W}^{b} (1)χ_{(Ω\e):W^{c}}^{b}(λ − 1).

Now applying (4.1) again, one has the right-hand side of the formula in Theorem 4.8. ■

We hope that Theorem 4.8 with λ = 0 might permit a generalization of Theorem 4.5, but we have not seen how to do that.

5. Polynomials from non-full biased graphs.

Most of the results of Section 4 were proved only when Ω was full, but by a little trick we can apply them to some non-full biased graphs, and there are variants of Theorem 4.1 that hold for others.

The little trick is that, if Q(Ω, C) = Q(Ω^{•}, C′) for some C′, then Q(Ω, C) can be treated as though Ω were full. (We want Ω^{•} rather than some other full biased graph, in part because the balanced polynomials, appearing in the right-hand side of (4.1) and in other identities, are unaffected by the presence or absence of unbalanced edges but tend to change when one alters the biased graph in other ways.) The first results characterize when this is possible, either for all C (with C′ constructed in a certain systematic way) or for a particular C. Let

U(Ω) = {X ⊆ V : b(Ω: X) = 0}.

Proposition 5.1. Given Ω and C, let D be a subset of P(V) with ∅ ∈ D. Then Q(Ω, C) = Q(Ω^{•}, D) if and only if D = C ∪ U(Ω)^{∗c}.

Proof. It is clear that LatΩ = Q(Ω^{•}, U(Ω)^{∗c}). It follows that Q(Ω, C) = Q(Ω^{•}, U(Ω)^{∗c}∪C). Evidently D must contain U(Ω)^{∗c} and C if Q(Ω^{•}, D) is not to have extra flats; meanwhile, it cannot contain any more than C ∪ U(Ω)^{∗c} or it will have too few flats. ■

Proposition 5.1 shows what the form of D ought to be. The hitch is that U(Ω)^{∗c} may not be a simplicial complex. Then C′ = C ∪ U(Ω)^{∗c} may not be a simplicial complex so (4.1) may fail. Thus we want to know when C′ is a simplicial complex; but that may depend on C, so we also want to know when C′ is a simplicial complex for every C —that is, when U(Ω)^{∗c} itself is a simplicial complex.

Proposition 5.2. Let Ω be a simply biased graph. U(Ω)^{∗c} is a simplicial complex if and only if

(a) every u ∈ U(Ω) and w ∈ U(Ω)^{c} are adjacent, and

(b) for every unbalanced digon or induced unbalanced polygon C in Ω: U(Ω)^{c} and every vertex w ∈ U(Ω)^{c}\V (C), there is an edge from w to a vertex of C.

Proof. U(Ω)^{∗c} is an order ideal ⟺ each induced subgraph Ω: W that has a balanced component is balanced ⟺

(c) for each balanced, connected Ω: W and unbalanced, connected Ω: X with X∩W = ∅, there is an edge between X and W.

This last condition implies (a) and (b). Conversely, suppose (a) and (b) and let W and X be as in (c). Pick w ∈ W and either an unbalanced edge at a vertex u ∈ X, if possible, or a vertex-minimal unbalanced polygon C in Ω: X. C must be an induced polygon or a digon. Therefore in either case there is an edge between w ∈ W and a vertex in X. ■

Corollary 5.3. U(Ω)^{∗c} is a simplicial complex if Ω is complete. ■

Let Ñ(y) = {z ∈ V \y : z is not adjacent to y}.

Proposition 5.4. Given Ω and C, C ∪ U(Ω)^{∗c} is a simplicial complex if and only if C contains V_{0}(Ω: Ñ(y)) for every y ∈ U(Ω)^{c}.

Proof. Let A be the class of sets X ∈ U(Ω)^{∗} that are subsets of sets in U(Ω)^{∗c}. Call X critical if it is maximal in A. Evidently, for C′ = C ∪ U(Ω)^{∗c} to be a simplicial complex it is necessary and sufficient that C contain every critical set.

It is clear that, if w ∉ U(Ω), then V_{0}(Ω: Ñ(w)) ∈ A.

Suppose X is critical and W is a minimal superset of X in U(Ω)^{∗c}. Thus W = X ∪ {y}, b(Ω: X) = 0, and b(Ω: W) > 0. Therefore Ω: W = (Ω: X) ∪· (Ω: {y}) and y ∉ U(Ω). It follows that X ⊆ V_{0}(Ω: Ñ(y)). But then X, being critical, equals V_{0}(Ω: Ñ(y)). We conclude that the critical sets are the maximal sets of the form V_{0}(Ω: Ñ(y)) where y ∈ U(Ω)^{c}. ■

Example 5.1. Let us apply this theory to Ω = [𝔊Δ^{(U)}] where Δ is a simple graph of order n, 𝔊 is a nontrivial group, and U ⊆ V = V (Δ).

Here U(Ω) = U and U(Ω) = {X ⊆ V : Ω: X has no isolated vertices in U^{c}}. Also, Ñ(y) is the same in Δ as in Ω, and V_{0}(Ω: Ñ(y)) = Ñ(y)\{z ∈ Ñ(y)\U : z is isolated in Δ: Ñ(y)}. This makes the application of Proposition 5.4 obvious.

Let Δ_{1}∨Δ_{2} denote the join of graphs: the disjoint union together with all edges between Δ_{1} and Δ_{2} . It is an exercise to deduce from Proposition 5.2 that U(Ω)^{∗c} is a simplicial complex if and only if Δ = (Δ: U) ∨ K_{n_{1}}^{c} ∨ K_{n_{2}}^{c} ∨ ⋯ ∨ K_{n_{l}}^{c}, where Δ: U is any simple graph on vertex set U, l ≥ 0, and n_{1} + n_{2} + ⋯ + n_{l} = |U^{c}|.

When computing the right-hand sides of (4.1) and (4.2), etc., keep in mind Formula (2.4). ■

A weaker version of Theorem 4.1 can be stated for all biased graphs that come from gain graphs Φ with finite gain group 𝔊. Let M = |𝔊| as usual. For λ = kM + 1 and W ⊆ V , let ξ_{Φ,W} (λ) be the number of proper k -colorings γ of Φ: W^{c} such that γ^{−1}(0) is nonadjacent to W.

Lemma 5.5. Given Φ with gain group 𝔊 and W ⊆ V . Let Φ_{1} be a 𝔊-gain graph on vertex set V_{1} = W^{c} ∪ {v_{0}}, where v_{0} ∉ V , such that Φ_{1}: W^{c} = Φ: W^{c}, v_{0} supports no unbalanced edge, and a vertex v ∈ W^{c} is adjacent to v_{0} in Φ_{1} if and only if it is adjacent to a vertex of W in Φ. (The gains on edges vv_{0} are arbitrary.) Let Φ_{2} be Φ_{1} with an unbalanced edge attached to v_{0} . Then

ξ_{Φ,W} (λ) = χ_{Φ_{1}}(λ) − χ_{Φ_{2}}(λ)

for all λ of the form Mk + 1 with k ∈ ℕ.

The proof is straightforward. ■

Consequently, ξ_{Φ,W} (λ) is a polynomial in λ and we can evaluate it, for example, at λ = 0.

Theorem 5.6. If Φ is a gain graph whose gain group is finite of order M, then

p_{Q̃(Φ,C)}(λ) = χ_{Ω}(λ) + ∑_{W ∈C^{∗}∩U(Φ)}χ_{Φ:W}^{b} (1)ξ_{Φ,W} (λ),  (5.1)

and if V ∉ C and E = ˆ1 has height n in Q(Φ, C), then

μ_{Q̃(Φ,C)}(ˆ0, ˆ1) = μ_{Lat Φ}(ˆ0, ˆ1) + ∑_{W ∈C^{∗}∩U(Φ)}χ_{Φ:W}^{b} (1)ξ_{Φ,W} (0).  (5.2)

Proof. We adapt the coloring proof of Theorem 4.1. Let λ = kM + 1 where k ∈ ℕ. The crucial difference is in (4.5) for balanced A. Instead of that formula we get an expression in terms of ξ.

Let A be a balanced flat in Lat Φ. Then

f(A) = λ^{b(A)} − ∑_{\begin{matrix}A′≥A \\ V_{0}A′∈C^{∗} \end{matrix}}(# of k -colorings κ of Φ with I(κ) = A′).

Thus after inverting (4.4), rather than (4.6) we get

g(∅) = pQ̃(λ) − ∑ ∑_{A≤A′}_{V_{0}A=∅,V_{0}A′∈C^{∗}}μ(∅, A)(# of κ with I(κ) = A′)

= pQ̃(λ) − ∑_{W ∈C^{∗}} ∑_{\begin{matrix}A′∈LatΦ \\ V_{0}A′=W \end{matrix}}χ_{Φ|A′}^{b}(1)(# of κ with I(κ) = A′).

We may write A′ as (E: W) ∪ A′_{1} where A′_{1} ∈ Lat^{b}(Φ: W^{c}). If A′_{1} ≠ ∅, then χ_{Φ|A′}^{b}(1) = χ_{Φ:W}^{b} (1)χ_{(Φ:W^{c})|A′_{1}}^{b}(1) and, because A′_{1} is balanced, χ_{(Φ:W^{c})|A′_{1}}^{b}(1) = χ_{(Γ:W^{c})|A′_{1}}(1) = 0, where Γ is the underlying graph of Φ. Consequently

g(∅) = pQ̃(λ) − ∑_{\begin{matrix}W ∈C^{∗} \\ b(Φ:W)=0 \end{matrix}}χ_{Φ:W}^{b} (1)(# of κ with I(κ) = E: W).  (5.3)

Now, a coloring κ that is counted here must be 0 on W, because b(Φ: W) = 0, and can be any proper k -coloring on W^{c} except that it may not color a vertex 0 that is adjacent to a vertex in W. Hence the quantity in parentheses in (5.3) equals ξ_{Φ,W} (λ). Since g(∅) = χ_{Φ}(λ), we have (5.1) for λ = kM + 1.

Being a polynomial identity, (5.1) therefore holds good for all numbers λ. Setting λ = 0 and observing that, if h(E) = n then r(E) = n so χ_{Φ}(0) = μ_{Q}(ˆ0, ˆ1), we get (5.2). ■

The question is: what is ξ_{Φ,X}(λ)? If we can evaluate it we have a formula for pQ̃(λ). Lemma 5.5 can provide one means of evaluation. Lemmas 5.7 and 5.8 provide others. Lemma 5.7. Given Φ with gain group of finite order M, λ = kM + 1 where k ∈ ℕ, and W ⊆ V , we have:

(a) χ_{Φ:W^{c}}^{b}(λ − 1) ≤ ξ_{Φ,W} (λ) ≤ χ_{Φ:W^{c}}(λ),

(b) ξ_{Φ,W} (λ) = the upper bound ⇔ U(Ω)^{c}\W is nonadjacent to W,

(c) ξ_{Φ,W} (λ) = the lower bound ⇔ every v ∈ U(Ω)^{c}\W is adjacent to every vertex in

W. Proof. Straightforward. ■ Lemma 5.8. Let Φ have finite gain group. A necessary and sufficient condition that ξ_{Φ,W} (λ) = χ_{Φ:W^{c}}^{b}(λ − 1) for all W ∈ C^{∗} is that each v ∈ supp C be adjacent to every vertex in U(Ω)^{c}\{v}. Proof. Easy, using Lemma 5.7(c). ■ Corollary 5.9. If Φ has finite gain group and satisfies the property in Lemma 5.8, for instance if it is complete, then

p_{Q̃(Φ,C)}(λ) = χ_{Φ}(λ) + ∑_{W ∈C^{∗}∩U(Φ)}χ_{Φ:W}^{b} (1)χ_{Φ:W^{c}}^{b}(λ − 1). ■

Let us compare this with the formula obtained from Proposition 5.2 or 5.4. If we employ (2.3a) to expand χ_{Φ}(λ) in terms of balanced chromatic polynomials, Corollary 5.9 takes the form

p_{Q̃(Φ,C)}(λ) = ( ∑_{W ∈C∪U(Φ)} + ∑_{\begin{matrix}W ≠∅ \\ stable \end{matrix}}) χ_{Φ:W}^{b} (1)χ_{Φ:W^{c}}^{b}(λ − 1).

That is rather different from what we get by setting Q̃(Ω, C) = Q̃(Φ^{•}, C ∪U(Φ)^{∗c}) in (4.1).

6. Examples.

We shall investigate the posets associated with several types of indexing complexes. In the first example, as a foretaste of the general ones to follow, for each type of complex we examine Q(𝔊K_{n}^{•}, C). Most of the examples show instances of a curious root-shifting phenomenon that we discuss briefly in the next section.

Throughout this section Ω will be a full biased graph.

Example 6.1. We take Ω = [𝔊K_{n}^{•}] so that, as usual denoting by M the order of the group,

p_{Lat Ω}(λ) = χ_{Ω}(λ) = (λ − 1)_{n,M},  (6.1a)

whose roots are

1, M + 1, …, (n − 2)M + 1, (n − 1)M + 1.  (6.1b)

We write Q = Q(Ω, C), which equals Q̃(Ω, C) since by Corollary 3.10 the extrinsic grading r is the actual rank function. Note that the statement and proof of Theorem 1.1 remain valid even when 𝔊 is not a cyclic group.

Example 6.1A. For our first instance we take C to be an m-point 0-dimensional complex C_{m}, say C_{m} = {∅, {i} : n − m < i ≤ n}, and we assume M ≥ 2. Here Q is the geometric lattice Lat 𝔊K_{n}^{(n−m)} , where 𝔊K_{n}^{(n−m)} is 𝔊K_{n}^{•} with the unbalanced edges removed from vertices n − m + 1, n − m + 2, …, n. Geometrically, if 𝔊 = ℤ_{M}, Q is the lattice of flats spanned by the subsystem of B_{n}(M) defined by D_{n}^{(n−m)}(M) = {u_{1}, …, u_{n−m}} ∪ D_{n}(M), which as m varies generates a chain of geometric lattices interpolating between D_{n}(M) and B_{n}(M). The characteristic polynomials are easy to calculate: from Theorem 1.1 we get

\begin{aligned}p_{Q}(λ) & = (λ − 1)_{n,m} + m(λ − 1)_{n−1,M} \\ & = (λ − 1)_{n−1,m}(λ − (n − 1)M − 1 + m). \end{aligned}

So the characteristic roots of D_{n}^{(n−m)}(M), or of 𝔊K_{n}^{(n−m)} for any group of order M, are

1, M + 1, …, (n − 2)M + 1, (n − 1)M + 1 − m.  (6.1c)

Compare to (6.1b): the largest root is reduced by m while the others remain as they were. The characteristic polynomial of C_{m} is

p_{C_{m}}(y) = y − m,

whose one root is precisely the amount by which the largest root of Lat Ω decreases in passing to Q.

The characteristic polynomials of these “interpolating” lattices have been treated elsewhere by different methods, three of which are described in [1, Section 5], [8], and [14, Theorem 7].

Example 6.1B. Next, let C = P(X) where |X| = k < n. The characteristic roots of Q are

1, M + 1, …, (n − k − 1)M + 1, (n − k)M, …, (n − 1)M.

(This list can be deduced from Theorem 1.1; it is also a special case of Example 6.3.) The indexing complex has characteristic polynomial

p_{P(X)}(y) = (y − 1)^{k},

whose k roots all equal 1, precisely the amount by which the k largest roots of Lat Ω are decreased as we pass to Q.

Geometrically, when 𝔊 is cyclic, Q consists of those flats generated by B_{n}(M) that contain either no coordinate vector u_{i} at all or at least one u_{i} for which i ∉ X.

Example 6.1C. Now we let C = P(X_{1}) ∪ ⋯ ∪ P(X_{m}) where m ≥ 2 and the X_{i} are nonempty, pairwise disjoint subsets of [n]. Let k_{i} = |X_{i}|. Then N_{i}(C) in Theorem 1.1 equals ∑_{i=1}^{m} ( \begin{matrix}k_{i} \\ i \end{matrix} ). If k = max k_{i}, then (λ − 1)_{n−k,M} is a factor of p_{Q}(λ) so 1, M + 1, …, (n − k − 1)M + 1 are characteristic roots, but there seem to be no general further factorization and no transformation of the roots in terms of the roots of p_{C}(y) unless all k_{i} = 1, which is Example 6.1A.

This suggests that cases like those in Examples 6.1A and B are rather special. We can, though, generalize them.

Example 6.1D. Given two simplicial complexes D and D′, define D∗D′ = {A∪B : A ∈ D and B ∈ D′}. If the supports of D and D′ are disjoint, then p_{D∗D′}(y) = p_{D}(y)p_{D′}(y). Suppose C = D ∗ P(X) where X = [n − k]^{c} and D is a simplicial complex on vertex set [n − k]. Then p_{C}(y) = (y − 1)^{k}p_{D}(y). From Proposition 6.1 below we get

p_{Q}(λ) = (λ − (n − k)M)(λ − (n − k + 1)M) ⋯ (λ − (n − 1)M)p_{Q(𝔊K_{n−k}^{•},D)}(λ).

So, whatever D does to the characteristic roots of 𝔊K_{n−k}^{•}, the effect of C is to do the same to the smallest n − k roots of 𝔊K_{n}^{•} while shrinking each of the largest k by 1.

For instance, when D = ∅, C merely reduces by 1 the k largest roots. When D = C_{[m]} = {∅, {1}, …, {m}}, then in addition the k + 1^{st} largest root is lowered by m.

Example 6.2. In treating more general examples we need a certain property of a vertex which is related to modularity of coatoms in G(Ω). In a full biased graph Ω a vertex v is bias simplicial if, for any two links e_{vw} and e_{vx} from v to distinct vertices w and x, there is an edge e_{wx} forming a balanced triangle {e_{vw}, e_{vx}, e_{wx}}. For instance, in 𝔊K_{n}^{•} every vertex is bias simplicial. In 𝔊Δ^{•} a vertex is bias simplicial if and only if it is simplicial in Δ (i.e., its neighbors form a clique). From [19, Theorem 2.1] we know that E(Ω\v) is a modular flat if and only if v is bias simplicial. Then by Stanley’s factorization theorem [11, Theorem 2], provided that Ω is simply biased, we have

χ_{Ω}(λ) = (λ − d_{v})χ_{Ω\v}(λ)  (6.2a)

where d_{v} = degree of v in Ω; also,

χ_{Ω}^{b}(λ) = (λ + 1 − d_{v})χ_{Ω\v}^{b}(λ)  (6.2b)

by (2.3b) applied to (6.2a).

We call Ω a bias-simplicial extension of Ω: Y by (v_{l+1}, v_{l+2}, …, v_{n}) if Y^{c} can be ordered as (v_{l+1}, v_{l+2}, …, v_{n}) so that each v_{i} is bias simplicial in Ω_{i} = Ω: (Y ∪ {v_{l+1}, …, v_{i}}). Define

d_{i} = degree of v_{i} in Ω_{i}.  (6.2c)

Then (6.2a) and (6.2b) imply

χ_{Ω}(λ) = (λ − d_{l+1})(λ − d_{l+2}) … (λ − d_{n})χ_{Ω:Y} (λ),  (6.2d)
χ_{Ω}^{b}(λ) = (λ + 1 − d_{l+1})(λ + 1 − d_{l+2}) ⋯ (λ + 1 − d_{n})χ_{Ω:Y}^{b} (λ),  (6.2e)

as long as Ω is simply biased.

Recall from Example 6.1D the definition of D ∗ D′. As before, we are interested in examples where D′ = P(X) for X ⊆ V . Proposition 6.1. Let Ω be a full, simply biased graph and X = {v_{n−k+1}, v_{n−k+2}, …, v_{n}}. Suppose Ω is a bias-simplicial extension by (v_{n−k+1}, v_{n−k+2}, …, v_{n}) of Ω: X^{c}. Let D be a simplicial complex on vertex set X^{c} and C = D ∗ P(X). Then

p_{Q̃(Ω,C)}(λ) = (λ + 1 − d_{n−k+1})(λ + 1 − d_{n−k+2}) ⋯ (λ + 1 − d_{n})p_{Q̃(Ω:X^{c},D)}(λ),

where d_{i} is defined by (6.2c). Proof. Clearly, we may apply the case k = 1 iteratively to deduce the whole proposition. So we assume k = 1. For W ⊆ V \v_{n} we write W′ = W ∪{v_{n}} and d_{n}(W′) for the degree of v_{n} in Ω: W′.

Since v_{n} is bias simplicial in Ω it has that same property in any induced subgraph Ω: W′. Thus

p_{Q̃(Ω,C)}(λ) = ∑_{W ∈D} {χ_{Ω:W}^{b} (1)χ_{Ω:W^{c}}(λ) + χ_{Ω:W′}^{b}(1)χ_{Ω:W′^{c}}(λ)}

= ∑_{W ∈D}{[λ − d_{n}(W^{c})]χ_{Ω:W}^{b} (1)χ_{Ω:W′^{c}}(λ) + [2 − d_{n}(W′)]χ_{Ω:W}^{b} (1)χ_{Ω:W′^{c}}(λ)}

= (λ + 1 − d_{n}) ∑_{W ∈D}χ_{Ω:W}^{b} (1)χ_{Ω:W′^{c}}(λ)

= (λ + 1 − d_{n})p_{Q̃(Ω\v_{n},D)}(λ). ■

We see that, whatever may be the effect on the characteristic roots of changing Lat(Ω: X^{c}) to Q̃(Ω: X^{c}, D), our construction of C superimposes a further effect of subtracting 1 from the additional roots of Lat Ω.

Example 6.3. We get C = P(X) by taking D = {∅} in Example 6.2. So when Ω is a bias-simplicial extension of Ω: X^{c} (and assuming X ≠ V ) we have a simple root-shifting phenomenon: certain k roots of Lat Ω, namely d_{n−k+1}, …, d_{n}, are reduced by 1, while the others are unchanged.

When Ω = [𝔊K_{n}^{•}] the shifted roots are the largest ones because the degrees are given by d_{i} = Mi + 1 for all i.

Example 6.4. Take C to be the 0-dimensional complex C_{Z} = {∅, {v} : v ∈ Z} where Z ⊆ V and |Z| = m ≥ 1. Theorem 4.1 reduces to

p_{Q̃(Ω,C)}(λ) = χ_{Ω}(λ) + ∑_{v∈Z}χ_{Ω\v}(λ).  (6.4a)

If it happens that Ω^{∗}: {v, w} is unbalanced for every pair {v, w} ⊆ Z, then Q̃(Ω, C_{Z}) is the geometric lattice Lat Ω^{∗(Z^{c})} , where Ω^{∗(Z^{c})} is Ω with the unbalanced edges removed from the vertices in Z. This applies for instance to Example 6.1A and more generally to Ω = [𝔊Δ^{•}] if Z is a clique in Δ and |𝔊| ≥ 2.

Suppose every vertex in Z is bias simplicial and has degree l. Then

χ_{Ω}(λ) = (λ − l)χ_{Ω\v}(λ)

for v ∈ Z by Proposition 6.1, so (6.4a) simplifies to

p_{Q̃(Ω,C_{Z})}(λ) = \frac{λ − l + m}{λ − l}p_{Lat Ω}(λ),  (6.4b)

which we interpret as saying that a certain characteristic root of Lat Ω has been reduced by m.

Example 6.5. We combine Examples 6.3 and 6.4. Let Ω be a bias-simplicial extension of Ω: X^{c} as in Proposition 6.1 and let C = P(X) ∗ C_{Z} with C_{Z} as in Example 6.4, where ∅ ≠ Z ⊆ X^{c} and each vertex v ∈ Z is bias simplicial in Ω: X^{c} and has degree l in Ω. Let m = |Z| and k = |X|. Comparing the characteristic roots of Lat Ω and Q̃(Ω, C), we observe that each of the former’s roots d_{n−k+1}, …, d_{n} is lowered by 1, while one of the roots l is reduced by m.

Example 6.6. Now let C = P(X_{1}) ∪ P(X_{2}) ∪ ⋯ ∪ P(X_{m}) where m ≥ 2 and the sets X_{1}, X_{2}, …, X_{m} are nonvoid and mutually disjoint. Then

p_{Q̃(Ω,C)}(λ) = χ_{Ω}(λ) + ∑_{i=1}^{m} ∑_{∅⊂W ⊆X_{i}}χ_{Ω:W}^{b} (1)χ_{Ω:W^{c}}(λ),  (6.6a)

which has no obvious factorization except in one special case.

Suppose all the flats A_{i} = E: X_{i}^{c} are modular in Lat Ω and let Y = (X_{1} ∪ ⋯ ∪ X_{m})^{c}. Then A = A_{1} ∩ … ∩ A_{m} = E: Y is modular because in a geometric lattice the meet of modular flats is modular (a result due to Stanley; see [3, Proposition 3.6] and [11, Lemma 2]). By Stanley’s factorization theorem [11], the characteristic polynomial of Lat(Ω|A), which is χ_{Ω:Y} (λ), is a common factor of all terms in (6.6a), hence a factor of pQ̃(λ).

In Example 6.1C we noticed the factor (λ−1)_{n−k,M}. That is an instance of the modular factorization just discussed, because E: Y is a modular flat of Lat 𝔊K_{n}^{•} for any Y ⊆ [n]. (See [6, Theorem 4].)

7. Root shifting and other problems.

In most of the examples in Section 6 we observed that under certain circumstances characteristic roots are shifted as we pass from Lat Ω to Q̃(Ω, C). The number of shifted roots and the amount of shift in these examples are precisely the number and size of the characteristic roots of C. Why this should be so, and whether it represents a general phenomenon or an accident, we do not know.

We summarize the data. In each case the shifting is known to take place only for certain nice Ω’s.

Examples 6.1A and 6.4. The characteristic polynomial of C is y − m. We observe that one root of p_{Lat Ω}(λ) is decreased by m, the root of p_{C}(y).

Examples 6.1B and 6.3. Here p_{C}(y) = (y − 1)^{k}, which has k roots equal to 1, and k roots of p_{Lat Ω}(λ) are decreased by 1.

Examples 6.1D and 6.2. We have p_{C}(y) = (y − 1)^{k}p_{D}(y) where k = |X|, so the characteristic roots of C are those of D and k additional 1’s. The effect on the roots of Lat Ω corresponds: whatever D does to p_{Lat Ω:X^{c}}(λ), each additional root of p_{Lat Ω}(λ) suffers a decrease of 1.

Example 6.5. Here p_{C}(y) = (y − 1)^{k}(y − m), whose roots correspond to the effect of C -restriction on the characteristic roots of Lat Ω.

Examples 6.1C and 6.6. Here, if m > 1 and some k_{i} > 1, the characteristic polynomial of C has no obvious factorization and the effect of C on the characteristic roots of Lat Ω, while obscure, is probably not simply related to the roots of p_{C}(y).

Based on these examples it is hard to tell whether or not there is an interesting answer to the problem of root shifting, which we state formally as

Problem 1. Is there any theory of a relationship among the roots of χ_{Ω}(λ), p_{C}(y), and p_{Q̃(Ω,C)}(λ)?

Our work suggests other theoretical questions in addition to the root-shifting problem. There are the questions of generalizing Theorems 3.6 and 3.8 to all biased graphs, determining more completely when μ_{Q(Ω,C)}(ˆ0, ˆ1) ≥ 0 (generalizing Theorem 4.5), clarifying the relationship (if any) between pQ̃(λ) and p_{Q}(λ), and gaining more understanding of ξ_{Φ,W} (λ) in Theorem 5.6. Two broader problems are these:

Problem 2. Can one extend the construction of Q̃(Ω, C) from bias matroids of biased graphs to an arbitrary matroid M with prescribed basis V , in such a way as to generalize any of our results?

Problem 3. Can algebraic constructions that lead to the exponents of a root system be carried out more generally, either for Q(±K_{n}^{•}, C) or Q(𝔊K_{n}^{•}, C), or for Q̃(Ω, C) in general?

References 1. C. Bennett and B.E. Sagan, A generalization of semimodular supersolvable lattices. J.

Combin. Theory Ser. A 72 (1995), 209-231. MR 96i:05180.

2. E. Brieskorn, Sur les groupes de tresses [d’après V.I. Arnol’d], in Séminaire Bourbaki, 24^{e} année, vol. 1971/72 (Lecture Notes in Math., Vol. 317), Exp. No. 401, pp. 21-44, Springer-Verlag, Berlin, 1973. MR 54 #10660.

3. T. Brylawski, Modular constructions for combinatorial geometries. Trans. Amer. Math. Soc. 203 (1975), 1-44. MR 50 #9631.

4. H.H. Crapo, A higher invariant for matroids. J. Combin. Theory 2 (1967), 406-417. MR 35 #6579.

5. H.H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries. Preliminary ed. MIT Press, Cambridge, Mass., 1970. MR 45 #74.

6. T.A. Dowling, A class of geometric lattices based on finite groups. J. Combin. Theory Ser. B 14 (1973), 61-86. MR 46 #7066. Erratum, ibid. 15 (1973), 211. MR 47 #8369.

7. P. Hanlon, A combinatorial construction of posets that intertwine the independence matroids of B_{n} and D_{n}. Manuscript, 1988.

8. T. Józefiak and B.E. Sagan, Basic derivations for subarrangements of Coxeter arrangements. J. Algebraic Combin. 2 (1993), 291-320.

9. P. Orlik and L. Solomon, Combinatorics and topology of complements of hyperplanes, Inv. Math. 56 (1980), 167-189.

10. G.-C. Rota, On the foundations of combinatorial theory: I. Theory of Möbius functions. Z. Wahrsch. verw. Gebiete 2 (1964), 340-368. MR 30 #4688.

11. R.P. Stanley, Modular elements of geometric lattices, Algebra Univ. 1 (1971), 214-217. MR 45 #5037.

12. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Monterey, Calif., 1986.

13. H. Terao, Generalized exponents of a free arrangement of hyperplanes and Shepherd-Todd-Brieskorn formula, Inv. Math. 63 (1981), 159-179.

14. T. Zaslavsky, The geometry of root systems and signed graphs. Amer. Math. Monthly 88, No. 2 (February, 1981), 88-105. MR 82g:05012. Zbl. 466.05058.

15. T. Zaslavsky, Signed graphs. Discrete Appl. Math. 4 (1982), 47-74. Erratum, ibid. 5 (1983), 248. MR 84e:05095.

16. T. Zaslavsky, Signed graph coloring. Discrete Math. 39 (1982), 215-228. MR 84h:05050a.

17. T. Zaslavsky, Chromatic invariants of signed graphs. Discrete Math. 42 (1982), 287-312. MR 84h:05050b.

18. T. Zaslavsky, Biased graphs. I. Bias, balance, and gains; II. The three matroids; III. Chromatic and dichromatic invariants; IV. Geometrical realizations. J. Combin. Theory Ser. B 47 (1989), 32-52; 51 (1991), 46-72; 64 (1995), 17-88; to appear. MR 90k:05138, 91m:05056, 96g:05139.

19. T. Zaslavsky, Supersolvable frame-matroid and graphic-lift lattices. Submitted.