W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Mathematics Colloquium/CSUMS Lecture
April 1, 2011
3pm - 4pm
Title: An Introduction to Matroid Theory Through Lattice Paths
Abstract: The first (longer) part of this talk is based on joint work with Anna de Mier and Marc Noy of Universitat Polit`ecnica de Catalunya. In this part, we introduce matroid theory through concrete examples that arise from lattice paths. Fix lattice paths P and Q that go from (o,o) to (m, r), with P never going above Q, and consider the lattice paths from (o,o) to (m, r) that stay in the region that P and Q bound. We show that these paths can be identified with the bases of a special type of matroid. (Bases of matroids have properties that abstract those of bases of vector spaces.) For these matroids, called lattice path matroids, the fundamental
operations of matroid theory have simple path interpretations. Many important invariants (such as the Tutte polynomial) are #P-hard to compute for arbitrary matroids, but their natural interpretations for lattice path matroids yield polynomial-time algorithms.
Lattice path matroids form a small part of the deep and beautiful theory of matroids, a field that has important applications to, for instance, combinatorial optimization, arrangements of hyperplanes, coding theory, and physics. The second part of the talk provides glimpses of the broader field. Building on ideas in the first part, we give a bird's-eye view of some of the major research areas, such as representability over fields, well-quasi-ordering by minors, extremal matroid theory, matroid constructions, and more.
Abstract: The first (longer) part of this talk is based on joint work with Anna de Mier and Marc Noy of Universitat Polit`ecnica de Catalunya. In this part, we introduce matroid theory through concrete examples that arise from lattice paths. Fix lattice paths P and Q that go from (o,o) to (m, r), with P never going above Q, and consider the lattice paths from (o,o) to (m, r) that stay in the region that P and Q bound. We show that these paths can be identified with the bases of a special type of matroid. (Bases of matroids have properties that abstract those of bases of vector spaces.) For these matroids, called lattice path matroids, the fundamental
operations of matroid theory have simple path interpretations. Many important invariants (such as the Tutte polynomial) are #P-hard to compute for arbitrary matroids, but their natural interpretations for lattice path matroids yield polynomial-time algorithms.
Lattice path matroids form a small part of the deep and beautiful theory of matroids, a field that has important applications to, for instance, combinatorial optimization, arrangements of hyperplanes, coding theory, and physics. The second part of the talk provides glimpses of the broader field. Building on ideas in the first part, we give a bird's-eye view of some of the major research areas, such as representability over fields, well-quasi-ordering by minors, extremal matroid theory, matroid constructions, and more.
Contact
[[gyu, Gexin Yu]]