An official website of the United States government
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
Log-concave poset inequalities
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
- Award ID(s):
- 2246845
- PAR ID:
- 10597806
- Publisher / Repository:
- Association for Mathematical Research
- Date Published:
- Journal Name:
- Journal of the Association for Mathematical Research
- Volume:
- 2
- Issue:
- 1
- ISSN:
- 2998-4114
- Page Range / eLocation ID:
- 53 to 153
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
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
-
Generalized permutahedra are polytopes that arise in combinatorics, algebraic geometry, representation theory, topology, and optimization. They possess a rich combinatorial structure. Out of this structure we build a Hopf monoid in the category of species. Species provide a unifying framework for organizing families of combinatorial objects. Many species carry a Hopf monoid structure and are related to generalized permutahedra by means of morphisms of Hopf monoids. This includes the species of graphs, matroids, posets, set partitions, linear graphs, hypergraphs, simplicial complexes, and building sets, among others. We employ this algebraic structure to define and study polynomial invariants of the various combinatorial structures. We pay special attention to the antipode of each Hopf monoid. This map is central to the structure of a Hopf monoid, and it interacts well with its characters and polynomial invariants. It also carries information on the values of the invariants on negative integers. For our Hopf monoid of generalized permutahedra, we show that the antipode maps each polytope to the alternating sum of its faces. This fact has numerous combinatorial consequences. We highlight some main applications: We obtain uniform proofs of numerous old and new results about the Hopf algebraic and combinatorial structures of these families. In particular, we give optimal formulas for the antipode of graphs, posets, matroids, hypergraphs, and building sets. They are optimal in the sense that they provide explicit descriptions for the integers entering in the expansion of the antipode, after all coefficients have been collected and all cancellations have been taken into account. We show that reciprocity theorems of Stanley and Billera–Jia–Reiner (BJR) on chromatic polynomials of graphs, order polynomials of posets, and BJR-polynomials of matroids are instances of one such result for generalized permutahedra. We explain why the formulas for the multiplicative and compositional inverses of power series are governed by the face structure of permutahedra and associahedra, respectively, providing an answer to a question of Loday. We answer a question of Humpert and Martin on certain invariants of graphs and another of Rota on a certain class of submodular functions. We hope our work serves as a quick introduction to the theory of Hopf monoids in species, particularly to the reader interested in combinatorial applications. It may be supplemented with Marcelo Aguiar and Swapneel Mahajan’s 2010 and 2013 works, which provide longer accounts with a more algebraic focus.more » « less
-
null (Ed.)Under Poincare-type conditions, upper bounds are explored for the Kolmogorov distance between the distributions of weighted sums of dependent summands and the normal law. Based on improved concentration inequalities on high-dimensional Euclidean spheres, the results extend and refine previous results to non-symmetric models.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.56994/JAMR.002.001.003
