An official website of the United States government
Abstract We establish a connection between the algebraic geometry of the type permutohedral toric variety and the combinatorics of delta‐matroids. Using this connection, we compute the volume and lattice point counts of type generalized permutohedra. Applying tropical Hodge theory to a new framework of “tautological classes of delta‐matroids,” modeled after certain vector bundles associated to realizable delta‐matroids, we establish the log‐concavity of a Tutte‐like invariant for a broad family of delta‐matroids that includes all realizable delta‐matroids. Our results include new log‐concavity statements for all (ordinary) matroids as special cases.
more »
« less
Stellahedral geometry of matroids
Abstract We use the geometry of the stellahedral toric variety to study matroids. We identify the valuative group of matroids with the cohomology ring of the stellahedral toric variety and show that valuative, homological and numerical equivalence relations for matroids coincide. We establish a new log-concavity result for the Tutte polynomial of a matroid, answering a question of Wagner and Shapiro–Smirnov–Vaintrob on Postnikov–Shapiro algebras, and calculate the Chern–Schwartz–MacPherson classes of matroid Schubert cells. The central construction is the ‘augmented tautological classes of matroids’, modeled after certain toric vector bundles on the stellahedral toric variety.
more »
« less
- PAR ID:
- 10526494
- Publisher / Repository:
- Cambridge
- Date Published:
- Journal Name:
- Forum of Mathematics, Pi
- Volume:
- 11
- ISSN:
- 2050-5086
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Chow rings of toric varieties, which originate in intersection theory, feature a rich combinatorial structure of independent interest. We survey four different ways of computing in these rings, due to Billera, Brion, Fulton–Sturmfels, and Allermann–Rau. We illustrate the beauty and power of these methods by giving four proofs of Huh and Huh–Katz’s formula μ_k(M) = deg_M(α^{r−k}β^k) for the coefficients of the reduced characteristic polynomial of a matroid M as the mixed intersection numbers of the hyperplane and reciprocal hyperplane classes α and β in the Chow ring of M. Each of these proofs sheds light on a different aspect of matroid combinatorics, and provides a framework for further developments in the intersection theory of matroids. Our presentation is combinatorial, and does not assume previous knowledge of toric varieties, Chow rings, or intersection theory. This survey was prepared for the Clay Lecture to be delivered at the 2024 British Combinatorics Conference.more » « less
-
We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a $$1 - 1/e - \epsilon$$ approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, $$1 - 1/e - \epsilon$$ approximation, using a nearly-linear number of function evaluations and arithmetic operations.more » « less
-
We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a 1 - 1/e - epsilon approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, 1 - 1/e - epsilon approximation, using a nearly-linear number of function evaluations and arithmetic operations.more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/fmp.2023.24
