Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Positroids and non-crossing partitions


Authors: Federico Ardila, Felipe Rincón and Lauren Williams
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
Published electronically: May 29, 2015
MathSciNet review: 3413866
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [AK06] 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 (2006i:05034), https://doi.org/10.1016/j.jctb.2005.06.004
  • [Bei85] Janet Simpson Beissinger, The enumeration of irreducible combinatorial objects, J. Combin. Theory Ser. A 38 (1985), no. 2, 143-169. MR 784711 (86f:05008), https://doi.org/10.1016/0097-3165(85)90065-2
  • [BGW03] 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 (2004i:05028)
  • [BPvdP] 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
  • [Cal04] David Callan, Counting stabilized-interval-free permutations, J. Integer Seq. 7 (2004), no. 1, Article 04.1.8, 7. MR 2049703
  • [DK07] 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 (2008d:18006), https://doi.org/10.1007/s10688-007-0001-3
  • [For13] Nicolas Ford, The expected codimension of a matroid variety, J. Algebraic Combin. 41 (2015), no. 1, 29-47. MR 3296243, https://doi.org/10.1007/s10801-014-0525-6
  • [GDW13] 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.
  • [GGMS87] I. M. Gelfand, 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 (88f:14045), https://doi.org/10.1016/0001-8708(87)90059-4
  • [Knu74] Donald E. Knuth, The asymptotic number of geometries, J. Combinatorial Theory Ser. A 16 (1974), 398-400. MR 0335312 (49 #94)
  • [LP] T. Lam and A. Postnikov, Polypositroids, In progress.
  • [MNWW11] 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 (2012g:05039), https://doi.org/10.1016/j.ejc.2011.01.016
  • [NS06] 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 (2008k:46198)
  • [Oh11] Suho Oh, Positroids and Schubert matroids, J. Combin. Theory Ser. A 118 (2011), no. 8, 2426-2435. MR 2834184 (2012k:05078), https://doi.org/10.1016/j.jcta.2011.06.006
  • [OPS] S. Oh, A. Postnikov, and D. Speyer, Weak separation and plabic graphs, Preprint. arXiv:1109.4434.
  • [Oxl92] James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587 (94d:05033)
  • [Pos] Alexander Postnikov, Total positivity, Grassmannians, and networks, Preprint. Available at http://www-math.mit.edu/~apost/papers/tpgrass.pdf.
  • [Pos12] Alex Postnikov, personal communication, 2012.
  • [PSW09] 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 (2010f:20043), https://doi.org/10.1007/s10801-008-0160-1
  • [Sch86] 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 (88m:90090)
  • [Slo94] N. J. A. Sloane, An on-line version of the encyclopedia of integer sequences, Electron. J. Combin. 1 (1994), Feature 1, approx. 5 pp. (electronic). MR 1269167 (95b:05001)
  • [Spe94] Roland Speicher, Multiplicative functions on the lattice of noncrossing partitions and free convolution, Math. Ann. 298 (1994), no. 4, 611-628. MR 1268597 (95h:05012), https://doi.org/10.1007/BF01459754
  • [ST09] Paolo Salvatore and Roberto Tauraso, The operad Lie is free, J. Pure Appl. Algebra 213 (2009), no. 2, 224-230. MR 2467399 (2009k:18009), https://doi.org/10.1016/j.jpaa.2008.06.008
  • [Sta99] 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 (2000k:05026)
  • [Tal08] 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 (2009m:14075), https://doi.org/10.1093/imrn/rnn081
  • [Wel76] D. J. A. Welsh, Matroid theory, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. MR 0427112 (55 #148)
  • [Wil05] Lauren K. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005), no. 2, 319-342. MR 2102660 (2005i:05197), https://doi.org/10.1016/j.aim.2004.01.003

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A15, 05B35, 14M15, 14P10, 46L53

Retrieve articles in all journals with MSC (2010): 05A15, 05B35, 14M15, 14P10, 46L53


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
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
Email: williams@math.berkeley.edu

DOI: https://doi.org/10.1090/tran/6331
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
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society