×

Positroids and non-crossing partitions. (English) Zbl 1325.05015

Summary: We investigate the role that non-crossing partitions play in the study of positroids, a class of matroids introduced by Postnikov. We prove that every positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then placing the structure of a connected positroid on each of the blocks of the partition. This structural result yields several combinatorial facts about positroids. We show that the face poset of a positroid polytope embeds in a poset of weighted non-crossing partitions. We enumerate connected positroids, and show how they arise naturally in free probability. Finally, we prove that the probability that a positroid on \([n]\) is connected equals \(1/e^2\) asymptotically.

MSC:

05A15 Exact enumeration problems, generating functions
05A17 Combinatorial aspects of partitions of integers
05B35 Combinatorial aspects of matroids and geometric lattices
14M15 Grassmannians, Schubert varieties, flag manifolds
14P10 Semialgebraic sets and related spaces
46L53 Noncommutative probability and statistics

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ardila, Federico; Klivans, Caroline J., The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B, 96, 1, 38-49 (2006) · Zbl 1082.05021 · doi:10.1016/j.jctb.2005.06.004
[2] Beissinger, Janet Simpson, The enumeration of irreducible combinatorial objects, J. Combin. Theory Ser. A, 38, 2, 143-169 (1985) · Zbl 0587.05004 · doi:10.1016/0097-3165(85)90065-2
[3] Borovik, Alexandre V.; Gelfand, I. M.; White, Neil, Coxeter matroids, Progress in Mathematics 216, xxii+264 pp. (2003), Birkh\"auser Boston, Inc., Boston, MA · Zbl 1050.52005 · doi:10.1007/978-1-4612-2066-4
[4] Bansal, Nikhil; Pendavingh, Rudi A.; van der Pol, Jorn G., On the number of matroids. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 675-694 (2012), SIAM, Philadelphia, PA · Zbl 1422.05030
[5] Callan, David, Counting stabilized-interval-free permutations, J. Integer Seq., 7, 1, Article 04.1.8, 7 pp. (2004) · Zbl 1065.05006
[6] Dotsenko, V. V.; Khoroshkin, A. S., Character formulas for the operad of a pair of compatible brackets and for the bi-Hamiltonian operad, Funktsional. Anal. i Prilozhen.. Funct. Anal. Appl., 41 41, 1, 1-17 (2007) · Zbl 1145.18001 · doi:10.1007/s10688-007-0001-3
[7] Ford, Nicolas, The expected codimension of a matroid variety, J. Algebraic Combin., 41, 1, 29-47 (2015) · Zbl 1318.14049 · doi:10.1007/s10801-014-0525-6
[8] [GW] Rafael Gonzalez D’Leon and Michelle Wachs, On the poset of weighted partitions, 25th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), Discrete Math. Theor. Comput. Sci. Proc., AJ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2013, pp. 1059-1070.
[9] Gel{\cprime }fand, I. M.; Goresky, R. M.; MacPherson, R. D.; Serganova, V. V., Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. in Math., 63, 3, 301-316 (1987) · Zbl 0622.57014 · doi:10.1016/0001-8708(87)90059-4
[10] Knuth, Donald E., The asymptotic number of geometries, J. Combinatorial Theory Ser. A, 16, 398-400 (1974) · Zbl 0278.05010
[11] [LP] T. Lam and A. Postnikov, Polypositroids, In progress.
[12] Mayhew, Dillon; Newman, Mike; Welsh, Dominic; Whittle, Geoff, On the asymptotic proportion of connected matroids, European J. Combin., 32, 6, 882-890 (2011) · Zbl 1244.05047 · doi:10.1016/j.ejc.2011.01.016
[13] Nica, Alexandru; Speicher, Roland, Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series 335, xvi+417 pp. (2006), Cambridge University Press, Cambridge · Zbl 1133.60003 · doi:10.1017/CBO9780511735127
[14] Oh, Suho, Positroids and Schubert matroids, J. Combin. Theory Ser. A, 118, 8, 2426-2435 (2011) · Zbl 1231.05061 · doi:10.1016/j.jcta.2011.06.006
[15] [OPS] S. Oh, A. Postnikov, and D. Speyer, Weak separation and plabic graphs, Preprint. arXiv:1109.4434. · Zbl 1309.05182
[16] Oxley, James G., Matroid theory, Oxford Science Publications, xii+532 pp. (1992), The Clarendon Press, Oxford University Press, New York · Zbl 0784.05002
[17] [postnikov] Alexander Postnikov, Total positivity, Grassmannians, and networks, Preprint. Available at \urlhttp://www-math.mit.edu/ apost/papers/tpgrass.pdf.
[18] [postnikovpersonal] Alex Postnikov, personal communication, 2012.
[19] Postnikov, Alexander; Speyer, David; Williams, Lauren, Matching polytopes, toric geometry, and the totally non-negative Grassmannian, J. Algebraic Combin., 30, 2, 173-191 (2009) · Zbl 1264.20045 · doi:10.1007/s10801-008-0160-1
[20] Schrijver, Alexander, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, xii+471 pp. (1986), John Wiley & Sons, Ltd., Chichester · Zbl 0970.90052
[21] Sloane, N. J. A., An on-line version of the encyclopedia of integer sequences, Electron. J. Combin., 1, Feature 1, approx.5 pp.(electronic) pp. (1994) · Zbl 1364.11001
[22] Speicher, Roland, Multiplicative functions on the lattice of noncrossing partitions and free convolution, Math. Ann., 298, 4, 611-628 (1994) · Zbl 0791.06010 · doi:10.1007/BF01459754
[23] Salvatore, Paolo; Tauraso, Roberto, The operad Lie is free, J. Pure Appl. Algebra, 213, 2, 224-230 (2009) · Zbl 1210.18008 · doi:10.1016/j.jpaa.2008.06.008
[24] Stanley, Richard P., Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics 62, xii+581 pp. (1999), Cambridge University Press, Cambridge · Zbl 0928.05001 · doi:10.1017/CBO9780511609589
[25] Talaska, Kelli, A formula for Pl\"ucker coordinates associated with a planar network, Int. Math. Res. Not. IMRN, Art. ID rnn 081, 19 pp. (2008) · Zbl 1170.05031 · doi:10.1093/imrn/rnn081
[26] Welsh, D. J. A., Matroid theory, xi+433 pp. (1976), Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York · Zbl 0343.05002
[27] Williams, Lauren K., Enumeration of totally positive Grassmann cells, Adv. Math., 190, 2, 319-342 (2005) · Zbl 1064.05150 · doi:10.1016/j.aim.2004.01.003
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.