An official website of the United States government
Thefoundationof a matroid is a canonical algebraic invariant which classifies, in a certain precise sense, all representations of the matroid up to rescaling equivalence. Foundations of matroids arepastures, a simultaneous generalization of partial fields and hyperfields which are special cases of both tracts (as defined by the first author and Bowler) and ordered blue fields (as defined by the second author). Using deep results due to Tutte, Dress–Wenzel, and Gelfand–Rybnikov–Stone, we give a presentation for the foundation of a matroid in terms of generators and relations. The generators are certain “cross-ratios” generalizing the cross-ratio of four points on a projective line, and the relations encode dependencies between cross-ratios in certain low-rank configurations arising in projective geometry. Although the presentation of the foundation is valid for all matroids, it is simplest to apply in the case of matroidswithout large uniform minors. i.e., matroids having no minor corresponding to five points on a line or its dual configuration. For such matroids, we obtain a complete classification of all possible foundations. We then give a number of applications of this classification theorem, for example: We prove the following strengthening of a 1997 theorem of Lee and Scobee: every orientation of a matroid without large uniform minors comes from a dyadic representation, which is unique up to rescaling. For a matroid without large uniform minors, we establish the following strengthening of a 2017 theorem of Ardila–Rincón–Williams: if is positively oriented then is representable over every field with at least 3 elements. Two matroids are said to belong to the samerepresentation classif they are representable over precisely the same pastures. We prove that there are precisely 12 possibilities for the representation class of a matroid without large uniform minors, exactly three of which are not representable over any field.
more »
« less
Purity and Separation for Oriented Matroids
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).
more »
« less
- PAR ID:
- 10507779
- Publisher / Repository:
- AMS
- Date Published:
- Journal Name:
- Memoirs of the American Mathematical Society
- Volume:
- 289
- Issue:
- 1439
- ISSN:
- 0065-9266
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Oriented matroids are combinatorial structures that generalize point configurations, vector configurations, hyperplane arrangements, polyhedra, linear programs, and directed graphs. Oriented matroids have played a key role in combinatorics, computational geometry, and optimization. This paper surveys prior work and presents an update on the search for bounds on the diameter of the cocircuit graph of an oriented matroid. The motivation for our investigations is the complexity of the simplex method and the criss-cross method. We review the diameter problem and show the diameter bounds of general oriented matroids reduce to those of uniform oriented matroids. We give the latest exact bounds for oriented matroids of low rank and low corank, and for all oriented matroids with up to nine elements (this part required a large computer-based proof). For arbitrary oriented matroids, we present an improvement to a quadratic bound of Finschi. Our discussion highlights an old conjecture that states a linear bound for the diameter is possible. On the positive side, we show the conjecture is true for oriented matroids of low rank and low corank, and, verified with computers, for all oriented matroids with up to nine elements. On the negative side, our computer search showed two natural strengthenings of the main conjecture are false.more » « less
-
A well-known conjecture of Richard Stanley posits that the $$h$$-vector of the independence complex of a matroid is a pure $${\mathcal O}$$-sequence. The conjecture has been established for various classes but is open for graphic matroids. A biconed graph is a graph with two specified 'coning vertices', such that every vertex of the graph is connected to at least one coning vertex. The class of biconed graphs includes coned graphs, Ferrers graphs, and complete multipartite graphs. We study the $$h$$-vectors of graphic matroids arising from biconed graphs, providing a combinatorial interpretation of their entries in terms of '$$2$$-weighted forests' of the underlying graph. This generalizes constructions of Kook and Lee who studied the Möbius coinvariant (the last nonzero entry of the $$h$$-vector) of graphic matroids of complete bipartite graphs. We show that allowing for partially $$2$$-weighted forests gives rise to a pure multicomplex whose face count recovers the $$h$$-vector, establishing Stanley's conjecture for this class of matroids. We also discuss how our constructions relate to a combinatorial strengthening of Stanley's Conjecture (due to Klee and Samper) for this class of matroids.more » « less
-
Abstract We show that the base polytopePMof any paving matroidMcan be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial ofPM, starting with Katzman’s formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes Ferroni’s work on sparse paving matroids. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation ofstressed-hyperplane relaxationintroduced by Ferroni, Nasr and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent.more » « less
-
Abstract Let ℳ 0 n {\mathcal{M}_{0}^{n}} be the class of closed, simply connected, non-negatively curved Riemannian n -manifolds admitting an isometric, effective, isotropy-maximal torus action. We prove that if M ∈ ℳ 0 n {M\in\mathcal{M}_{0}^{n}} , then M is equivariantly diffeomorphic to the free, linear quotient by a torus of a product of spheres of dimensions greater than or equal to 3. As a special case, we then prove the Maximal Symmetry Rank Conjecture for all M ∈ ℳ 0 n {M\in\mathcal{M}_{0}^{n}} . Finally, we showthe Maximal Symmetry Rank Conjecture for simply connected, non-negatively curved manifolds holds for dimensions less than or equal to 9 without additional assumptions on the torus action.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/memo/1439
