Chapter
1.5 Bipartite graphs and transversal matroids
Section 1.2 and 1.3 – Introduction to matroids
Section 1.4 – Graphs and matroids
Section 1.5 – Transversal matroids and other topics
2.1 From independent sets to bases and back again
2.2 Circuits and independent sets
2.3 Rank, flats, hyperplanes and closure
2.3.5 Cryptomorphism summary
2.4.1 Partially ordered sets
2.5 Tying it together with the rank function
2.5.1 Rank and independence
2.6 Cryptomorphisms between flats, hyperplanes and closure
2.6.3 Comments about complements
2.7 Application to optimization: the greedy algorithm
Axiom systems – Independent sets and bases
Axiom systems – Rank function
Axiom systems – Closure and flats
3.1 Matroid deletion and contraction
3.1.1 Drawing M-e and M/e
3.1.2 Commutativity of deletion and contraction
3.2 Deletion and contraction in graphs and representable matroids
3.2.1 Representable matroids
3.3.1 Motivation and examples
3.3.2 Fundamental results on dual matroids
3.4 Duality in graphic and representable matroids
3.4.1 Duals of graphic matroids
3.4.2 Duality in representable matroids
3.5 Direct sums and connectivity
3.5.3 Connectivity and rank
3.5.4 Connectivity motivation from graphs
Section 3.1 – Deletion and contraction
Section 3.2 – Deletion and contraction in graphs and matrices
Section 3.3 – Matroid duality
Section 3.4 – Duality in graphic and representable matroids
Section 3.5 – Direct sums
Section 3.5 – Connectivity
4.2 Graph versions of matroid theorems
4.2.1 Circuit elimination for graphs
4.2.2 Circuits, cocircuits and strong basis exchange
4.3 Duality and cocircuits in graphs
4.4 Connectivity and 2-isomorphism
Section 4.1 – Graphs are matroids
Section 4.2 – Circuits, cocircuits and bases
Section 4.3 – Duality and incidence matrices
Section 4.4 – 2-isomorphism of graphs
5.1 Affine geometry and affine dependence
5.1.1 Affine planes and cartesian coordinates
5.1.2 Fields and vector spaces
5.1.3 Affine geometry and matroids
5.2.1 Rank, closure and hyperplanes for affine geometries
5.3 The projective plane PG(2,q)
5.3.1 The projective plane PG(2,q) from affine space AG(3,q)
5.3.2 The projective plane PG(2,q) from the affine plane AG(2,q)
5.5 Counting k-flats and q-binomial coefficients
5.5.2 Connection to binomial coefficients
5.6 Abstract projective planes
Section 5.1 – Affine planes
Section 5.2 – Affine dependence
Section 5.3 – Projective planes
Section 5.4 – AG(n, q) and PG(n, q)
Section 5.5 – q-binomial coefficients
6: Representable matroids
6.1 Matrices are matroids
6.1.1 Column dependences of a matrix
6.1.2 Isthmuses, loops, deletion and contraction
6.1.3 Duality and the Rank-Nullity Theorem
6.2 Representing representable matroids
6.2.1 Finding a nice matrix
6.2.2 From a matroid to a matrix
6.2.3 Coordinatizing paths
6.3 How representations depend on the field
6.4 Non-representable matroids
6.5 Representations and geometry
Section 6.1 – Matrices and matroids
Section 6.2 – Finding representations
Section 6.3 – Representations and field characteristics
Section 6.4 – Non-representable matroids
Section 6.5 – Representations and geometry
7.2 Transversal matroids, matching theory and geometry
7.2.1 Matching theory and systems of distinct representatives
7.2.2 Finding nice bipartite graphs
7.2.3 Transversal matroids and geometry
7.2.4 Transversal matroids, deletion, contraction and duality
7.2.5 Representations of transversal matroids
7.3 Hyperplane arrangements and matroids
7.3.1 Central arrangements and matroids
7.3.2 Non-central arrangements
7.4 Cutting cheese; counting regions via deletion and contraction
Section 7.1 – Transversal matroids
Section 7.2 – Hall’s Theorem and free-simplicial representations
Section 7.3 – Hyperplane arrangements
Section 7.4 – Counting regions
8.1 Examples, excluded minors and the Scum Theorem
8.2.1 Graphs and binary matroids
8.2.2 Equivalent conditions for binary matroids
8.3 Summary of excluded minor results
Section 8.1 – Examples, excluded minors and the Scum Theorem
Section 8.2 – Binary matroids
Section 8.3 – Excluded minors
9.1 Motivation and history
9.2 Definition and basic examples
9.3 Corank-nullity polynomial
9.4 Duality and direct sum
9.5 Tutte--Grothendieck invariants
9.6 The chromatic polynomial
9.6.1 Basics of graph coloring
9.6.2 Connection to Tutte polynomial
Section 9.2 – The Tutte polynomial via deletion and contraction
Section 9.3 – The corank–nullity polynomial
Section 9.4 – Duality and direct sums
Section 9.5 – Tutte–Grothendieck invariants
Section 9.6 – Chromatic and flow polynomials
P.1 The number of matroids
P.3 Relaxing a hyperplane
P.4 Bases and probability in affine and projective space
P.5 Representing affine space - the characteristic set of AG(n,q)
P.6 The card game SET4.5pt and affine geometry
P.6.2 Connections to affine geometry
P.7 More matroid constructions - truncation
Appendix: Matroid axiom systems
Rank function r For any A ⊆ E: