Thomas Zaslavsky
Secrets of Biased Graphs Revealed!
A biased graph is a graph together with a class of distinguished circles (called balanced circles) such that, in any theta subgraph (this is the union of three internally disjoint paths with common endpoints), the number of balanced circles is 0, 1, or 3, but not 2. There is an extensive theory of biased graphs. We will discuss a few of the following.
- Different Kinds of Bias: Bias can arise from signs on the edges and more generally from gains, which are labellings of the edges from a group so that reversing the edge inverts the label (the gain) of the edge. In particular, a signed graph has gains in the sign group. Other kinds of bias arise from quasigroups, Latin hypercubes, Hamiltonian circles, transversal systems, and so on.
- Matroids: A biased graph has two (and a half) natural matroids. One of them, the bias matroid, includes as a special case the Dowling lattices of a group as well as many kinds of vector sets of current interest.
- Vector and Hyperplane Representations: The matroids can in some cases be represented by sets of vectors or hyperplanes, e.g., over the real or complex numbers. Little is known about when such representations exist. Examples of such representing sets include the classical root systems, also known as ``Coxeter arrangements'' (essentially, these correspond to signed graphs), for the bias matroid and the currently popular ``deformations of the Coxeter arrangement of type A'', for the lift matroid.
- Oriented Matroids: These matroids, especially the first kind, can be oriented in a way consistent with hyperplane representations over the reals.
- Coloring: There is a way to color a graph with gains in a finite group, analogous to ordinary graph coloring. Little is known about the chromatic number.
- Invariants: A biased graph has numerous polynomial invariants, such as: a chromatic polynomial (in fact, two of them), a Tutte polynomial (again, two of them; the invariants typically come in pairs), and so forth.
- Surface Embedding: Signed graphs have natural ways of embedding in nonorientable surfaces. A little bit is known about which signed graphs embed in which surfaces. The signed graph's chromatic number is related to the surface and there is a conjectured ``signed Heawood Theorem''. There is also a duality theory for gain graphs in surfaces.