Chapter IV: Gain Graphs and Biased Graphs.
- Dates: Jan.-March 2010.
- Description: Further generalization of signed graphs.
- Technical Definitions: Gain Graphs. (1/28-2/4)
- Gain graph.
- Walk and circle gains.
- Balance.
- Switching and potentials.
- Balance again.
- Two parameters (prelude).
- Examples. Trivial gains. Group and set expansions. Full gain graphs. Catalan and Shi gain graphs. Gains in a field. (2/9-11)
- Technical Definitions: Biased Graphs. (2/9)
- Biased graph.
- Balance.
- From gains to bias. [Ω] vs. <Ω>.
- Balanced partial partition πb(S), b(S). c(S), π(S).
- Examples. (2/9-11)
- Integral gain graphs associated with hyperplane arrangements. (2/9)
- Full biased graphs. (2/9)
- Non-gain bias. (2/9)
- Biased expansions, groups, and quasigroups and Latin squares. (2/11)
- Minors. (2/16-3/9)
- Deletion of an edge or edge set. (2/16)
- Contraction of an edge or edge set. (2/16)
- Minors. (2/18-3/9)
- Things that Balance. (3/11)
- Balancing vertices.
- Balancing edges.
- Balancing sets.
- Closure and Closed Sets. (3/11-)
- Closure operator. (3/11)
- Closed sets. Lift closure. (3/11)
- Group-labelled partial partitions. Dowling lattices.
- Rank. The two or three matroids.
- Examples.
- Incidence Matrices of a Gain Graph. ()
- Multiplicative gains.
- Canonical and standard form.
- Vector representation from multiplicative gains.
- Additive gains.
- Incidence matrix.
- Vector representation from additive gains.
- Hyperplane Representations. ()
- Linear representation from multiplicative gains.
- Affine representation from additive gains.
- Coloring Gain Graphs. ()
- Proper vs. improper. Set of improper edges.
- Chromatic polynomials.
- Techniques of coloring. Integral gain graphs.
- Chromatic Functions of Gain and Biased Graphs. ()
- Chromatic polynomials. Deletion-contraction and multiplicativity. Subset expansion.
- Dichromatic polynomials. Deletion-contraction and multiplicative identities.
- Tutte polynomial.
- Reading: [BG1, BG2, BG3 Sections 3-6, BG4 Sections 2, 4]
Main Course Page | LaTeX Tips | Main Outline | Readings
To my