Positroids and non-crossing partitions

Ardila, Federico; Rincón, Felipe; Williams, Lauren

doi:10.1090/tran/6331

Positroids and non-crossing partitions
HTML articles powered by AMS MathViewer

by Federico Ardila, Felipe Rincón and Lauren Williams PDF

Trans. Amer. Math. Soc. 368 (2016), 337-363 Request permission

Abstract:

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.

References

Federico Ardila and Caroline J. Klivans, The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B 96 (2006), no. 1, 38–49. MR 2185977, DOI 10.1016/j.jctb.2005.06.004
Janet Simpson Beissinger, The enumeration of irreducible combinatorial objects, J. Combin. Theory Ser. A 38 (1985), no. 2, 143–169. MR 784711, DOI 10.1016/0097-3165(85)90065-2
Alexandre V. Borovik, I. M. Gelfand, and Neil White, Coxeter matroids, Progress in Mathematics, vol. 216, Birkhäuser Boston, Inc., Boston, MA, 2003. MR 1989953, DOI 10.1007/978-1-4612-2066-4
Nikhil Bansal, Rudi A. Pendavingh, and Jorn G. van der Pol, On the number of matroids, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2012, pp. 675–694. MR 3186782
David Callan, Counting stabilized-interval-free permutations, J. Integer Seq. 7 (2004), no. 1, Article 04.1.8, 7. MR 2049703
V. V. Dotsenko and A. S. Khoroshkin, Character formulas for the operad of a pair of compatible brackets and for the bi-Hamiltonian operad, Funktsional. Anal. i Prilozhen. 41 (2007), no. 1, 1–22, 96 (Russian, with Russian summary); English transl., Funct. Anal. Appl. 41 (2007), no. 1, 1–17. MR 2333979, DOI 10.1007/s10688-007-0001-3
Nicolas Ford, The expected codimension of a matroid variety, J. Algebraic Combin. 41 (2015), no. 1, 29–47. MR 3296243, DOI 10.1007/s10801-014-0525-6
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.
I. M. Gel′fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. in Math. 63 (1987), no. 3, 301–316. MR 877789, DOI 10.1016/0001-8708(87)90059-4
Donald E. Knuth, The asymptotic number of geometries, J. Combinatorial Theory Ser. A 16 (1974), 398–400. MR 335312, DOI 10.1016/0097-3165(74)90063-6
T. Lam and A. Postnikov, Polypositroids, In progress.
Dillon Mayhew, Mike Newman, Dominic Welsh, and Geoff Whittle, On the asymptotic proportion of connected matroids, European J. Combin. 32 (2011), no. 6, 882–890. MR 2821559, DOI 10.1016/j.ejc.2011.01.016
Alexandru Nica and Roland Speicher, Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series, vol. 335, Cambridge University Press, Cambridge, 2006. MR 2266879, DOI 10.1017/CBO9780511735127
Suho Oh, Positroids and Schubert matroids, J. Combin. Theory Ser. A 118 (2011), no. 8, 2426–2435. MR 2834184, DOI 10.1016/j.jcta.2011.06.006
S. Oh, A. Postnikov, and D. Speyer, Weak separation and plabic graphs, Preprint. arXiv:1109.4434.
James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
Alexander Postnikov, Total positivity, Grassmannians, and networks, Preprint. Available at http://www-math.mit.edu/~apost/papers/tpgrass.pdf.
Alex Postnikov, personal communication, 2012.
Alexander Postnikov, David Speyer, and Lauren Williams, Matching polytopes, toric geometry, and the totally non-negative Grassmannian, J. Algebraic Combin. 30 (2009), no. 2, 173–191. MR 2525057, DOI 10.1007/s10801-008-0160-1
Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
N. J. A. Sloane, An on-line version of the encyclopedia of integer sequences, Electron. J. Combin. 1 (1994), Feature 1, approx. 5. MR 1269167
Roland Speicher, Multiplicative functions on the lattice of noncrossing partitions and free convolution, Math. Ann. 298 (1994), no. 4, 611–628. MR 1268597, DOI 10.1007/BF01459754
Paolo Salvatore and Roberto Tauraso, The operad Lie is free, J. Pure Appl. Algebra 213 (2009), no. 2, 224–230. MR 2467399, DOI 10.1016/j.jpaa.2008.06.008
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
Kelli Talaska, A formula for Plücker coordinates associated with a planar network, Int. Math. Res. Not. IMRN , posted on (2008), Art. ID rnn 081, 19. MR 2439562, DOI 10.1093/imrn/rnn081
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
Lauren K. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005), no. 2, 319–342. MR 2102660, DOI 10.1016/j.aim.2004.01.003