Supersolvable matroids of signed and biased graphs
by
Thomas Zaslavsky
SUNY at Binghamton, a.k.a "Binghamton University"

A signed graph is a graph in which each edge is labelled + or -. A polygon (i.e., circuit) is called ``balanced'' when the product of its edge signs is positive. If we want to understand the linear dependence structure of a subset S of the dual hyperplane arrangement of a classical root system, - let's say, of C_n^* = { x_i = x_j, x_i = -x_j } in Rⁿ - we can do so through a matroid G(\Sigma) which is defined on the edge set of a signed graph \Sigma (corresponding to S) in terms of the balance of polygons in \Sigma. G(\Sigma) faithfully represents the linear dependence properties of S. This gives us a graphical, and reasonably practical, way to calculate the matroidal characteristic polynomial of S (a polynomial that is better known to some, these days, as the Hilbert polynomial of the hyperplane arrrangement S^* dual to S) and to study such properties of S^* as its algebraic (i.e., Terao) freeness and supersolvability that imply an integral factorization of the polynomial.

A gain graph is like a signed graph but with the group of signs replaced by an arbitrary group. (When the group is finite cyclic, we can use gain graphs to represent the linear dependence structure of a subset of a complex analog of a root system.) A biased graph is a combinatorial abstraction of signed and biased graphs, much as an abstract projective geometry abstracts the projective space over a field, ) which is just strong enough to permit a matroid theory.

With biased graph theory it is easy to characterize which signed, gain, and biased graphs have matroids that are supersolvable, generalizing Stanley's theorem about graphic matroids. By gain graph coloring, it is easy to perform a graphical calculation of the characteristic polynomial; with such calculations and the characterization of supersolvability one can generalize to gain graphs Edelman and Reiner's description of the signed graphs that contain all possible positive nonloop edges and are supersolvable or algebraically free.

Date received: May 16, 1999