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
Additional Information
- Federico Ardila
- Affiliation: Department of Mathematics, San Francisco State University, San Francisco, California 94132 – and – Departamento de Matemáticas, Universidad de Los Andes, Bogotá, Colombia
- MR Author ID: 725066
- Email: federico@sfsu.edu
- Felipe Rincón
- Affiliation: Mathematics Institute, University of Warwick, Coventry CV4 7AL, United Kingdom – and – Departamento de Matemáticas, Universidad de Los Andes, Bogotá, Colombia
- Email: e.f.rincon@warwick.ac.uk
- Lauren Williams
- Affiliation: Department of Mathematics, University of California, Berkeley, California 94720-3840
- MR Author ID: 611667
- Email: williams@math.berkeley.edu
- Received by editor(s): October 18, 2013
- Received by editor(s) in revised form: November 5, 2013
- Published electronically: May 29, 2015
- Additional Notes: The first author was partially supported by the National Science Foundation CAREER Award DMS-0956178 and the SFSU-Colombia Combinatorics Initiative
The second author was supported by the EPSRC grant EP/I008071/1
The third author was partially supported by the National Science Foundation CAREER award DMS-1049513 - © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 368 (2016), 337-363
- MSC (2010): Primary 05A15, 05B35, 14M15, 14P10, 46L53
- DOI: https://doi.org/10.1090/tran/6331
- MathSciNet review: 3413866