Matroids : a geometric introduction /

Mostrar otras versiones (1)
Detalles Bibliográficos
Autor principal: Gordon, Gary, 1956-
Otros Autores: McNulty, Jennifer
Formato: Libro
Lenguaje:English
Publicado: Cambridge ; New York : Cambridge University Press, 2012.
Materias:
Matroides.
Geometría combinatoria.
Tabla de Contenidos:
  • 1. A tour of matroids
  • 1.1. Motivation
  • 1.2. Introduction to matroids
  • 1.3. Geometries
  • 1.4. Graphs and matroids
  • 1.5. Bipartite graphs and transversal matroids
  • Exercises
  • 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.4. Lattice of flats
  • 2.5. Tying it together with the rank function
  • 2.6. Cryptomorphisms between flats, hyperplanes and closure
  • 2.7. Application to optimization: the greedy algorithm
  • Exercises
  • 3. New matroids from old
  • 3.1. Matroid deletion and contraction
  • 3.2. Deletion and contraction in graphs and representable matroids
  • 3.3. Duality in matroids
  • 3.4. Duality in graphic and representable matroids
  • 3.5. Direct sums and connectivity
  • Exercises
  • 4. Graphic matroids
  • 4.1. Graphs are matroids
  • 4.2. Graph versions of matroid theorems
  • 4.3. Duality and cocircuits in graphs
  • 4.4. Connectivity and 2-isomorphism
  • Exercises
  • 5. Finite geometry
  • 5.1. Affine geometry and affine dependence
  • 5.2. Affine dependence
  • 5.3. The projective plane PG(2, q)
  • 5.4. Projective geometry
  • 5.5. Counting k-flats and q-binomial coefficients
  • 5.6. Abstract projective planes
  • Exercises
  • 6. Representable matroids
  • 6.1. Matrices are matroids
  • 6.2. Representing representable matroids
  • 6.3. How representations depend on the field
  • 6.4. Non-representable matroids
  • 6.5. Representations and geometry
  • Exercises
  • 7. Other matroids
  • 7.1. Transversal matroids
  • 7.2. Transversal matroids, matching theory and geometry
  • 7.3. Hyperplane arrangements and matroids
  • 7.4. Cutting cheese; counting regions via deletion and contraction
  • Exercises
  • 8. Matroid minors
  • 8.1. Examples, excluded minors and the Scum Theorem
  • 8.2. Binary matroids
  • 8.3. Summary of excluded minor results
  • Exercises
  • 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
  • Exercises
  • Projects
  • P.1. The number of matroids
  • P.2. Matrix-Tree Theorem
  • 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 SET{reg} and affine geometry
  • P.7. More matroid constructions
  • truncation
  • Appendix Matroid axiom systems
  • A.1. Axiom lists
  • A.2. Axiom tables.

Ejemplares similares