×

Lattice path matroids: Enumerative aspects and Tutte polynomials. (English) Zbl 1031.05031

Summary: 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.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05A15 Exact enumeration problems, generating functions

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. Ardila, The Catalan matroid, arXiv:math.CO/0209354 v1, 25 Sep 2002.; F. Ardila, The Catalan matroid, arXiv:math.CO/0209354 v1, 25 Sep 2002.
[2] Björner, A., The homology and shellability of matroids and geometric lattices, (White, N., Matroid Applications (1992), Cambridge University Press: Cambridge University Press Cambridge), 226-283 · Zbl 0772.05027
[3] J. Bonin, O. Giménez, Multi-path matroids, in preparation.; J. Bonin, O. Giménez, Multi-path matroids, in preparation.
[4] J. Bonin, A. de Mier, Lattice path matroids: structural aspects, in preparation.; J. Bonin, A. de Mier, Lattice path matroids: structural aspects, in preparation. · Zbl 1087.05014
[5] Brylawski, T., An affine representation for transversal geometries, Stud. Appl. Math., 54, 143-160 (1975) · Zbl 0309.05018
[6] Brylawski, T., The Tutte polynomial. I. General theory, (Barlotti, A., Matroid Theory and its Applications (1982), Liguori: Liguori Naples), 125-175 · Zbl 1302.05023
[7] Brylawski, T.; Oxley, J. G., The Tutte polynomial and its applications, (White, N., Matroid Applications (1992), Cambridge University Press: Cambridge University Press Cambridge), 123-225 · Zbl 0769.05026
[8] Colbourn, C. J.; Provan, J. S.; Vertigan, D., The complexity of computing the Tutte polynomial on transversal matroids, Combinatorica, 15, 1-10 (1995) · Zbl 0821.05011
[9] Delest, M.-P.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci., 34, 169-206 (1984) · Zbl 0985.68516
[10] Merlini, D. D.; Sprugnoli, R.; Verri, C., The tennis ball problem, J. Combin. Theory Ser. A, 99, 307-344 (2002) · Zbl 1006.05007
[11] Mohanty, S. G., Lattice Path Counting and Applications (1979), Academic Press: Academic Press New York · Zbl 0455.60013
[12] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[13] Oxley, J. G.; Prendergast, K.; Row, D., Matroids whose ground sets are domains of functions, J. Austral. Math. Soc. Ser. A, 32, 380-387 (1982) · Zbl 0485.05023
[14] Rota, G.-C., On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrsch. Verw. Gebiete, 2, 340-368 (1964) · Zbl 0121.02406
[15] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, www.research.att.com/ njas/sequences/; N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, www.research.att.com/ njas/sequences/ · Zbl 1274.11001
[16] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.; R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999. · Zbl 0928.05001
[17] Stanton, D.; White, D., Constructive Combinatorics (1986), Springer: Springer New York · Zbl 0595.05002
[18] Welsh, D. J.A., A bound for the number of matroids, J. Combin. Theory, 6, 313-316 (1969) · Zbl 0167.01704
[19] Welsh, D. J.A., Complexity: Knots, Colourings and Counting (1993), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0799.68008
[20] Zaslavsky, T., The Möbius function and the characteristic polynomial, (White, N., Combinatorial Geometries (1987), Cambridge University Press: Cambridge University Press Cambridge), 114-138 · Zbl 0632.05017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.