NB: A PDF version of this announcement (suitable for posting) is also available.

Lattice Path Matroids

Joseph E. Bonin
The George Washington University

Thursday, November 6, 2003
102 Bradley Hall, 4 pm
Tea 3:30 pm, Math Lounge

Abstract: For fixed lattice paths P and Q that go from (0,0) to (m,r), with P never going above Q, how many lattice paths from (0,0) to (m,r) stay in the region bounded by P and Q? How many such paths P^* have a given area, say i, between P and P^*? Such questions fall under the enumerative theory of lattice paths, which has developed greatly in recent decades.

We develop the theory of lattice paths in a new direction, showing that the paths that remain in the region bounded by P and Q can be identified with the bases of a special type of matroid, called a lattice path matroid. This gives the theory of lattice paths a new geometric dimension. Many important invariants (such as the Tutte polynomial) that are \#P-hard to compute for arbitrary matroids have natural lattice-path interpretations for lattice path matroids, and these interpretations yield simple polynomial-time algorithms for computing the invariants. Also, we describe how the matroid perspective on lattice paths leads to new enumerative results.

This talk, which should be accessible to a wide audience, will supply the few items of matroid background that are necessary to understand the results. This project is joint work with Anna de Mier (Oxford University and Universitat Politecnica de Catalunya) and Marc Noy (Universitat Politecnica de Catalunya). A preprint is available at http://arxiv.org/abs/math.CO/0211188.

This talk will be accessible to graduate students.