## 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