AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Purity and Separation for Oriented Matroids
About this Title
Pavel Galashin and Alexander Postnikov
Publication: Memoirs of the American Mathematical Society
Publication Year:
2023; Volume 289, Number 1439
ISBNs: 978-1-4704-6700-5 (print); 978-1-4704-7594-9 (online)
DOI: https://doi.org/10.1090/memo/1439
Published electronically: August 24, 2023
Keywords: Weak separation,
strong separation,
purity phenomenon,
cluster algebras,
positroids,
oriented matroids,
zonotopal tilings,
Bohne-Dress theorem,
outerplanar graphs
Table of Contents
Chapters
- 1. Introduction
- 2. Separation, purity, and zonotopal tilings
- 3. Motivating examples
- 4. Simple operations on oriented matroids
- 5. Main results on purity
- 6. Background on zonotopal tilings and oriented matroids
- 7. Maximal by size ${\mathcal {M}}$-separated collections
- 8. Pure oriented matroids
- 9. The graphical case
- 10. The rank $3$ case
- 11. Classification results
Abstract
Leclerc and Zelevinsky, motivated by the study of quasi-commuting quantum flag minors, introduced the notions of strongly separated and weakly separated collections. These notions are closely related to the theory of cluster algebras, to the combinatorics of the double Bruhat cells, and to the totally positive Grassmannian.
A key feature, called the purity phenomenon, is that every maximal by inclusion strongly (resp., weakly) separated collection of subsets in $[n]$ has the same cardinality.
In this paper, we extend these notions and define $\mathcal {M}$-separated collections for any oriented matroid $\mathcal {M}$.
We show that maximal by size $\mathcal {M}$-separated collections are in bijection with fine zonotopal tilings (if $\mathcal {M}$ is a realizable oriented matroid), or with one-element liftings of $\mathcal {M}$ in general position (for an arbitrary oriented matroid).
We introduce the class of pure oriented matroids for which the purity phenomenon holds: an oriented matroid $\mathcal {M}$ is pure if $\mathcal {M}$-separated collections form a pure simplicial complex, i.e., any maximal by inclusion $\mathcal {M}$-separated collection is also maximal by size.
We pay closer attention to several special classes of oriented matroids: oriented matroids of rank $3$, graphical oriented matroids, and uniform oriented matroids. We classify pure oriented matroids in these cases. An oriented matroid of rank $3$ is pure if and only if it is a positroid (up to reorienting and relabeling its ground set). A graphical oriented matroid is pure if and only if its underlying graph is an outerplanar graph, that is, a subgraph of a triangulation of an $n$-gon.
We give a simple conjectural characterization of pure oriented matroids by forbidden minors and prove it for the above classes of matroids (rank $3$, graphical, uniform).
- Federico Ardila, Felipe Rincón, and Lauren Williams, Positroids, non-crossing partitions, and positively oriented matroids, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), Discrete Math. Theor. Comput. Sci. Proc., AT, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2014, pp. 655–666 (English, with English and French summaries). MR 3466411
- Christos A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. Math. 122 (1996), no. 2, 193–233. MR 1409420, DOI 10.1006/aima.1996.0059
- Spencer Backman, Matthew Baker, and Chi Ho Yuen, Geometric bijections for regular matroids, zonotopes, and Ehrhart theory, Forum Math. Sigma 7 (2019), Paper No. e45, 37. MR 4061968, DOI 10.1017/fms.2019.40
- Arkady Berenstein, Sergey Fomin, and Andrei Zelevinsky, Cluster algebras. III. Upper bounds and double Bruhat cells, Duke Math. J. 126 (2005), no. 1, 1–52. MR 2110627, DOI 10.1215/S0012-7094-04-12611-9
- L. J. Billera, M. M. Kapranov, and B. Sturmfels, Cellular strings on polytopes, Proc. Amer. Math. Soc. 122 (1994), no. 2, 549–555. MR 1205482, DOI 10.1090/S0002-9939-1994-1205482-0
- Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1999. MR 1744046, DOI 10.1017/CBO9780511586507
- Jochen Bohne. Eine kombinatorische analyse zonotopaler raumaufteilungen. Univ., Diss.–Bielefeld, 1992.
- Gary Chartrand and Frank Harary, Planar permutation graphs, Ann. Inst. H. Poincaré Sect. B (N.S.) 3 (1967), 433–438. MR 227041
- Henry H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969), 211–229. MR 262095, DOI 10.1007/BF01817442
- Vladimir I. Danilov, Alexander V. Karzanov, and Gleb A. Koshevoy, On maximal weakly separated set-systems, J. Algebraic Combin. 32 (2010), no. 4, 497–531. MR 2728757, DOI 10.1007/s10801-010-0224-x
- Vladimir I Danilov, Alexander V Karzanov, and Gleb A Koshevoy. Combined tilings and the purity phenomenon on separated set-systems. arXiv preprint arXiv:1401.6418, 2014.
- Miriam Farber and Pavel Galashin, Weak separation, pure domains and cluster distance, Selecta Math. (N.S.) 24 (2018), no. 3, 2093–2127. MR 3816500, DOI 10.1007/s00029-018-0394-2
- Lukas Finschi. A graph theoretical approach for reconstruction and generation of oriented matroids. PhD thesis, Swiss Federal Institute of Technology Zurich, 2001.
- Sergey Fomin and Andrei Zelevinsky, Cluster algebras. I. Foundations, J. Amer. Math. Soc. 15 (2002), no. 2, 497–529. MR 1887642, DOI 10.1090/S0894-0347-01-00385-X
- Sergey Fomin and Andrei Zelevinsky, Cluster algebras. II. Finite type classification, Invent. Math. 154 (2003), no. 1, 63–121. MR 2004457, DOI 10.1007/s00222-003-0302-y
- Sergey Fomin and Andrei Zelevinsky, $Y$-systems and generalized associahedra, Ann. of Math. (2) 158 (2003), no. 3, 977–1018. MR 2031858, DOI 10.4007/annals.2003.158.977
- Sergey Fomin and Andrei Zelevinsky, Cluster algebras. IV. Coefficients, Compos. Math. 143 (2007), no. 1, 112–164. MR 2295199, DOI 10.1112/S0010437X06002521
- Pavel Galashin, Plabic graphs and zonotopal tilings, Proc. Lond. Math. Soc. (3) 117 (2018), no. 4, 661–681. MR 3873131, DOI 10.1112/plms.12139
- Emeric Gioan, Enumerating degree sequences in digraphs and a cycle-cocycle reversing system, European J. Combin. 28 (2007), no. 4, 1351–1366. MR 2305596, DOI 10.1016/j.ejc.2005.11.006
- Emeric Gioan, Circuit-cocircuit reversing systems in regular matroids, Ann. Comb. 12 (2008), no. 2, 171–182. MR 2428903, DOI 10.1007/s00026-008-0345-2
- I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
- Jacob E. Goodman and Richard Pollack, Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines, J. Combin. Theory Ser. A 29 (1980), no. 3, 385–390. MR 600606, DOI 10.1016/0097-3165(80)90038-2
- Pavel Galashin and Gaiane Panina, Manifolds associated to simple games, J. Knot Theory Ramifications 25 (2016), no. 12, 1642003, 14. MR 3571379, DOI 10.1142/S0218216516420037
- B. Gärtner and E. Welzl, Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, Discrete Comput. Geom. 12 (1994), no. 4, 399–432. MR 1296137, DOI 10.1007/BF02574389
- Casimir Kuratowski. Sur le problème des courbes gauches en Topologie. Fundamenta mathematicae, 15(1):271–283, 1930.
- Gaku Liu, A counterexample to the extension space conjecture for realizable oriented matroids, Sém. Lothar. Combin. 78B (2017), Art. 31, 7. MR 3678613
- Michel Las Vergnas, Extensions ponctuelles compatibles d’une géométrie combinatoire, C. R. Acad. Sci. Paris Sér. A-B 286 (1978), no. 21, A981–A984 (French, with English summary). MR 497888
- Bernard Leclerc and Andrei Zelevinsky, Quasicommuting families of quantum Plücker coordinates, Kirillov’s seminar on representation theory, Amer. Math. Soc. Transl. Ser. 2, vol. 181, Amer. Math. Soc., Providence, RI, 1998, pp. 85–108. MR 1618743, DOI 10.1090/trans2/181/03
- Yu. I. Manin and V. V. Shekhtman, Higher Bruhat orderings connected with the symmetric group, Funktsional. Anal. i Prilozhen. 20 (1986), no. 2, 74–75 (Russian). MR 847150
- Suho Oh, Alexander Postnikov, and David E. Speyer, Weak separation and plabic graphs, Proc. Lond. Math. Soc. (3) 110 (2015), no. 3, 721–754. MR 3342103, DOI 10.1112/plms/pdu052
- James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819, DOI 10.1093/acprof:oso/9780198566946.001.0001
- Alexander Postnikov. Total positivity, Grassmannians, and networks. arXiv preprint arXiv:math/0609764, 2006.
- Victor Reiner, The generalized Baues problem, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 293–336. MR 1731820
- N. Sauer, On the density of families of sets, J. Combinatorial Theory Ser. A 13 (1972), 145–147. MR 307902, DOI 10.1016/0097-3165(72)90019-2
- Josh Scott, Quasi-commuting families of quantum minors, J. Algebra 290 (2005), no. 1, 204–220. MR 2154990, DOI 10.1016/j.jalgebra.2001.12.001
- Joshua S. Scott, Grassmannians and cluster algebras, Proc. London Math. Soc. (3) 92 (2006), no. 2, 345–380. MR 2205721, DOI 10.1112/S0024611505015571
- Saharon Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math. 41 (1972), 247–261. MR 307903
- Richard P. Stanley, An introduction to hyperplane arrangements, Geometric combinatorics, IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, RI, 2007, pp. 389–496. MR 2383131, DOI 10.1090/pcms/013/08
- W. T. Tutte, A homotopy theorem for matroids. I, II, Trans. Amer. Math. Soc. 88 (1958), 144–174. MR 101526, DOI 10.1090/S0002-9947-1958-0101526-0
- W. T. Tutte, Matroids and graphs, Trans. Amer. Math. Soc. 90 (1959), 527–552. MR 101527, DOI 10.1090/S0002-9947-1959-0101527-3
- V. N. Vapnik and A. Ja. Červonenkis, The uniform convergence of frequencies of the appearance of events to their probabilities, Teor. Verojatnost. i Primenen. 16 (1971), 264–279 (Russian, with English summary). MR 288823
- È. B. Vinberg, Discrete linear groups that are generated by reflections, Izv. Akad. Nauk SSSR Ser. Mat. 35 (1971), 1072–1112 (Russian). MR 302779
- V. A. Voevodskiĭ and M. M. Kapranov, The free $n$-category generated by a cube, oriented matroids and higher Bruhat orders, Funktsional. Anal. i Prilozhen. 25 (1991), no. 1, 62–65 (Russian); English transl., Funct. Anal. Appl. 25 (1991), no. 1, 50–52. MR 1113124, DOI 10.1007/BF01090678
- K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), no. 1, 570–590 (German). MR 1513158, DOI 10.1007/BF01594196
- Günter M. Ziegler, Higher Bruhat orders and cyclic hyperplane arrangements, Topology 32 (1993), no. 2, 259–279. MR 1217068, DOI 10.1016/0040-9383(93)90019-R