Thomas Zaslavsky (Binghamton)

Signed and Biased Graphs: A Survey

Abstract for the Combinatorics Seminar
2005

A survey of some widely divergent areas within the theories of signed and biased graphs, with emphasis on my own research.

A signed graph is a graph whose edges have been signed (by graph theorists -- joke!) by + and - signs; the basic fact is then which circles have positive or negative sign product. The second basic fact is that, within each theta subgraph, the number of negative circles is even. If all circles are positive the signed graph is called balanced. One may ask for criteria that a signed graph be balanced; or when there is a negative circle through any specified vertex, or similar questions.

A biased graph is a graph together with a list of circles, which are called balanced circles, such that within each theta subgraph the number of balanced circles is not exactly 2. (For instance, a signed graph gives a biased graph; and one can generalize that statement from the sign group to any group.) From this single fact one can construct two matroids, the bias and lift matroids of the biased graph, which have interesting linear representations (for instance, signed graphs correspond to subsets of the classical root systems and graphs with edges labelled from Zn correspond to complex n-th-root-of-unity generalizations) and whose matroid characteristic polynomials can often be computed by a group generalization of graph coloring. Such computations lead to conclusions about strange things, for instance, a geometrical model of voting.