×

The Catalan matroid. (English) Zbl 1031.05030

Summary: We show how the set of Dyck paths of length 2\(n\) naturally gives rise to a matroid, which we call the “Catalan matroid” \(\mathbf C_n\). We describe this matroid in detail; among several other results, we show that \(\mathbf C_n\) is self-dual, it is representable over \(\mathbb Q\) but not over finite fields \(\mathbb F_q\) with \(q \leqslant n-2\), and it has a remarkably nice Tutte polynomial. We then generalize our construction to obtain a family of matroids, which we call “shifted matroids”. They are precisely the matroids whose independence complex is a shifted simplicial complex.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05E10 Combinatorial aspects of representation theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. Ardila, Enumerative and algebraic aspects of matroids and hyperplane arrangements, Ph.D. Dissertation, Massachusetts Institute of Technology, 2003.; F. Ardila, Enumerative and algebraic aspects of matroids and hyperplane arrangements, Ph.D. Dissertation, Massachusetts Institute of Technology, 2003.
[2] J.E. Bonin, A. de Mier, Lattice path matroids: structural aspects, in preparation.; J.E. Bonin, A. de Mier, Lattice path matroids: structural aspects, in preparation. · Zbl 1087.05014
[3] J.E. Bonin, A. de Mier, M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials,; J.E. Bonin, A. de Mier, M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, · Zbl 1031.05031
[4] Crapo, H. H., The Tutte polynomial, Aequationes Math., 3, 211-229 (1969) · Zbl 0197.50202
[5] Fulton, W., Young Tableaux with Applications to Representation Theory and Geometry (1997), Cambridge University Press: Cambridge University Press New York · Zbl 0878.14034
[6] J. Haglund, personal communication, 2002.; J. Haglund, personal communication, 2002.
[7] Kalai, G., Algebraic shifting, (Hibi, T., Computational Commutative Algebra and Combinatorics (2002), Mathematical Society of Japan: Mathematical Society of Japan Tokyo) · Zbl 1034.57021
[8] C. Klivans, Shifted matroid complexes, Ph.D. Dissertation, Massachusetts Institute of Technology, in preparation.; C. Klivans, Shifted matroid complexes, Ph.D. Dissertation, Massachusetts Institute of Technology, in preparation.
[9] Kreweras, G., Sur les éventails de segments, Cahiers BURO, 15, 3-41 (1970)
[10] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press New York · Zbl 0784.05002
[11] 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
[12] Piff, M. J.; Welsh, D. J.A., On the vector representation of matroids, J. London Math. Soc., 2, 284-288 (1970) · Zbl 0213.29102
[13] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks - Cole, Belmont, CA, 1986; reprinted by Cambridge University Press, Cambridge, 1997.; R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks - Cole, Belmont, CA, 1986; reprinted by Cambridge University Press, Cambridge, 1997. · Zbl 0608.05001
[14] R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999.; R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, 1999. · Zbl 0928.05001
[15] R.P. Stanley, personal communication, 2002.; R.P. Stanley, personal communication, 2002.
[16] Vallé, J., Une bijection explicative de plusieurs propriétés ramarquables des ponts, European J. Combin., 18, 117-124 (1997) · Zbl 0866.05005
[17] Welsh, D. J.A., A bound for the number of matroids, J. Combin. Theory, 6, 313-316 (1969) · Zbl 0167.01704
[18] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press New York · Zbl 0343.05002
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.