Math 581: Topics in Graph Theory
Graphs and Geometry
Fall 2008 – Spring 2009

Outline and Readings

Main Course Page | LaTeX Tips | Readings

• Chapter O: Background and Introduction.
• Chapter I: Graphs.
• Chapter II: Signed Graphs.
• Chapter III: Geometry.
• Chapter IV: Gain Graphs and Biased Graphs.
• Chapter V: Matroids. (Possible future course.)
• Chapter VI: Coloring. (Possible future course.)

Detailed Outline

• Chapter O: Background and Introduction.
  • Dates: Day One and any time.
  • Description:
    1. Day One: Overview of graphs, signed graphs, equations, hyperplanes. (8/25)
    2. As things come up: All kinds of background.
  • Readings:
    • Right away: [GRS].
    • As needed: [Pearls] or (better) Bondy-Murty or equivalent, [Cox] or equivalent.

• Chapter I: Graphs.
  • Dates: First month.
  • Description: Basics, orientation, geometry, coloring, polynomials.
    1. Technical Definitions. (8/27,29)
       1. Graph.
       2. Types of edge: link, loop, half edge, loose edge. Edge notation. Ordinary graph.
       3. Degree of a vertex.
       4. Spanning, induced, arbitrary subgraphs.
       5. Special kinds of graph.
       6. Special vertex sets.
    2. Basic Structures. (8/27,29)
       1. Walks, trails, paths, closed paths.
       2. Connectedness (defined via paths). Components. c(Γ) = number of (vertex) components. π(Γ).
       3. Circles. Walk/trail/path vs. graph.
       4. Trees and forests: spanning and not. Maximal forest. 1-Trees, pseudotrees, 1-forests, pseudoforests.
    3. Minors: Deletion and contraction by an edge or edge set. V(Γ/S) = π(V,S) = π(S). (8/29)
    4. Closure (operation on edge sets). Lattice of closed sets and lattice of connected partitions. (8/29, 9/8)
    5. Incidence and Adjacency Matrices. (9/3)
       1. Incidence matrix. Column structure.
       2. Adjacency matrix. Eigenvalues.
    6. Orientation. (9/5)
       1. Definition and notation.
       2. Incidence matrix.
       3. Cycles. Acyclic and totally cyclic orientations.
       4. Acyclic orientation: Ordering of the vertex set.
    7. Equations and Inequalities from Edges. (9/8)
       1. Graphic hyperplane arrangements, intersection lattice.
       2. Linear dependence of columns of the incidence matrix.
       3. Closure, intersection lattice, and connected partitions.
       4. Regions; consistency of inequalities via acyclic orientation.
    8. Chromatic Functions. (9/8-22)
       1. Coloring. Proper vs. improper. Set of improper edges. (9/8)
       2. Chromatic number χ(Γ). (9/8)
       3. Chromatic polynomial χ_Γ(λ). Corank-nullity polynomial. Deletion-contraction and multiplication identities. Subset expansion. (9/8)
       4. Acyclic orientations. Proper and compatible pairs; Stanley's theorem; interpretation via inside-out polytopes. (9/17,19)
       5. Dichromatic polynomial Q_Γ(u,v) and corank-nullity polynomial R_Γ(u,v). Deletion-contraction and multiplication identities. Small examples. (9/22)
       6. Numbers of spanning trees and maximal forests. (9/22)
       7. Colorations by improper edge set. (9/22)
       8. Tutte polynomial. (9/24)
    9. Line Graphs. Matrices and eigenvalues. Bounds for line graphs and regular graphs. (9/26)
    10. Circuits and Bonds. Cycles (defs. b, c, d) and cocycles. Cycle and cocycle spaces. (9/26, 10/3)
  • Readings: [Pearls] for elementary notions. [BM] mainly, also [AGTPG], [SG, §1], and [BG1, §1], for advanced notions.

• Chapter II: Signed Graphs.
  • Dates: Second to fourth months. Second semester extension, first month.
  • Description: Basics, orientation, geometry, coloring, polynomials.
    1. Technical Definitions. (10/6,8)
       1. Signed graph.
       2. Walk and circle signs.
       3. Balance.
          • Criteria for balance.
          • Harary's theorem and Harary bipartition.
       4. Switching.
       5. Examples. (10/24)
    2. Basic Structures. (10/8-15)
       1. Signature as a homomorphism. (10/8,13,15)
       2. Balanced circles and the oddity condition. (10/15)
    3. Connectedness.
       1. Balanced components. b(Σ), π_b(Σ). (10/13)
       2. Unbalanced blocks. (10/20)
    4. Measurement of Imbalance. (10/22)
       1. Balancing vertex and balancing edge.
       2. Many ways to measure.
       3. Frustration index. Petersdorf theorem.
       4. Vertex deletion number.
       5. Vertex-disjoint negative circles. Theorem of Slilaty.
    5. Minors. (10/24,27)
    1. Deletion.
    2. Contraction.
    3. Minors.
    6. Closure and Closed Sets. (10/29 - 11/3)
       1. Closure operator. (10/29)
       2. Closed sets. (10/29)
       3. Signed partial partitions. (10/29,31)
       4. Examples. (10/31, 11/3)
    7. Incidence and Adjacency Matrices. (11/3,5,7,10)
    1. Incidence matrix. Column structure: dependent sets, closed sets, rank.
    2. Adjacency matrix. Eigenvalues.
    8. Orientation. (11/10,12)
       1. Bidirected graphs.
       2. Incidence matrix.
       3. Cycles. Acyclic and totally cyclic orientations.
    9. Equations and Inequalities from Edges. (11/12-17)
       1. Signed-graphic hyperplane arrangements. (11/12)
          • 2-term hyperplanes: linear and projective arrangements.
          • Intersection lattice, closed sets, and signed partial partitions.
       2. Regions of real hyperplane arrangement; consistency of inequalities via acyclic orientation. (11/12,14)
       3. Binary additive representation. (11/17)
          • Lift circuits.
          • Augmented incidence matrix. Column structure.
          • Affinographic hyperplanes over F₂.
          • Intersection semilattice, balanced closed sets, and signed partitions.
    10. Chromatic Functions. (11/19-12/8)
        1. Coloring. Proper vs. improper. Set of improper edges. (11/19)
        2. Chromatic numbers χ(Σ) and χ*(Σ). (11/19)
        3. Chromatic polynomials: ordinary, balanced (zero-free), and comprehensive. Deletion-contraction and multiplicativity. Subset expansion. (11/19-21)
        4. Acyclic orientations. Proper and compatible pairs; Stanley-type theorem; inside-out polytope. (11/24-12/3)
        5. Dichromatic polynomials. Corank-nullity polynomials. Deletion-contraction and multiplicative identities. (12/3-8)
        6. Counting all colorations. (12/8-10)
        7. Tutte polynomial. (12/10)
    11. Signed complete graphs. (12/12)
        1. Coloring.
        2. Two-graphs.
        3. Strongly regular graphs.
    12. Line Graphs. (1/29-2/3)
        1. Line graph properties: eigenvalues and reconstruction. (1/29)
        2. Two definitions without properties: Behzad-Chartrand line graph, product line graph. (1/29)
        3. A definition with the eigenvalue property. (1/29-2/3)
           • A switching class. Bidirected. (1/29)
           • Adjacency matrix. (1/29-2/3)
           • Reduced signed graphs. (2/3)
           • All-positive, all-negative. Generalized line graphs. (2/3)
    13. Circuits and Cocircuits. Cycle and Cocycle Spaces. (2/5-24)
        1. Cycles and cuts, circuits and bonds. (2/5-19)
        2. Directed cycles and cuts. Indicator vectors. (2/5-19)
        3. Spaces and orthogonality. (2/24)
  • Readings:
    • Basic: [GRS], [SG], [SGC], [MTS], [OSG] (early part).
    • Advanced: [LG], [CW].

• Chapter III: Geometry.
  • Dates: Second semester extension, second-fourth months. Summer extension.
  • Description: Geometrical representations and applications.
    1. Linear, Affine, and Projective Spaces and Geometries. (2/26-3/3)
       1. Construction of affine and projective spaces (and geometries). (2/26)
          • Linear space Kⁿ (analytic). Subspaces, vectors, hyperplanes; dimension vs. rank.
          • Affine space Aⁿ(K). Construction from Kⁿ. Flats.
          • Projective geometry Pⁿ (synthetic). Construction from and to Aⁿ. Flats.
          • Projective space Pⁿ(K). Construction from Kⁿ⁺¹. Flats.
          • Affine space as a flat in Kⁿ⁺¹. Affine dependence as linear dependence.
       2. Vector sets and hyperplane arrangements. (2/26-3/3,10)
          • Real vectors. Positive span.
          • Hyperplanes: linear, projective, and affine. Characteristic polynomial.
          • Real hyperplane arrangements: regions, deletion-contraction formula.
          • Complex hyperplane arrangements: cohomology. (3/3,10)
    2. Geometric Representations of Signed Graphs. (3/3-12)
       1. Vector edge representations. (3/3)
          • Frame vector representation.
          • Columns of the incidence matrix.
          • Root systems; classical root systems.
          • Transitive closure and positive span.
          • Lift representation and the augmented incidence matrix.
       2. Hyperplane edge representations. (3/5-10)
          • Two-term (frame) hyperplane representation.
          • Regions and the chromatic polynomial.
          • Complex cohomology and the chromatic polynomial. (3/10)
          • Affinographic (lift) hyperplane representation in affine space. (3/10)
       3. Angle vertex representations. (3/10-7/23)
          • Root systems. (3/10-24)
          • Gramian representation. Gram matrix vs. adjacency matrix. (3/10-12)
          • Angle representation. Bipartite and nonbipartite graphs. (3/10-26)
          • Root representation vs. root systems. (3/26-7/23)
          • Eigenvalues ≥ −2. Line graphs. (7/23)
       4. Equiangular and semi-equiangular lines. (7/29-30)
  • Readings: [Cox], [GRS], [GR].

• Chapter IV: Gain Graphs and Biased Graphs.
  • Dates: Spring 2010.
  • Description: Further generalization of signed graphs.
    1. Technical Definitions: Gain Graphs. ()
       1. Gain graph.
       2. Walk and circle gains.
       3. Balance.
       4. Switching.
    2. Technical Definitions: Biased Graphs. ()
       1. Biased graph.
       2. Balance. Balanced partition.
    3. Minors. ()
       1. Deletion of an edge or edge set.
       2. Contraction of an edge or edge set.
       3. Minors.
    4. Closure and Closed Sets. ()
       1. Closure operator.
       2. Closed sets.
       3. Group-labelled partial partitions.
       4. The two matroids. Rank.
       5. Examples.
    5. Incidence Matrices of a Gain Graph. ()
       1. Multiplicative gains.
          • Canonical and standard form.
          • Vector representation from multiplicative gains.
       2. Additive gains.
          • Incidence matrix.
          • Vector representation from additive gains.
    6. Hyperplane Representations. ()
       1. Linear representation from multiplicative gains.
       2. Affine representation from additive gains.
    7. Coloring Gain Graphs. ()
       1. Proper vs. improper. Set of improper edges.
       2. Chromatic polynomials.
    8. Chromatic Functions of Gain and Biased Graphs. ()
       1. Chromatic polynomials. Deletion-contraction and multiplicativity. Subset expansion.
       2. Dichromatic polynomials. Deletion-contraction and multiplicative identities.
       3. Tutte polynomial.
  • Reading: [BG1, BG2, BG3 Sections 3-6, BG4 Sections 2, 4]

• Chapter V: Matroids.
  • Dates: Spring 2010.
  • Description: Abstract and applied geometry of signed, gain, and biased graphs.
  • Reading: [Oxley], [BG2], [BG4], [GLSP].

• Chapter VI: Coloring.
  • Dates: Spring 2010 or later.
  • Description: Many examples and uses of coloring of signed, gain, and biased graphs.
  • Reading: [SGC], [CISG], [BG3], [GLSP].

Main Course Page | LaTeX Tips | Outline

• [Cox] H.S.M. Coxeter, Introduction to Geometry, second edition. Chapters 12–14, §§ 15.1-3.
  Basic geometrical background for use in the course.
• [Pearls] Nora Hartsfield and Gerhart Ringel, Pearls in Graph Theory.
  Ch. 1, §§ 2.1-2, § 3.1, Ch. 8 for elementary background in graph theory. Very readable. Not always precisely correct, so make sure you understand the proofs.
• [BM] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. North Holland, New York, 1976.
  An advanced introduction, conceptually oriented. The best graph theory textbook to find background for this course. In connection with our course, see especially Chapters 1-3, 6, 8, 9, 12, and some of 10. The table of contents and links to the entire book are on the Web at
      http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html
• [PG] Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.
  Readable treatment of special topics, e.g., chordal graphs and comparability graphs.

• [SG] T.Z., "Signed graphs".
  Basic (but not necessarily elementary) concepts and properties.
• [SGC] T.Z., "Signed graph coloring".
  Basic (but not necessarily elementary) concepts and properties of coloring and the chromatic polynomial.
• [OSG] T.Z., "Orientation of signed graphs".
  Oriented signed graphs (bidirected graphs) and their hyperplane geometry.
• [MTS] T.Z., "Matrices in the theory of signed simple graphs".
  Introductory survey.
• [LG] T.Z., "Notes on line graphs".
  (Incomplete; not available yet. Sorry!)
• [CW] Beifang Chen and Jue Wang, The flow and tension spaces and lattices of signed graphs". European J. Combin. 30 (2009), 263-279.
  The basic paper.

• [GRS] T.Z., "The geometry of root systems and signed graphs". Amer. Math. Monthly, 88 (Feb., 1981), no. 2, 88-105.
  A readable introduction to some of the connections between graph theory and geometry.
• [CGSS] P.J. Cameron, J.M. Goethals, J.J. Seidel, and E.E. Shult, "Line graphs, root systems, and elliptic geometry". J. Algebra 43 (1976), 305-327. MR 56 #182. Zbl. 337.05142.
  A classic research paper in the background of part of our topic. Not introductory.
• [GR] Chris Godsil and Gordon Royle, Algebraic Graph Theory.
  Ch. 10 on strongly regular graphs (§§ 10.1-2), Ch. 11 on two-graphs and equiangular lines, and Ch. 12 (and § 1.7) on line graphs (§§ 12.1-3). A textbook that presents much of the material of [CGSS] with its background, in a more accessible way.

• [BG1] T.Z., "Biased graphs. I. Bias, balance and gains".
  Fundamentals of gain graphs and biased graphs. § 5: Fundamentals of gain graphs.
• [BG3] T.Z., "Biased graphs. III. Chromatic and dichromatic invariants".
  § 5: General theory of coloring gain graphs.

Biased Graphs and Gain Graphs:

• [BG1] T.Z., "Biased graphs. I. Bias, balance and gains".
  Fundamentals of gain graphs and biased graphs.
• [BG2] T.Z., "Biased graphs. II. The three matroids".
  The closure operations that are basic to the theory, in §§ 2, 3. Important open problems.
• [BG3] T.Z., "Biased graphs. III. Chromatic and dichromatic invariants".
  Chromatic polynomial et al., with and without colorings.
• [BG4] T.Z., "Biased graphs. IV: Geometrical realizations".
  Extensive treatment of the geometry of gain graphs. Fundamentals in §§ 2, 4. More advanced topics throughout, especially in § 7.

Main Course Page | LaTeX Tips | Outline | Readings