Matroid Theory, 2007 course notes
Federico Ardila · Free author course
Read lectures 13–18 for closure and flats before returning to the fixed K₃ ground set.
Open the sourceMatroid polytopes: selections become points
A basis is a zero–one vector. Their convex hull is a shape.
Prerequisites: 06 · Coordinates are not the arrow, 16 · Bases, circuits, rank and flats, 20 · Mixed area: a geometric inequality you can prove
Understand
Objectives
- Translate each K₃ basis into an edge-indexed indicator.
- Distinguish rank, ambient dimension and affine dimension.
- Explain an exchange edge and a fractional mixture.
Start with something you can see
In the polytope lab, start with the selected K₃ path {a,b}. Predict what happens to rank when edge c closes the cycle, then select each of the three two-edge bases. The graph edges a,b,c are the fixed matroid ground set, not the graph vertices.
Give the idea a precise name
A basis indicator has coordinate 1 for each selected edge and 0 otherwise. The base polytope is the convex hull of all basis indicators: a point is a nonnegative weighted average of these vertices, with weights summing to one. A fractional mixture is a point of the polytope, not a basis.
P(M)=conv{1_B : B a basis}; xₐ+x_b+x_c=2 for U₂,₃
In U₂,₃, every basis has two of the three edges. The ambient coordinate space is ℝ³, but the fixed-sum equation places the triangle in a plane. Its three vertices are not collinear, so the affine dimension is 2. Rank 2, affine dimension 2 and ambient dimension 3 describe different things. Changing the selected path in the lab does not change E or the polytope.
Work one small world
The figure projects the three indicator vertices from the plane xₐ+x_b+x_c=2 onto a triangle. The table gives the exact coordinates that the projection cannot show.
| Basis | (xₐ,x_b,x_c) | Exchange from {a,b} |
|---|---|---|
| {a,b} | (1,1,0) | start |
| {a,c} | (1,0,1) | b→c |
| {b,c} | (0,1,1) | a→c |
The midpoint of the first two vertices is (1,1/2,1/2), a half-and-half mixture. Their difference is (0,−1,1), the exchange direction e_c−e_b.
Counterexample to “every polytope point is a basis”: (1,1/2,1/2) lies on an edge but has fractional entries. In U₂,₄ the point (1/2,1/2,1/2,1/2) is a mixture of bases of rank 2 in ℝ⁴; the base polytope has affine dimension 3, not 4.
THE BRIDGEThe next ring packages flat relations rather than bases; the two constructions should not be identified.
WHERE THIS IDEA STOPSThe displayed triangle is a projection of points in ℝ³, not a claim that the original graph has these coordinates.
Experiment
Use the path buttons to test closure, then the three basis buttons to follow indicator points. Move Weight for {a,b} and Weight for {a,c}; the third weight is the remainder. Interior point sets 0.2 and 0.3, leaving 0.5.
Which motion inside this shape corresponds to swapping exactly one selected element?
Check & explain
What is the sum of the three coordinates of any U₂,₃ base-polytope point?
What does (0,−1,1) do to {a,b}?
- Adds both b and c
- Exchanges b for c
- Changes the ground set to vertices
Teach back
List all six bases of U₂,₄. Express (1/2,1/2,1/2,1/2) as a mixture, and explain why it is not a basis.
- Index coordinates by ground-set edges or elements.
- Give nonnegative weights summing to one.
- Separate the three-dimensional affine hull from ℝ⁴.
Read deeper
Discrete Geometry / Polytopes, 2010 course
Federico Ardila · Free author course
Read lectures 2–3 for convex hulls; construct the three indicator points directly.
Open the sourceLecture Notes: Topics in Combinatorial Optimization
MIT OpenCourseWare · Course notes · MIT OCW
Optional lecture 10 describes the independent-set matroid polytope, a different polytope from this base polytope.
Open the source