Lattice path matroids: enumerative aspects and Tutte polynomials

Details Lattice path matroids: enumerative aspects and Tutte polynomials Lattice path matroids: enumerative aspects and Tutte polynomials

2002-11-12

arxiv.org/abs/math/0211188v1

Mathematics

Combinatorics

28 pages, 11 figures

Scientific paper

Fix two lattice paths P and Q from (0,0) to (m,r) that use East and North steps with P never going above Q. We show that the lattice paths that go from (0,0) to (m,r) and that remain in the region bounded by P and Q can be identified with the bases of a particular type of transversal matroid, which we call a lattice path matroid. We consider a variety of enumerative aspects of these matroids and we study three important matroid invariants, namely the Tutte polynomial and, for special types of lattice path matroids, the characteristic polynomial and the beta invariant. In particular, we show that the Tutte polynomial is the generating function for two basic lattice path statistics and we show that certain sequences of lattice path matroids give rise to sequences of Tutte polynomials for which there are relatively simple generating functions. We show that Tutte polynomials of lattice path matroids can be computed in polynomial time. Also, we obtain a new result about lattice paths from an analysis of the beta invariant of certain lattice path matroids.

Affiliated with

Also associated with

No associations

Rating

Lattice path matroids: enumerative aspects and Tutte polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lattice path matroids: enumerative aspects and Tutte polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lattice path matroids: enumerative aspects and Tutte polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-19439