MATHEMATICAL SCIENCES
COLLOQUIUM
| DATE: |
Thursday, November 15, 2001
|
| TIME: |
4:30-5:30 PM
|
| PLACE: |
LN 2205
|
| SPEAKER:
|
Thomas Zaslavsky (Binghamton University)
|
| TITLE: |
Secrets of Biased Graphs Revealed!
|
Abstract
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.
R E F R E S H M E N T S
4:00 To 4:25 PM
Kenneth W. Anderson
Memorial Reading Room