**Problem of the Week**

**Math Club**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

seminars:comb:abstract.200503zas

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 **Z**_{n} 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.

seminars/comb/abstract.200503zas.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported