Supersolvable Frame-Matroid and Graphic-Lift Lattices by Thomas Zaslavsky Binghamton University Binghamton, New York 13902-6000 U.S.A.

September 4, 1992 Revised February, 2000

Abstract

A geometric lattice is a frame if its matroid, possibly after enlargement, has a basis such that every atom lies under a join of at most two basis elements. Examples include all subsets of a classical root system. Using the fact that finitary frame matroids are the bias matroids of biased graphs, we characterize modular coatoms in frames of finite rank and we describe explicitly the frames that are supersolvable. We apply the characterizations to three kinds of examples.

A geometric lattice is a graphic lift if it can be extended to contain an atom whose upper interval is graphic. We characterize modular coatoms in and supersolvability of graphic lifts of finite rank and we examine families analogous to the frame examples.

Introduction

One of the outstanding problems concerning arrangements of hyperplanes and finite matroids is to understand when and why the characteristic polynomial of the associated geometric lattice has a complete integral factorization. A sufficient condition for such a factorization, which even implies a simple combinatorial interpretation of the roots, is that the lattice be supersolvable, which means that it has a complete chain of modular flats [14, Cor. 2.3]. However, it can be hard to decide whether a particular geometric lattice is supersolvable. Here we completely settle that question for two kinds of geometric lattice which can be presented in terms of graphs.

The first kind is a geometric lattice (of finite rank) whose matroid has a basis, or can be extended to have one, such that each point lies on a line generated by a pair of basis elements. We call this a (finite-rank) frame matroid. The primary example is the matroid of a subset of a classical root system; more generally, of a subgeometry of a Dowling group geometry. One can think of a frame matroid as an abstraction of a two-term arrangement of hyperplanes: a finite set of homogeneous hyperplanes in F^{n}, each of whose equations involves at most two variables; thus x_{i} = gx_{j} or x_{k} = 0. If g ∈ {±1} and F = ℝ or ℂ, we have a subarrangement of B_{n}^{∗} = {x_{i} = ±x_{j}, x_{k} = 0 : 1 ≤ i < j ≤ n, 1 ≤ k ≤ n}, the real or complex arrangement dual to the root system B_{n}. By [18], a finitary frame matroid is the matroid of a graph with certain additional structure which I call a “bias” (to be explained in Section 1); and conversely every such “bias matroid” is a finitary frame. This representation theorem is what makes two-term arrangements and their abstraction to frame matroids relatively tractable, since it permits one to employ the rich theory of biased graphs to characterize modular copoints and supersolvability. Since an ordinary graph can be treated as a certain kind of biased graph, our theorem generalizes Stanley’s that the lattice of contractions of a graph is supersolvable if and only if the graph is chordal.

The second kind of geometric lattice is one which contains, or can be extended to contain, an atom e_{0} whose upper interval is graphic—that is, the lattice of contractions of a graph. We call this a graphic lift because it is obtained from a graphic matroid by a standard lift construction specified by a bias on the graph. Graphic lifts abstract a different kind of arrangement of hyperplanes, which we call affinographic because the defining equations have the form x_{i} − x_{j} = g, whence the hyperplanes are affine flats in F^{n}. Some types of real affinographic arrangements have been studied in [1, 9, 15] et al. Again, biased graph theory helps us to treat these arrangements and all graphic lift matroids and in particular to determine all modular copoints and supersolvable lattices of this kind.

We find that very few frame-matroid or graphic-lift lattices are supersolvable. Yet we know several families of vector sets (or dually, arrangements of hyperplanes) that correspond to frame and lift matroids whose characteristic polynomials have integral roots but which are on the whole not supersolvable: the root subsystems obtained from B_{n} by removing some coordinate vectors, for example, and generalizations; certain bicircular matroid lattices; lattices related to the semilattices of composed partitions studied in [9]; and some lift analogs. This shows that supersolvability is far from explaining integral factorization even for frame matroids. There are several broader properties of an arrangement of hyperplanes or a matroid that guarantee integral roots, such as freeness (see [11]), factorization [8, 16], and existence of an atom decision tree [3]. Why, then, characterize a comparatively weak property? The best reason is that it can be done—in considerable generality. There is no known characterization in comparable generality of any other integrality property, although it has been done for a few special types, notably graphic arrangements (subarrangements of A_{n−1}^{∗} = {x_{i} = x_{j} : 1 ≤ i < j ≤ n}); arrangements between A_{n−1}^{∗} and B_{n}^{∗}, for which freeness and supersolvability are characterized in the beautiful theorem of [7], extended to factorizability by [2]^{1}; and the projectivizations (“cones”) of arrangements between A_{n−1}^{∗} and the Shi arrangement, for which Athanasiadis characterized freeness and supersolvability in [1]. In some of these types, most of the properties that guarantee integral roots turn out to nearly coincide. That is not so in the whole class of frame matroids, but, to extend a question raised by Bailey [2], might it be true of all subarrangements of B_{n}^{∗}, i.e., of all signed graphs? This question is wide open.

1The present work, except Example 4c, and that of Edelman, Reiner, and Bailey were originally done independently, including Bailey’s independent discovery of Theorem 2.2 for signed graphs (with a longer proof). However, this report and [2] have been revised to take account of the connections.

After developing the general results we turn to three families of examples, looking for supersolvability and for nonsupersolvable cases that nonetheless have integral roots. Examples 4a and 4b include the root system D_{n} and Dowling’s group geometries. In Example 4c we obtain a mild generalization of Edelman and Reiner’s supersolvability theorem. In Example 4d we characterize the supersolvable bicircular matroids. We close with comments on algorithmics, chordality, and freeness and some open questions.

1. Biased Graphs, Matroids, Etc.

We give a quick exposition of the relevant portions of biased graph theory, from definitions through their matroids to their representations as vector sets and arrangements of hyperplanes. The source for biased graphs is [17], especially the cryptomorphic definitions of the matroids in Theorems II.2.1 (that is, Theorem 2.1 of Part II) and II.3.1 and the gain-graph and matroid invariant theory of Sections III.4 and III.5. The reader need not be acquainted with the sources in order to read this paper. 1a. Biased graphs. A biased graph Ω = (V, E, B) is a graph ||Ω|| = (V, E), not necessarily finite, together with a linear subclass B = B(Ω) of its polygons (or “circuits,” but we reserve this term for matroid circuits): a class of polygons such that, if in a theta subgraph two polygons belong to B, so does the third. In biased graph theory we find it helpful to have four kinds of edges: links (two distinct endpoints), loops (two coincident endpoints), half edges (one endpoint), and loose edges (no endpoints; the name is due to Tutte). Neither of the latter can belong to a polygon. A subgraph or edge set is balanced if it contains no half edge and any polygon in it belongs to B. It is contrabalanced if it contains no balanced polygon or loose edge. Thus a loose edge is balanced, a half edge is not, and a loop may or may not be. For matroidal purposes 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.

Several special types of biased and unbiased graphs will be needed. An ordinary graph has only links and loops. A link graph has only links. A simple graph is a link graph that contains no digons. A star S_{k} is a simple graph having k edges (where k ≥ 1), all incident to one vertex (the center). A unicycle is a connected ordinary graph having exactly one polygon. By mΓ we mean a graph Γ with every edge replaced by m copies of itself. An induced subgraph of Γ = (V, E) is Γ:W = (W, E:W) where W ⊆ V and E:W = {e ∈ E : ∅ ≠ V (e) ⊆ W }, V (e) denoting the set of endpoints of e. For W ⊆ V and S ⊆ E we write W^{c} = V \ W, S^{c} = E \ S, Γ \ W = Γ:W^{c}, and Γ|S = (V, S). W is stable if E:W = ∅. The neighborhood of v ∈ V is N(v) = {x ∈ V : x is adjacent but not equal to v\}; the complete neighborhood is \overline{N}(v) = N(v) ∪ \{v\}. We denote by ⟨Γ⟩ the biased graph whose underlying graph is Γ, in which every polygon is balanced.

In a biased graph Ω, we let U(Ω) = {v ∈ V : v supports an unbalanced edge}. Ω is full if U(Ω) = V . We call Ω simply biased if it has no loose edges, balanced loops, balanced digons, or pairs of unbalanced edges at the same vertex. If W ⊆ V and S ⊆ E, Ω^{(W)} denotes Ω with a half edge added at each vertex in W \ U(Ω). Ω:W, Ω|S, etc., denote subgraphs of Γ with balance of polygons the same as in Ω. Similarly, Γ^{(W)} denotes a graph Γ with a half edge added to each vertex in W not already supporting one.

Two special unions are the disjoint union Ω_{1} ∪· Ω_{2} and the one-point amalgamation Ω_{1} ∪_{p} Ω_{2} , where p is a vertex of Ω_{1} and Ω_{2} and Ω_{1} ∩ Ω_{2} = {p}. In each case the balance of a polygon is the same as in Ω_{1} or Ω_{2} , whichever it is that contains the polygon. 1b. Gain graphs. In the examples we need gain graphs, which for our purposes can be defined in the following way (simplified from [17, Sect. III.4]). Take a group 𝔊. On the vertex set [n] = {1, 2, …, 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}. Adding a half edge to each of p vertices gives 𝔊K_{n}^{(p)} . We call g the gain of (i, j; g) in the direction from i to j and we write φ_{n}(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}^{(p)}⟩. A gain graph Φ = (V, E, φ) with gain group 𝔊 and gain function φ is any subgraph of 𝔊K_{n}^{(n)} , φ being the restriction to E of φ_{n}; ⟨Φ⟩ denotes the corresponding biased graph. We call 𝔊K_{n} the 𝔊-expansion of K_{n} and 𝔊K_{n}^{(n)} the full 𝔊-expansion. When n ≤ 3 (but not if n ≥ 4) the construction works for any quasigroup 𝔊.

Switching Φ by a function τ : V → 𝔊 means changing the gain of each link or loop from ϕ(i, j; g) = g to ϕ^{τ} (i, j; g) = τ(i)^{−1}gτ(j). Switching preserves the balance or imbalance of polygons, hence ⟨Φ^{τ} ⟩ = ⟨Φ⟩.

A signed graph Σ is a gain graph whose group is the sign group {+, −}. We write E_{+} and E_{−} for the sets of positive and negative edges and Σ_{+} , Σ_{−} for the corresponding spanning subgraphs. N_{+}(v) and N_{−}(v) denote the neighborhoods of v in Σ_{+} and Σ_{−}. We write ±K_{n} for the sign-group expansion of K_{n}. Switching a vertex x in Σ means reversing the sign of every link at x. Switching X ⊆ V (E) means switching each vertex in X in turn. Switching does not change ⟨Σ⟩ or, consequently, any of the matroids we will define on ⟨Σ⟩. 1c. Matroids. For matroid theory and notation we mainly follow [12]. However, we write E(M) for the point set of a matroid M, S^{c} for E(M) \ S if S ⊆ E(M), and M/S for the contraction of M by S. The rank function is r_{M} or simply r. The lattice of closed sets is Lat M. Two fundamental if elementary properties of modular elements of Lat M are that a copoint A of M is modular iff it is not disjoint from any line, and that M (to be precise, Lat M) is supersolvable iff it has a modular copoint A such that M|A is supersolvable. (See for example [4, Cor. 3.4 and Prop. 3.5].) 1d. The bias matroid. A handcuff is a connected graph (or its edge set) having exactly two polygons and no monovalent vertices (a half edge counting as a loop here); it is tight if all its edges lie in the polygons. The bias matroid G(Ω) is the matroid on E whose circuits are the bias circuits: the balanced polygons, loose edges, and contrabalanced handcuffs and thetas. For S ⊆ E let V (S) = the set of endpoints of edges in S and let b(S) = the number of connected components of (V (S), S) which are balanced. Then the rank of S in G(Ω) is r(S) = |V (S)| − b(S). If Γ has no loose or half edges, then G(⟨Γ⟩) = G(Γ), the usual polygon matroid of Γ.

Bias matroids are just a graph-theoretic way of presenting finitary frame matroids. In particular, suppose Φ ⊆ 𝔊K_{n}^{(n)} is a gain graph whose gain group is a subgroup of F^{∗}, the multiplicative group of a field (or skew field) F. Then G(Φ) (i.e., G(⟨Φ⟩), but we omit the angle brackets) has a standard vector representation over F: the vector space is F^{n} with standard basis b_{1}, …, b_{n} and an edge e = (i, j; g) is represented by x(e) = b_{i} − gb_{j}. (Thus x(e^{−1}) = b_{j} − g^{−1}b_{i} = −g^{−1}x(e). Either of these vectors serves equally well in representing the matroid.) If e is a loose edge we define x(e) = 0; for a half edge at vertex i, x(e) = b_{i}. The linear dependence matroid of x(Φ) = {x(e) : e ∈ E} equals G(Φ) [17, Thm. IV.2.1].

Dually, let x^{∗}(e) be the dual hyperplane in F^{n}, so x^{∗}(Φ) is an arrangement of hyperplanes. Each hyperplane equation has the form x_{i} = gx_{j} (where i ≠ j, g ≠ 0) or x_{i} = 0. It is these two-term arrangements of hyperplanes that are represented by bias matroids of gain graphs and abstracted by frame matroids and biased graphs. For example, let 𝔊 = {+, −} and F = ℝ or ℂ. Then x(Φ) = B_{n}, the root system, if we take Φ = ±K_{n}^{(n)} , or D_{n} if Φ = ±K_{n}, or an arbitrary subset of B_{n} if we take a suitable Φ ⊆ ±K_{n}^{(n)} . Hence we have, in Theorem 2.2 below with Ω = ⟨Φ⟩ ⊆ ⟨±K_{n}^{(n)}⟩, a graphical characterization of the supersolvable subsets of B_{n} and dually of those of the hyperplane arrangement B_{n}^{∗}.

Scaling an arrangement in F^{n} means replacing each coordinate variable x_{i} by a nonzero scalar multiple τ(i)x_{i}, or equivalently, transforming F^{n} by an invertible diagonal matrix. Scaling a two-term arrangement x^{∗}(Φ) is equivalent to switching Φ by 1/τ.

If A_{1} and A_{2} are homogeneous arrangements in F^{n} and codim ⋂(A_{1}∪A_{2}) = codim (⋂ A_{1})+ codim (⋂ A_{2}), we say A_{1} ∪ A_{2} is the direct sum of A_{1} and A_{2} . 1e. The lift matroids. A broken handcuff is the union of two vertex-disjoint polygons. (It is not a handcuff. Again, a half edge counts as a loop.) The extended lift matroid L_{0}(Ω) is the matroid on E_{0} = E ∪ e_{0} , where e_{0} is a new element called the extra point, whose circuits are the lift circuits: balanced polygons, loose edges, contrabalanced tight and broken handcuffs and thetas, and sets C ∪ e_{0} where C is an unbalanced polygon or a half edge. The lift matroid L(Ω) is L_{0}(Ω)\e_{0} . We call S ⊆ E_{0} balanced if S is a balanced edge set. Letting c(S) be the number of connected components of (V (S \ e_{0}), S \ e_{0}), the rank function in the lift and extended lift is r_{0}(S) = |V (S\e_{0})|−c(S)+ϵ(S) where ϵ(S) = 0 if S is balanced, 1 otherwise. If Γ has no loose or half edges, L(⟨Γ⟩) = G(⟨Γ⟩) = G(Γ), the polygon matroid.

Suppose now that Φ ⊆ 𝔊K_{n}^{(n)} where 𝔊 ⊆ F^{+} , the additive group of a field (or skew field). Then L_{0}(Φ) has a standard representation in F^{1+n} (with standard basis b_{0}, b_{1}, …, b_{n}): an edge e = (i, j; g) corresponds to the vector z(e) = gb_{0} − b_{i} + b_{j}; a half edge or the extra point e = e_{0} corresponds to z(e) = b_{0} , and a loose edge e has z(e) = 0. The linear dependence matroid of z(Φ) = {z(e) : e ∈ E} equals L(Φ), and that of z_{0}(Φ) = z(Φ) ∪ {z(e_{0})} naturally equals L_{0}(Φ) [17, Thm. IV.4.1].

Dually, we regard z^{∗}(Φ) and z_{0}^{∗}(Φ) as affine hyperplane arrangements in F^{n}. Then z^{∗}(e) has equation x_{i} − x_{j} = g if e = (i, j; g), while a half edge or the extra point corresponds to the infinite hyperplane H_{∞} and therefore does not appear in the affine hyperplane representation A. However, we cannot ignore it entirely. The projectivization of A is the arrangement A_{ℙ} = A ∪ {H_{∞}} in ℙ^{n}(F). Note that switching the associated gain graph by τ corresponds to a translation, replacing x_{i} by x_{i} + τ(i).

An affine arrangement A_{1} ∪ A_{2} is the direct sum of A_{1} and A_{2} if r(A_{1}) + r(A_{2}) = r(A_{1} ∪ A_{2}), where r(A) = max{codim S : S is a nonempty intersection flat of hyperplanes of A}. For homogeneous arrangements this specializes to the definition in Section 1d. It entails that A_{1} and A_{2} are disjoint. 1f. Coloring and polynomials. A 1-coloring of Φ is a mapping c : V → 𝔊 ∪ {ˆ0} where ˆ0 ∉ 𝔊. It is proper if c^{−1}(ˆ0) is stable and for all edges (i, j; g) ∈ E with i, j ∉ c^{−1}(ˆ0) we have c(j) ≠ c(i)g. If Φ and 𝔊 are finite there is a polynomial χ(λ) associated with Φ, called the chromatic polynomial, which has the property that χ(|𝔊| + 1) is the number of proper 1-colorings of Φ. Furthermore, λ^{−b(E)}χ(λ) = p_{G}(λ), the characteristic polynomial of G(Φ) [17, Thm. III.5.1]. For the zero-free chromatic polynomial χ^{∗}(λ) we set χ^{∗}(|𝔊|) is the number of proper 1-colorings not using the color ˆ0. (If 𝔊 ⊆ F^{+} , χ^{∗} is the characteristic polynomial of the affinographic arrangement z(Φ) [17, Thm. III.5.3 and Sect. IV.4].) If Φ is full, then χ^{∗}(λ) = χ(λ + 1) = p_{G}(λ + 1); and more generally,

(1.1)  p_{G}(λ + 1) = χ_{Φ}(λ + 1) = ∑_{\begin{matrix}X⊆V \\ stable \end{matrix}} χ_{Φ\X}^{∗}(λ)

[17, Thm. III.6.1]. For an arbitrary finite biased graph there are algebraic definitions of χ and χ^{∗} which yield the same identities; see especially [17, Sects. III.3 and III.6] but there is no easy way to evaluate the polynomials without coloring theory.

If Ω is a finite, connected biased graph, the characteristic polynomial of L_{0}(Ω) is

(1.2)  p_{L_{0}}(λ) = λ^{−1}(λ − 1)χ^{∗}(λ) = λ^{−1}(λ − 1)p_{G(Ω^{(V )})}(λ + 1).

We see that the roots of p_{L_{0}(Ω)}(λ) are those of p_{G(Ω^{(V )})}(λ) decreased by one, except that the root 1 remains unchanged. If Ω is also a link graph and is unbalanced, the characteristic polynomial of L(Ω) is (from [17, Thm. III.5.2])

(1.3)  p_{L}(Ω) = p_{L_{0}}(λ) + λ^{−1}χ_{||Ω||}(λ).

2. Frames

In a biased graph Ω a vertex v is bias simplicial if

(s1) for each pair of edges, e and f, from v to distinct neighbors x and y, there is an

xy edge which completes a balanced triangle; (s2) for each unbalanced digon at v, the other endpoint is in U(Ω); and (s3) if v is in U(Ω) then every neighbor is in U(Ω).

We call v link simplicial if it satisfies (s1) and simplicial if it is link simplicial and the set E(v) of edges incident with v is balanced (that is, there is no unbalanced digon at v, and v ∉ U(Ω)). In a balanced graph ⟨Γ⟩ a simplicial or link or bias-simplicial vertex (in the biased sense) is the same as a simplicial vertex of Γ (in the ordinary sense).

We restate the conditions to apply to a gain graph Φ: (s1′) whenever there are edges e = (v, x; g) and f(v, y; h) with x ≠ y, there is an edge (x, y; g^{−1}h); (s2′) whenever there are edges (v, x; g) and (v, x; h) with g ≠ h, there is an unbalanced loop or half edge at x; (s3′) if v supports an unbalanced loop or half edge, so does every neighbor.

Theorem 2.1. Let Ω be a connected, simply biased graph. A subset A ⊆ E is a modular copoint of G(Ω) if and only if Ω and A are of one of the following types.

(1) Ω is a one-point amalgamation Ω_{1} ∪_{v} Ω_{2} , where Ω_{2} is balanced and v is a biassimplicial vertex in Ω_{1} ; and A = (E_{1}:{v}^{c}) ∪ E_{2} .

(2) Ω = ⟨Γ⟩^{(U)} where Γ is connected and U is a nonempty clique in Γ; and A = E(Γ).

(3) Ω = ⟨Γ⟩ ∪ (mK_{2}, ∅)^{(U)} where Γ is connected, m ≥ 2, U ⊆ V (K_{2}), and one link of the mK_{2} is in Γ; and A = E(Γ).

(4) Ω = ⟨Σ⟩ where Σ is a connected signed link graph, E_{−} is a triangle parallel to a triangle of positive edges; and A = E_{+} .

(5) Ω = ⟨Σ⟩ where Σ is a connected signed link graph, E_{−} is a star of one or more edges centered at a vertex v, N_{−}(v) is a clique; and A = E_{+} .

(6) Ω = ⟨Σ⟩^{(v)} where Σ and A are as in (5) and furthermore N_{−}(v) ⊆ N_{+}(v).

I regard the first kind of modular copoint as the normal one; the others are exceptional cases.

Proof. We may assume G(Ω) is connected and unbalanced. (The balanced case is known from [13, Thm. 3].)

First, we need a catalog of all types of line Λ in G(Ω). It is easy to produce one because b(Λ) ≤ 2.

(a) Contrabalanced, order 2. Λ = E:{x, y}, where |E:{x, y}| ≥ 2. This line is (mK_{2}, ∅)^{(U)} with m + |U| ≥ 2.

(b) Partly balanced, order 3. Λ = M_{1 \frac{1}{2}} := E(K_{2} ∪ K_{1}^{(v)}), that is, a link and an unbalanced edge at a third vertex.

(c) Balanced, order 3 or 4. Here there are three kinds of Λ. (i) ⟨C_{3}⟩, a balanced triangle. (ii) A proper angle A_{2} := two links having one common vertex and not contained in a ⟨C_{3}⟩. (iii) M_{2} := E(K_{2} ∪· K_{2}), a two-edge matching.

Next, we need the description of copoints in [17, Thm. II.2.1(h)]. There are two kinds of copoints: a maximal balanced edge set A, and an unbalanced edge set of the form A = E:Y^{c} ∪ A_{Y} where ∅ ⊂ Y ⊂ V , b(Ω:Y^{c}) = 0, (Y, A_{Y}) is connected, and A_{Y} is a maximal balanced edge set in Ω:Y .

In the former case we see from lines of types M_{2} and M_{1 \frac{1}{2}} that A^{c} can contain no two vertex-disjoint edges except a pair of unbalanced edges, which, due to lines of order 2, must be at vertices which are adjacent in A. If A^{c} contains no links, A has type (3). Otherwise A has type (4), (5), or (6). The details are routine.

Suppose now that A is the second kind of copoint. Since the set D of edges between Y and Y^{c} can contain no M_{2} , we have |Y | = 1 or Ω = Ω_{1} ∪_{p} Ω_{2} where Ω_{1} and Ω_{2} ⊂ Ω, Y ⊆ V (Ω_{1}), Y^{c} ⊆ V (Ω_{2}), and any unbalanced edge at p is in Ω_{2} . It is easy to see that, if |Y | = 1, say Y = {y} (so A = E:{y}^{c}), then y is bias simplicial. We show that |Y | > 1 is impossible.

We show first that when a point p exists, Ω_{1} is balanced. Take p ∈ Y if possible. (Note that p is not uniquely determined if D is incident with only two vertices.) Let e ∈ D. If p ∉ Y , let f ∈ D, not parallel to e. Then M_{1 \frac{1}{2}} shows that no vertex of Y \ V (e) (or Y \ V (f), if p ∉ Y) can support an unbalanced edge. Thus Ω_{1} has no unbalanced edges. Suppose A^{c}:Y contained a link g. Then eg would be an M_{2} or A_{2} or else p ∉ Y and eg would be in a ⟨C_{3}⟩ at p, so we would have a line disjoint from A, which contradicts the hypothesis. We conclude that E(Ω_{1}) = A_{Y} , whence Ω_{1} is balanced.

But then G(Ω) is the direct sum of G(Ω_{1}) and G(Ω_{2}), contrary to assumption. ■

Now we can characterize supersolvable frame matroids of finite rank. A bias-simplicial vertex ordering (briefly, b.s.v.o.) of a biased graph Ω of finite order is a linear ordering of the vertices, say (v_{1}, v_{2}, …, v_{n}), such that each v_{i} is bias simplicial in Ω:{v_{1}, …, v_{i}}. A link-simplicial vertex ordering (l.s.v.o.) is similar. If Ω is balanced we call this a simplicial vertex ordering (s.v.o.); in reverse order it is a perfect vertex elimination scheme of ||Ω|| [10, Sect. 4.2]. We call Ω a simplicial [or, bias- or link-simplicial] extension of Ω_{0} if Ω_{0} is an induced subgraph of Ω and V (Ω_{0})^{c} can be linearly ordered, say (w_{1}, …, w_{k}), so that each w_{i} is simplicial [or, bias or link simplicial] in Ω:(V (Ω_{0}) ∪ {w_{1}, …, w_{i}}). Incidentally, in a b.s.v.o. any vertex v ∉ U(Ω) must follow all its neighbors that are in U(Ω). Consequently, any b.s.v.o. can be rearranged so that U(Ω) is an initial segment.

For an ordinary graph Γ Stanley proved that Lat G(Γ) is supersolvable if and only if Γ is a chordal (“triangulated”, “rigid-circuit”) graph [14, Prop. 2.8]. A good reference for chordal graphs is [10, Sect. 4.2]. We mention especially Dirac’s lemma (see [10, Lemma 4.2]) that a chordal graph is complete or has a pair of nonadjacent simplicial vertices and the consequence that a graph is chordal if and only if it has a simplicial vertex ordering (from which Stanley’s theorem follows easily).

Theorem 2.2. Let Ω be a simply biased graph of finite order. G(Ω) is supersolvable if and only if each connected component of Ω either

(i) has a bias-simplicial vertex ordering, or (ii) is a simplicial extension of one of (a) (mK_{2}, ∅), where m ≥ 2, or

(b) ⟨±K_{3}⟩, or

(c) ⟨Σ⟩ for Σ = +Γ ∪ −S_{k}, where Γ is a chordal simple graph of finite order, S_{k} is a k -edge star whose vertex set lies in V (Γ), and the noncentral vertices of S_{k} are a clique in Γ.

Furthermore, the bias-simplicial vertex ordering (or, simplicial extension) can be chosen so that any desired bias-simplicial (or, simplicial) vertex is the last vertex.

An alternate description of Σ in (ii)(c) is as (+Γ_{0} ∪ −e)/(−e) where Γ_{0} is a chordal simple graph of finite order and e is a link whose endpoints are not adjacent in Γ_{0} .

If we have a gain graph Φ ⊆ 𝔊K_{n}^{(n)} instead of an abstract biased graph Ω, we can restate some of Theorem 2.2. Part (ii)(b) becomes: a gain subgraph of 𝔊K_{3} obtained by switching {1, g}K_{3} where g is an involution in 𝔊. Part (ii)(c) becomes: a gain graph with gain group 𝔊 obtained by switching from 1Γ ∪ gS_{k}, where g ∈ 𝔊, g ≠ 1, gS_{k} denotes S_{k} with every edge given gain g in the orientation away from the central vertex, and Γ and S_{k} are as before.

Proof. Sufficiency is clear by Theorem 2.1 and the properties of modular flats cited in Section 1c.

For necessity we have only to clear up some technicalities. We may assume Ω is connected and unbalanced. We proceed by induction on the order. A supersolvable G(Ω) has a modular copoint A such that G(Ω)|A is supersolvable. Consequently Ω and the modular copoint A_{n−1} are as described in Theorem 2.1.

Let us take up first the exceptional cases (2)–(6). Here Γ = (V, A) is balanced, hence chordal by Stanley’s theorem. By Dirac’s lemma Γ is K_{n} or has two nonadjacent simplicial vertices. It is easy to deduce that Ω has a b.s.v.o. in cases (2), (3) when U ≠ ∅, and (6). In cases (3) with U = ∅ and (4), if Ω ≠ Ω_{0} := (mK_{2}, ∅) or ⟨±K_{3}⟩, respectively, then Γ has a simplicial vertex v ∉ V (Ω_{0}). Then v is clearly simplicial in Ω, so it can be eliminated; by induction, Ω is a simplicial extension of Ω_{0} . As for case (5), here Ω is as in case (ii c).

Now consider case (1). Here G(Ω) = G(Ω_{1}) ⊕ G(Ω_{2}); thus G(Ω) is supersolvable if and only if G(Ω_{1}) and G(Ω_{2}) are so. Ω_{2} , being balanced, has a simplicial vertex ordering, in which one can choose the first vertex to be v (because a chordal graph has at least two simplicial vertices; see [10, p. 82]). Ω_{1} is a bias-simplicial extension of Ω_{1}:{v}^{c}. Thus Ω itself is a bias-simplicial extension of Ω_{1}:{v}^{c}. By successively eliminating biassimplicial vertices we will either find a b.s.v.o. or express Ω as a bias-simplicial extension of a supersolvable Ω_{0} which has no bias-simplicial vertex. But then by induction Ω_{0} is one of (mK_{2}, ∅), ⟨±K_{3}⟩, or ⟨+Γ ∪ −S_{k}⟩ where Γ is chordal. It is easy to see that a bias-simplicial extension of such an Ω_{0} is a simplicial extension. Therefore the theorem is proved. ■

Clearly, if G(Ω) is supersolvable, then so is G(||Ω||) unless Ω is as in (ii) (c). However, we can say more. Let ||Ω||_{0} be the graph obtained from Ω through replacing unbalanced loops and half edges by links to a new vertex v_{0} , then taking the underlying unbiased graph and eliminating loops and multiple edges.

Corollary 2.3. If G(Ω) is supersolvable, then ||Ω||_{0} is chordal or Ω falls under case (ii)

(c) of Theorem 2.2. ■

Now, the geometry of Theorem 2.2. Let A be a two-term arrangement of hyperplanes in F^{n} and U the set of coordinates i for which x_{i} = 0 is in A. Call a coordinate i transitive if (i) whenever it participates in hyperplanes x_{i} = gx_{j} and x_{k} = hx_{i} (where i, j, k are distinct; and we always tacitly assume g, h ≠ 0), then A has a hyperplane x_{k} = hgx_{j}; (ii) the same, if k = j ≠ i and hg ≠ 1 (whence x_{k} = hgx_{j} is the coordinate hyperplane x_{j} = 0); and (iii) if A contains x_{i} = 0 and x_{i} = gx_{j}, then it contains x_{j} = 0. Call i strictly transitive if it is transitive, x_{i} = 0 is not in A, and for each j ≠ i, there is at most one hyperplane equation involving both x_{i} and x_{j}. Let A_{(i)} = {H ∈ A : the equation of H involves only x_{1}, …, x_{i}, at most}.

Corollary 2.4. Let A be a two-term arrangement of hyperplanes in F^{n}, where F is a skew field. Then A is supersolvable if and only if it is a direct sum of arrangements B of any of the following four forms (after suitably scaling and renumbering the coordinates):

(i) B is such that each i is transitive in B_{(i)} .

(ii) Each i ≥ 3 is strictly transitive in B_{(i)} .

(iii) B consists of hyperplanes x_{i} = ±x_{j} for 1 ≤ i < j ≤ 3 and additional hyperplanes (if any) so that each i ≥ 4 is strictly transitive in B_{(i)} .

(iv) There is an r such that every coordinate i > r is strictly transitive in B_{(i)} ; B_{(r)} = B_{+} ∪ B_{−}, where B_{+} is graphic and supersolvable (i.e., its hyperplanes have equations x_{i} = x_{j} and each i ≥ 3 is strictly transitive in B_{(i)} ); B_{−} consists of hyperplanes x_{m} = g_{0}x_{i} for fixed m, fixed g_{0} ∈ F^{∗}\{1}, and all i ∈ {i_{1}, …, i_{k}} (where k ≥ 1 and no i_{j} = m); and B_{+} contains all hyperplanes x_{i_{j}} = x_{i_{l}} for 1 ≤ j < l ≤ k. ■

3. Graphic Lifts

First in our treatment of graphic lifts we ought to verify that a finitary graphic lift lattice, or matroid rather, really is the lift or extended lift of a graphic matroid. In other words we should prove that for a finitary matroid M to have a nonloop point e_{0} such that M/e_{0} is graphic, it is necessary and sufficient that M = L_{0}(Ω) for some biased graph Ω. This is implicit in [6, Sect. 6] as amplified in [17, Sect. II.3 near Thm. II.3.1]. Here is how Ω is constructed: if M/e_{0} = G(Γ), then ||Ω|| = Γ; and a polygon is unbalanced when its closure in M contains e_{0} .

To simplify the results we shall often assume that Ω is connected. We can do so because, if it is not and if one identifies just enough vertices to make it connected, the lift and extended lift matroids are not changed.

Now we state the main theorems. We leave the proofs to the reader since they are along the same lines as those for frame matroids. We may without loss of generality take Ω to be a link graph, for an unbalanced edge is parallel to e_{0} , whence Lat L(Ω) = Lat L_{0}(Ω) if Ω has any such edge.

Recall from Section 2 that a vertex v is link simplicial if any two nonparallel links at v are contained in a balanced triangle. If Ω_{1} ⊆ Ω and v ∈ V (Ω_{1}), then E_{1}(v) is the set of edges of Ω_{1} incident with v.

Theorem 3.1. Let Ω be a simply biased link graph.

(A) A subset A ⊆ E_{0} is a modular copoint in L_{0}(Ω) if and only if (1) Ω has a block Ω_{1} which has a link-simplicial vertex v, and A = E_{0} \ E_{1}(v), or

(2) Ω is balanced and A = E. (B) A subset A ⊆ E is a modular copoint of L(Ω) if and only if

(1) Ω has a block Ω_{1} which has a simplicial vertex v, and A = E \ E_{1}(v), or (2) Ω and A are as in Theorem 2.1 (3, 4, or 5). ■

Theorem 3.2. Let Ω be a simply biased, connected link graph of finite order. (A) L_{0}(Ω) is supersolvable if and only if Ω has a link-simplicial vertex ordering. (B) L(Ω) is supersolvable if and only if

(i) Ω is balanced and ||Ω|| is chordal, or

(ii) Ω is as in Theorem 2.2 (ii).

Furthermore, the link-simplicial vertex ordering (or, simplicial extension) can be chosen so that any desired bias-simplicial (or, simplicial) vertex is last. ■

Corollary 3.3. For a simply biased link graph Ω of finite order, L_{0}(Ω) is supersolvable precisely when G(Ω^{(V)}) is supersolvable. ■

This and the remark on p_{L_{0}} in Section 1f show that, for a biased graph Ω, the properties of supersolvability, and of positive integrality of characteristic roots, of L_{0}(Ω) parallel those of G(Ω^{(V)}).

For the geometric interpretation of Theorem 3.2 consider an affinographic arrangement A in F^{n} and its projectivization A_{ℙ} in ℙ^{n}(F) = F^{n} ∪ H_{∞}. Call a coordinate i in F^{n} affinely transitive in A if, whenever A has hyperplanes x_{i} − x_{j} = g and x_{k} − x_{i} = h, it has a hyperplane x_{k} − x_{j} = g + h. Call i strictly affinely transitive if, in addition, for each j ≠ i there is at most one hyperplane of the form x_{i} − x_{j} = g.

Corollary 3.4. Let A be an affinographic arrangement of hyperplanes in F^{n}, where F is a skew field.

(A) A_{ℙ} is supersolvable if and only if, after suitable translation and renumbering of coordinates, each coordinate i is affinely transitive in A_{(i)} .

(B) A_{ℙ}\{H_{∞}} is supersolvable, as an arrangement in ℙ^{n}(F), if and only if A is a direct sum of (affine) arrangements B that have any of the following forms, after translation and renumbering coordinates:

(i) Every coordinate i ≥ 3 in B is strictly affinely transitive in B_{(i)} .

(ii) Every coordinate i ≥ 4 is strictly affinely transitive in B_{(i)} , char F = 2, and B

contains x_{j} − x_{k} = 0, 1 for 1 ≤ j < k ≤ 3. (iii) There are a fixed g_{0} ∈ F^{∗}, a set {i_{1}, …, i_{k}, m} of coordinates with k ≥ 1, and a

coordinate r ≥ i_{1}, …, i_{k}, m, such that every coordinate i > r is strictly affinely transitive in B_{(i)} ,

B_{0} = {x_{m} = x_{i_{j}} + g_{0} : 1 ≤ j ≤ k} ⊆ B,

{x_{i_{j}} = x_{i_{l}} : 1 ≤ j < l ≤ k} ⊆ B \ B_{0} ⊆ {x_{i} = x_{j} : 1 ≤ i < j ≤ r}, and every coordinate i ≤ r is strictly affinely transitive in B_{(i)} \ B_{0} . ■

4. Examples

4a. Group expansions and biased expansions. Take a simple graph Γ with vertex set [n] and a subset U ⊆ V (Γ). In the definition of 𝔊K_{n}, include only those edges (i, j; g) for which ij ∈ E(Γ). Then one has the partially filled 𝔊-expansion 𝔊Γ^{(U)} of Γ. If 𝔊 = ℤ_{γ}, this gain graph corresponds to the complex hyperplane arrangement

{x_{i} = ω^{k}x_{j}, x_{l} = 0 : ij ∈ E(Γ), 0 ≤ k < γ, l ∈ U},

where ω is a primitive γ^{th} root of unity. (Of course, if γ = 2, then ω = −1 and we can regard this as a real arrangement.) Corollary 4.1. Assuming |𝔊| ≥ 2 and Γ is connected, G(𝔊Γ^{(U)}) is supersolvable if and only if Γ is chordal and U^{c} is a stable set of simplicial vertices in Γ, or 𝔊Γ^{(U)} = ±K_{3} , or |V (Γ)| ≤ 2. Furthermore, G(𝔊Γ^{(U)}) has a modular coatom if and only if Γ has a simplicial vertex v with N(v) ⊆ U, or 𝔊Γ^{(U)} = ±K_{3} , or |V (Γ)| ≤ 2. ■

The characteristic polynomial of the bias matroid of a finite 𝔊-expansion, provided γ = |𝔊| ≥ 2 or U ≠ ∅, is

(4.1)  p_{G}(λ) = _{∑_{X⊆V (Γ)} ; stable}γ^{n−|X|}χ_{Γ\X} (\frac{λ − 1}{γ}) ,

χ_{Γ} being the chromatic polynomial. (See [17, Ex. III.3.6 and III.4.6].) In particular if U = V (Γ) we have

(4.2)  p_{G}(λ) = γ^{n}χ_{Γ} (\frac{λ − 1}{γ}) ,

so in this case p_{G}(λ) has (positive) integral roots if and only if χ_{Γ} does. Thus if Γ is nonchordal with integral characteristic roots, then G(𝔊Γ^{(V)}) is nonsupersolvable with integral roots.

Suppose that Γ is chordal (i.e., that G(Γ) is supersolvable); then p_{G}(λ) has positive integral roots if U = V (Γ). More generally, let U^{c} be a set of simplicial vertices of Γ. It is easy to see that U^{c} is the disjoint union of cliques W_{1}, W_{2}, …, W_{q} where every element of W_{i} has the same complete neighborhood, therefore the same degree d_{i}. Thus the characteristic polynomial of Lat G(𝔊Γ^{(U)}) is given by

(4.3)  p_{G}(λ) = γ^{n−q}χ_{Γ\Q} (\frac{λ − 1}{γ}) ∏_{i=1}^{q}(λ − γd_{i} + |W_{i}| − 1)

where Q is any set consisting of one vertex from each W_{i}. Letting the roots of χ_{Γ} be d_{1}, …, d_{q}, d_{q+1}, …, d_{n}, we conclude that p_{G}(λ) has roots

γd_{1} + 1 − |W_{1}|, …, γd_{q} + 1 − |W_{q}|, γd_{q+1} + 1, …, γd_{n} + 1.

These are positive integers, of course. But G(𝔊Γ^{(U)}) is supersolvable only when all |W_{i}| = 1.

Factorizability and freeness. One can show that Γ and its full 𝔊-expansion parallel each other’s behavior in regard to properties like factorizability of the matroid or, for finite cyclic 𝔊, freeness of a representing hyperplane arrangement. And how about a nonfull expansion Φ = 𝔊Γ^{(U)} ? I can show by calculating characteristic polynomials that, for G(Φ) to be free or have a factorization in the sense of [8, 16], Γ must be chordal and U^{c} consist only of simplicial vertices. Then G(Φ) is supersolvable, hence is free and has a factorization, if U^{c} is stable. (What happens when U^{c} is not stable I have not determined.) Thus in some sense the supersolvable examples of this type are fundamental, while the nonsupersolvable ones are derived by very selective deletions. Whether this observation may generalize to any other kinds of matroids is not known.

Corollary 4.2. Assume Γ is a simple graph of finite order and |𝔊| ≥ 2.

(A) L_{0}(𝔊Γ) is supersolvable ⟺ Γ is chordal. It has a modular coatom ⟺ Γ has

a simplicial vertex. (B) Assuming Γ has no isolated vertices, L(𝔊Γ) is supersolvable, and indeed has a

modular coatom, only when |V (Γ)| ≤ 2 or 𝔊Γ = ±K_{3} . ■

The supersolvable lift examples are trivial in a sense: they satisfy L(𝔊Γ) = G(𝔊Γ), so they are subsumed under Corollary 4.1.

Are there any examples with integral roots that are not supersolvable? By Section 1f, the positivity and integrality of the roots of L_{0}(𝔊Γ) are identical to those of G(𝔊Γ^{(V)}).

Setting γ = |𝔊| and assuming γ and n ≥ 2, the lift characteristic polynomial for connected Γ, from [17, Ex. III.6.6], is

(4.4)  p_{L}(λ) = λ^{−1} \{(λ − 1)γ^{n−1}χ_{Γ} (\frac{λ}{γ}) + χ_{Γ}(λ)\} .

Although it seems that an integral factorization of p_{L}(λ) could exist, if at all, only in the rarest circumstances, I see no way to decide this except in very special cases.

4b. Near-Dowling and Dowling lift lattices. The most interesting group expansions are those in which Γ = K_{n}. The near-Dowling lattice Q_{n,p}^{†}(𝔊) of a group 𝔊 (or quasigroup, if n ≤ 3) is Lat G(𝔊K_{n}^{(p)}); it generalizes the Dowling lattice Q_{n,n}^{†}(𝔊) introduced in [5]. If |𝔊| = 2, Q_{n,p}^{†}(𝔊) is the lattice of subspaces generated by the root system B_{n} with n − p standard basis vectors omitted, thus in particular by D_{n} if p = 0. If 𝔊 = ℤ_{γ}, Q_{n,p}^{†}(𝔊) is a complex analog.

The characteristic polynomial of a finite near-Dowling lattice follows from (4.1), since χ_{K_{l}}(y) = y(y − 1) ⋯ (y − l + 1). Evidently the roots are positive integers. Can this fact be explained by supersolvability? Mostly not, since by Corollary 4.1, if γ ≥ 2, then Q_{n,p}^{†}(𝔊) is supersolvable if and only if p ≥ n−1 or (n, p, γ) = (3, 0, 2). (The supersolvability of the Dowling lattices was proved by Dowling. Nonsupersolvability for various particular values of n, p, and γ seems to have been noticed several times.) Notwithstanding this, there are explanations of the integrality of the roots of the near-Dowling lattices: algebraically, if |𝔊| = 2 the corresponding arrangements are free [7]; combinatorially, the lattice has an atom decision tree if |𝔊| = 2 [3], while one can regard the gain-graph coloring method of [17, Ex II.4.7] as a graphical reason. On the other hand, Bailey [2] showed that if |𝔊| = 2 the matroid does not have a factorization in the sense of [8, 16].

The [extended] Dowling lift lattice Q_{n}^{§§}(𝔊) [or, Q_{n}^{§}(𝔊)] of 𝔊 is Lat L(𝔊K_{n}) [or, Lat L_{0}(𝔊K_{n})]. Q_{n}^{§§}(𝔊) equals the near-Dowling lattice Q_{n,0}^{†}(𝔊) if n ≤ 3, and Q_{1}^{§}(𝔊) = Q_{1,1}^{†}(𝔊); otherwise the lift, extended lift, and near Dowling lattices are all different. From Corollary 4.2 we see that all Q_{n}^{§}(𝔊) are supersolvable. On the other hand, Q_{n}^{§§}(𝔊) is supersolvable only when n ≤ 2 or γ = 1 or (n, γ) = (2, 3). The roots of Q_{n}^{§§}(𝔊) are positive integers when n = 3 because the lattice equals Q_{3,0}^{†}(𝔊). For larger n it seems impossible that they could all be integers, but I cannot prove there are no exceptions.

4c. An extension of Edelman and Reiner’s theorem. Edelman and Reiner [7] showed that the two-term hyperplane representation x^{∗}(Σ^{(U)}) of a signed graph Σ^{(U)} , where Σ has the form +K_{n} ∪ −Δ, is supersolvable if and only if Δ is a threshold graph and U satisfies certain conditions. They did so as a byproduct of their characterization of free arrangements of this type. We can derive their supersolvability criterion and a simple generalization directly from Theorem 2.2.

First we need some definitions. The (decreasing) degree partial order on the vertices of a graph Δ is defined by v ≺ w if deg v > deg w. A degree order on V (Δ) is any linear extension of the degree partial order. A graph Δ is a threshold graph if it is obtained from the empty graph by adding one vertex at a time, each new vertex being adjacent to all or none of the previous vertices. (For threshold graphs see [10, Chapter 10].)

Corollary 4.3. Let 𝔊 be a group, ℌ a proper subgroup, Δ a spanning subgraph of K_{n}, and U ⊆ V (K_{n}). Define Φ = 𝔊Δ ∪ ℌK_{n}. Then G(Φ^{(U)}) is supersolvable if and only if one of the following holds:

(i) Δ is a threshold graph, U is an ideal in the degree partial order, and U^{c} is stable in Δ if |ℌ| = 1, |U^{c}| ≤ 1 if |ℌ| > 1.

(ii) |ℌ| = 1, U = ∅, and |E(Δ)| = 1.

(iii) |ℌ| = 1, |𝔊| = 2, U = ∅, and E(Δ) is either a triangle or a star. ■

One could apply Corollary 4.2 to a finite cyclic group 𝔊 ⊆ ℂ^{∗}. Then the hyperplane representation x^{∗}(Φ^{(U)}) is a mild complex generalization of the arrangements treated by Edelman and Reiner.

Corollary 4.4. With notation as in Corollary 4.3, L_{0}(Φ) is supersolvable if and only if Δ is a threshold graph. L(Φ) is supersolvable if and only if Φ is as in Corollary 4.3 (ii-iii). ■

4d. Bicircular matroids. These are the bias matroids G(Γ, ∅) of contrabalanced graphs (Γ, ∅). (Loose edges are excluded here. We also exclude loops, since they behave like half edges. Multiple edges are, as usual, allowed.) Since (Γ, ∅) can be embedded in ⟨ℤ_{γ}K_{n}^{(n)}⟩ for any γ ≥ 2^{|E(Γ)|}, we obtain a representation of G(Γ, ∅) by complex hyperplanes of the forms x_{i} = ω^{k}x_{j} and x_{l} = 0, similar to those mentioned in Example 4a.

A multitree is a link graph whose simplification (that is, the graph resulting from replacing parallel sets by simple edges) is a tree. A partially filled multitree is T^{(U)} where U ⊆ V (T). A multitree T can be described by a tree \overline{T} and a positive multiplicity function μ : E(\overline{T}) → ℤ. T^{(U)} can be described by the pair (\overline{T}^{(U)}, μ). A leaf is a vertex having just one neighbor.

Corollary 4.5. Let Γ be a graph of finite order.

(a) G(Γ, ∅) is supersolvable if and only if each component of Γ is either a partially filled multitree T^{(U)} such that T:U is connected and every multiple edge is incident with a vertex in U, or a multitree with just one multiple edge, or a link graph containing exactly one polygon.

(b) G(Γ, ∅) has a modular coatom if and only if Γ has a leaf whose degree is one or whose neighbor is filled, or Γ = mK_{2} with m ≥ 2, or Γ is a unicycle. ■

The matroids of partially filled multitrees are very simple. Geometrically, they consist of lines l_{ij}, corresponding to adjacent pairs of vertices, in general position in n-space except for meeting at points P_{i} (called “joints”) corresponding to vertices. A joint belongs to the matroid if and only if the corresponding vertex is in U. The total number of points, other than joints, on each l_{ij} equals the multiplicity of edges joining its two vertices. (These matroids are obviously not new; our interest in them is as examples of our biased-graphic theorems.)

Let T^{(U)} be a partially filled multitree of the kind in Corollary 4.5(a). Let B = E(T̄):U. One can show by coloring in suitable gain groups that G(T^{(U)}) has characteristic polynomial

(4.5)  p_{G}(λ) = ∏_{e∈B}(λ − 1 − μ(e)) ∏_{e∉B}(λ − μ(e)),

assuming T^{(U)} is not balanced. In fact one can calculate the characteristic polynomials of any G(T^{(U)}). It turns out that there do exist limited but still substantial numbers of these matroids that are not supersolvable but whose characteristic roots are positive integers. The details are complicated and mysterious, so I omit them.

We conclude with the lift analogs of bicircular matroids. A multiisthmus in a connected graph is an edge or a set of parallel edges whose removal disconnects the graph.

Corollary 4.6. Let Γ be a connected link graph of finite order.

(A) L_{0}(Γ, ∅) is supersolvable ⟺ Γ is a multitree. It has a modular copoint ⟺ Γ has a multiisthmus.

(B) L(Γ, ∅) is supersolvable ⟺ Γ is a multitree with at most one multiple edge. It has a modular copoint ⟺ Γ has an isthmus, or Γ is a multitree with one multiple edge, or Γ is a unicycle. ■

5. Comments and questions

5a. Algorithmics. Theorems 2.2 and 3.2 yield a reasonably fast algorithm for deciding whether a given biased or gain graph has supersolvable bias, lift, or extended lift matroid; and thereby whether a given two-term or graphic-lift arrangement of hyperplanes is supersolvable.

5b. Generalized chordality. Theorem 2.2 raises the tantalizing question of generalizing criteria for chordality in graphs. For a graph Γ, supersolvability of G(Γ) is equivalent to each of the following: existence of a simplicial vertex ordering, chordality, and Dirac’s condition that minimal vertex joins be cliques (see [10, Thm. 4.1]). The first property is generalized (with necessary exceptions) to biased graphs by Theorem 2.2 but I do not know how to generalize the others.

Acknowledgement

I thank Marge Pratt for expert and patient typing of many and messy changes to get the manuscript completed. I also thank the referee for providing relevant recent references.

References

1. Christos A. Athanasiadis, On free deformations of the braid arrangement, European J. Combin. 19 (1998), 7–18. MR 99d:52008.

2. G.D. Bailey, Inductively factored signed-graphic arrangements of hyperplanes, Discrete Math., to appear.

3. C. Bennett and B. Sagan, A generalization of semimodular supersolvable lattices, J. Combin. Theory Ser. A 72 (1995), 209–231. MR 96i:05180.

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

5. 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.

6. T.A. Dowling and D.G. Kelly, Elementary strong maps between combinatorial geometries. In: Colloquio Internazionale sulle Teorie Combinatorie (Atti, Roma, 1973), Vol. II. Atti dei Convegni Lincei, 17. Accademia Nazionale dei Lincei, Rome, 1976, pp. 121-152. MR 58 #27567.

7. P.H. Edelman and V. Reiner, Free hyperplane arrangements between A_{n−1} and B_{n}, Math. Z. 215 (1994), 347-365. MR 95b:52021.

8. M. Falk and M. Jambu, Factorizations of combinatorial geometries, manuscript, 1989.

9. Robert Gill, The number of elements in a generalized partition semilattice, Discrete Math. 186 (1998), 125–134. MR 99e:52014.

10. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. MR 81e:68081.

11. P. Orlik and H. Terao, Arrangements of Hyperplanes. Grundl. math. Wiss., Vol. 300. Springer-Verlag, Berlin, 1992. MR 94e:52014.

12. J.G. Oxley, Matroid Theory. Oxford University Press, Oxford, 1992. MR 94d:05033.

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

14. R.P. Stanley, Supersolvable lattices, Algebra Univ. 2 (1972), 197-217. MR 46 #8920.

15. R.P. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Nat. Acad. Sci. USA 93 (1996), 2620–2625. MR 97i:52013.

16. H. Terao, Factorizations of the Orlik-Solomon algebras, Adv. In Math. 91 (1992), 45-53. MR 92m:52024.

17. Th. 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.

18. Th. Zaslavsky, Frame matroids and biased graphs, Europ. J. Combin. 15 (1994), 303-307. MR 95a:05021.