Matroids: A Geometric Introduction · contents
Gary Gordon & Jennifer McNulty · Publisher contents
Use the publisher contents to locate chapters 1–2, pp.1–39, and chapter 4 for graphic matroids; the contents are not a full chapter.
Open the sourceCapstone I · One triangle, five languages
Graph → matrix → matroid → polytope → polynomial.
Prerequisites: 14 · The first exact bridge: graph → matrix, 18 · The lattice and characteristic polynomial, 21 · Matroid polytopes: selections become points, 24 · The Hodge bridge: signature → inequality
Understand
Objectives
- Build and label five triangle representations.
- Calculate a cycle relation, basis exchange and polynomial normalization.
- Distinguish the basis polynomial Hessian from characteristic coefficients.
Start with something you can see
Draw a triangle with edge ground set E={a,b,c}. Predict what remains when you translate its edges into signed incidence columns, independent sets, basis indicator points and polynomials. Check all three two-edge selections before claiming the translations preserve dependence. For each arrow, name what gets lost.
Give the idea a precise name
Orient edges a:1→2, b:2→3 and c:3→1; columns record −1 at a tail and +1 at a head. The graphic matroid ground set is the three edges, not the vertices. Bases are maximal cycle-free edge sets. A basis indicator has coordinate 1 for each selected edge and 0 otherwise.
B=[−1 0 1; 1 −1 0; 0 1 −1]; f(z)=zₐz_b+zₐz_c+z_bz_c
The columns sum to zero. Every pair is independent, so the sole circuit is {a,b,c}, the rank is 2, and U₂,₃ has seven independent subsets including the empty set. Its three basis indicators (1,1,0), (1,0,1), (0,1,1) form a triangle in the plane xₐ+x_b+x_c=2. Exchanging b for c moves along one edge.
Work one small world
The atlas anchors are P_G(q)=q(q−1)(q−2), χ_M(q)=(q−1)(q−2), and χ̄_M(q)=q−2 because this connected graph has P_G=qχ_M. The separate polynomial f has Hessian H=[0 1 1; 1 0 1; 1 1 0]. It sends (1,1,1) to twice itself and each vector with coordinate sum zero to its negative, so its eigenvalues are 2, −1, −1.
| Atlas view | Map / retained fact | Not retained automatically |
|---|---|---|
| Graph → incidence columns | Orient edges; cycle gives a column relation | Orientation is a choice |
| Columns → matroid | Independent column sets become edge sets | Vector lengths and angles |
| Bases → polytope | Send a basis to its 0–1 indicator; take convex hull | Interior points are not bases |
| Graph → P → χ → χ̄ | Count proper vertex colorings; divide q, then q−1 | These are not the basis polynomial f |
| Bases → f → H | Sum basis monomials; take second derivatives | A Hessian signature alone proves no general theorem |
Counterexample to replacing edge ground sets by vertices: the three graph vertices also number three, but a graphic-matroid basis is a two-edge spanning tree, not a two-vertex selection. Nor may the rank-3 U₃,₃ Chow calculation be copied to this rank-2 matroid.
THE BRIDGENext use the same map-by-map discipline for a four-cycle proof map.
WHERE THIS IDEA STOPSA single Hessian calculation does not establish the general Lorentzian or Hodge theorem.
Experiment
Use the graph lab’s triangle comparison from lesson 17 and the fixed K₃ polytope from lesson 16. Fill each atlas row before opening the worked anchors; test a basis exchange along one polytope edge.
Which exact proposition makes each translation valid?
Check & explain
How many independent edge subsets, including ∅, does the triangle have?
What is the positive eigenvalue of the displayed Hessian?
Teach back
In the teach-back field, submit your translation atlas: a table of five views with a named map, one preserved fact and one lost fact per arrow. Include the oriented cycle equation, three indicators, basis exchange, three distinct polynomial formulas and the Hessian eigenspaces.
- If an edge/vertex distinction is missing, label both ground sets.
- If a map is missing, write its input and output and verify all three bases.
- If the polynomial distinction is missing, calculate P, χ, χ̄ and f separately.
- If the signature claim is unsupported, exhibit the all-ones and sum-zero eigenspaces.
Read deeper
Lecture 6: Graph Theory and Coloring
MIT OpenCourseWare · Course lecture · MIT OCW
Use Lecture 6 for the definition of proper vertex coloring only; derive the polynomials in this worksheet.
Open the source