An official website of the United States government
We study combinatorial inequalities for various classes of set systems: matroids, polymatroids, poset antimatroids, and interval greedoids. We prove log-concave inequal- ities for counting certain weighted feasible words, which generalize and extend several previous results establishing Mason conjectures for the numbers of independent sets of matroids. Notably, we prove matching equality conditions for both earlier inequalities and our extensions. In contrast with much of the previous work, our proofs are combinatorial and employ nothing but linear algebra. We use the language formulation of greedoids which allows a linear algebraic setup, which in turn can be analyzed recursively. The underlying non- commutative nature of matrices associated with greedoids allows us to proceed beyond polymatroids and prove the equality conditions. As further application of our tools, we rederive both Stanley’s inequality on the number of certain linear extensions, and its equality conditions, which we then also extend to the weighted case.
more »
« less
Intersection Theory of Polymatroids
Abstract Polymatroids are combinatorial abstractions of subspace arrangements in the same way that matroids are combinatorial abstractions of hyperplane arrangements. By introducing augmented Chow rings of polymatroids, modeled after augmented wonderful varieties of subspace arrangements, we generalize several algebro-geometric techniques developed in recent years to study matroids. We show that intersection numbers in the augmented Chow ring of a polymatroid are determined by a matching property known as the Hall–Rado condition, which is new even in the case of matroids.
more »
« less
- Award ID(s):
- 2001854
- PAR ID:
- 10526497
- Publisher / Repository:
- Oxford
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- Volume:
- 2024
- Issue:
- 5
- ISSN:
- 1073-7928
- Page Range / eLocation ID:
- 4207 to 4241
- 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
-
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
-
Abstract We initiate the study of a class of polytopes, which we coinpolypositroids, defined to be those polytopes that are simultaneously generalized permutohedra (or polymatroids) and alcoved polytopes. Whereas positroids are the matroids arising from the totally nonnegative Grassmannian, polypositroids are “positive” polymatroids. We parametrize polypositroids using Coxeter necklaces and balanced graphs, and describe the cone of polypositroids by extremal rays and facet inequalities. We introduce a notion of$$(W,c)$$-polypositroidfor a finite Weyl groupWand a choice of Coxeter elementc. We connect the theory of$$(W,c)$$-polypositroids to cluster algebras of finite type and to generalized associahedra. We discussmembranes, which are certain triangulated 2-dimensional surfaces inside polypositroids. Membranes extend the notion of plabic graphs from positroids to polypositroids.more » « less
-
We present a combinatorial formula using skew Young tableaux for the coefficients of Kazhdan-Lusztig polynomials for sparse paving matroids. These matroids are known to be logarithmically almost all matroids, but are conjectured to be almost all matroids. We also show the positivity of these coefficients using our formula. In special cases, such as uniform matroids, our formula has a nice combinatorial interpretation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imrn/rnad213
