Cover

Matroids: A Geometric Introduction

Title

Copyright

Dedication

Contents

Preface

Matroids – a quick prehistory

Using this text

Note to instructors

A note to students

Acknowledgements

1: A tour of matroids

1.1 Motivation

1.2 Introduction to matroids

1.3 Geometries

1.4 Graphs and matroids

1.4.1 Graph basics

1.4.2 Matroids defined from graphs

1.5 Bipartite graphs and transversal matroids

Exercises

Section 1.2 and 1.3 – Introduction to matroids

Section 1.4 – Graphs and matroids

Section 1.5 – Transversal matroids and other topics

2: Cryptomorphisms

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.1 Rank

2.3.2 Flat or closed set

2.3.3 Hyperplanes

2.3.4 Closure operator

2.3.5 Cryptomorphism summary

2.4 Lattice of flats

2.4.1 Partially ordered sets

2.4.2 Geometric lattices

2.5 Tying it together with the rank function

2.5.1 Rank and independence

2.5.2 Rank and closure

2.6 Cryptomorphisms between flats, hyperplanes and closure

2.6.1 Flats

2.6.2 Hyperplanes

2.6.3 Comments about complements

2.7 Application to optimization: the greedy algorithm

Exercises

Basic matroid concepts

Axiom systems – Independent sets and bases

Axiom systems – Rank function

Axiom systems – Closure and flats

Posets and lattices

Greedy algorithm

3: New matroids from old

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 Duality in 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.1 Direct sums

3.5.2 Connected matroids

3.5.3 Connectivity and rank

3.5.4 Connectivity motivation from graphs

Exercises

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: Graphic matroids

4.1 Graphs are matroids

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

Exercises

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: Finite geometry

5.1 Affine geometry and affine dependence

5.1.1 Affine planes and cartesian coordinates

5.1.2 Fields and vector spaces

Fields

Vector spaces

5.1.3 Affine geometry and matroids

5.2 Affine dependence

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.4 Projective geometry

From affine 3-space

From the affine plane

5.5 Counting k-flats and q-binomial coefficients

5.5.1 Computing

5.5.2 Connection to binomial coefficients

5.6 Abstract projective planes

Exercises

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

Exercises

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: Other matroids

7.1 Transversal matroids

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

Exercises

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: Matroid minors

8.1 Examples, excluded minors and the Scum Theorem

8.2 Binary matroids

8.2.1 Graphs and binary matroids

8.2.2 Equivalent conditions for binary matroids

8.3 Summary of excluded minor results

Exercises

Section 8.1 – Examples, excluded minors and the Scum Theorem

Section 8.2 – Binary matroids

Section 8.3 – Excluded minors

9: The Tutte polynomial

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

9.6.3 Nowhere-zero flows

First surprise

Second surprise

Third surprise

Exercises

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

Projects

P.1 The number of matroids

P.2 Matrix-Tree Theorem

P.3 Relaxing a hyperplane

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5

P.4 Bases and probability in affine and projective space

A. First, the formulas

B. Next, some analysis

C. A surprise

P.5 Representing affine space - the characteristic set of AG(n,q)

P.6 The card game SET4.5pt and affine geometry

P.6.1 The game

P.6.2 Connections to affine geometry

Problem 1

Problem 2

P.6.3 Counting problems

Problem 3

Problem 4

P.6.4 Caps

Problem 5

P.7 More matroid constructions - truncation

Appendix: Matroid axiom systems

A.1 Axiom lists

Independent sets I

Bases B

Circuits C

Rank function r For any A ⊆ E:

Flats F

Hyperplanes H

A.2 Axiom tables

Graphic matroids

Representable matroids

Transversal matroids

Bibliography

Index