Search ResultsShowing 1-20 of 20
-
arXiv:2502.08948 (Published 2025-02-13)
Preservation of log-concavity on gamma polynomials
Comments: 13 pages, 4 figuresCategories: math.COEvery symmetric polynomial $h(x) = h_0 + h_1\,x + \cdots + h_n\,x^n$, where $h_i = h_{n-i}$ for each $i$, can be expressed as a linear combination in the basis $\{x^i(1+x)^{n-2i}\}_{i=0}^{\lfloor n/2\rfloor}$. The polynomial $\gamma_h(x) = \gamma_0 + \gamma_1 \,x+ \cdots + \gamma_{\lfloor n/2\rfloor}\, x^{\lfloor n/2\rfloor}$, commonly referred to as the $\gamma$-polynomial of $h(x)$, records the coefficients of the aforementioned linear combination. Two decades ago, Br\"and\'en and Gal independently showed that if $\gamma_h(x)$ has nonpositive real roots only, then so does $h(x)$. More recently, Br\"and\'en, Ferroni, and Jochemko proved using Lorentzian polynomials that if $\gamma_h(x)$ is ultra log-concave, then so is $h(x)$, and they raised the question of whether a similar statement can be proved for the usual notion of log-concavity. The purpose of this article is to show that the answer to the question of Br\"anden, Ferroni, and Jochemko is affirmative. One of the crucial ingredients of the proof is an inequality involving binomial numbers that we establish via a path-counting argument.
-
arXiv:2410.08812 (Published 2024-10-11)
A convex ear decomposition of the augmented Bergman complex of a matroid
Comments: 13 pagesCategories: math.COThis article concerns the face enumeration of augmented Bergman complexes of matroids, introduced by Braden, Huh, Matherne, Proudfoot and Wang. We prove that the augmented Bergman complex of any matroid admits a convex ear decomposition and deduce that augmented Bergman complexes are doubly Cohen--Macaulay and that they have top-heavy $h$-vectors. We provide some formulas for computing the $h$-polynomials of these complexes and exhibit examples which show that, in general, they are neither log-concave nor unimodal.
-
arXiv:2408.12386 (Published 2024-08-22)
Preservation of inequalities under Hadamard products
Comments: 21 pagesCategories: math.COWagner (1992) proved that the Hadamard product of two P\'olya frequency sequences that are interpolated by polynomials is again a P\'olya frequency sequence. We study the preservation under Hadamard products of related properties of significance in combinatorics. In particular, we show that ultra log-concavity, $\gamma$-positivity, and interlacing symmetric decompositions are preserved. Furthermore, we disprove a conjecture by Fischer and Kubitzke (2014) concerning the real-rootedness of Hadamard powers.
-
arXiv:2406.19962 (Published 2024-06-28)
Deletion formulas for equivariant Kazhdan-Lusztig polynomials of matroids
Comments: 14 pages. A part of this article was previously included in arXiv:2212.03190We study equivariant Kazhdan--Lusztig (KL) and $Z$-polynomials of matroids. We formulate an equivariant generalization of a result by Braden and Vysogorets that relates the equivariant KL and $Z$-polynomials of a matroid with those of a single-element deletion. We also discuss the failure of equivariant $\gamma$-positivity for the $Z$-polynomial. As an application of our main result, we obtain a formula for the equivariant KL polynomial of the graphic matroid gotten by gluing two cycles. Furthermore, we compute the equivariant KL polynomials of all matroids of corank~$2$ via valuations. This provides an application of the machinery of Elias, Miyata, Proudfoot, and Vecchi to corank $2$ matroids, and it extends results of Ferroni and Schr\"oter.
-
arXiv:2403.17696 (Published 2024-03-26)
Tutte polynomials of matroids as universal valuative invariants
Comments: 22 pagesCategories: math.COWe provide a full classification of all families of matroids that are closed under duality and minors, and for which the Tutte polynomial is a universal valuative invariant. There are four inclusion-wise maximal families, two of which are the class of elementary split matroids and the class of graphic Schubert matroids. As a consequence of our framework, we derive new properties of Tutte polynomials of arbitrary matroids. Among other results, we show that the Tutte polynomial of every matroid can be expressed uniquely as an integral combination of Tutte polynomials of graphic Schubert matroids.
-
arXiv:2311.01397 (Published 2023-11-02)
Schubert matroids, Delannoy paths, and Speyer's invariant
Comments: 20 pages. 1 ancillary file. To appear in Combinatorial TheoryCategories: math.COWe provide a combinatorial way of computing Speyer's $g$-polynomial on arbitrary Schubert matroids via the enumeration of certain Delannoy paths. We define a new statistic of a basis in a matroid, and express the $g$-polynomial of a Schubert matroid in terms of it and internal and external activities. Some surprising positivity properties of the $g$-polynomial of Schubert matroids are deduced from our expression. Finally, we combine our formulas with a fundamental result of Derksen and Fink to provide an algorithm for computing the $g$-polynomial of an arbitrary matroid.
-
Face enumeration for split matroid polytopes
Comments: 18 pages. Title updated. To appear in Combinatorics, Probability & ComputingCategories: math.COThis paper initiates the explicit study of face numbers of matroid polytopes and their computation. We prove that, for the large class of split matroid polytopes, their face numbers depend solely on the number of cyclic flats of each rank and size, together with information on the modular pairs of cyclic flats. We provide a formula which allows us to calculate $f$-vectors without the need of taking convex hulls or computing face lattices. We discuss the particular cases of sparse paving matroids and rank two matroids, which are of independent interest due to their appearances in other combinatorial and geometric settings.
-
arXiv:2307.10852 (Published 2023-07-20)
Examples and counterexamples in Ehrhart theory
Comments: Comments welcome!This article provides a comprehensive exposition about inequalities that the coefficients of Ehrhart polynomials and $h^*$-polynomials satisfy under various assumptions. We pay particular attention to the properties of Ehrhart positivity as well as unimodality, log-concavity and real-rootedness for $h^*$-polynomials. We survey inequalities that arise when the polytope has different normality properties. We include statements previously unknown in the Ehrhart theory setting, as well as some original contributions in this topic. We address numerous variations of the conjecture asserting that IDP polytopes have a unimodal $h^*$-polynomial, and construct concrete examples that show that these variations of the conjecture are false. Explicit emphasis is put on polytopes arising within algebraic combinatorics. Furthermore, we describe and construct polytopes having pathological properties on their Ehrhart coefficients and roots, and we indicate for the first time a connection between the notions of Ehrhart positivity and $h^*$-real-rootedness. We investigate the log-concavity of the sequence of evaluations of an Ehrhart polynomial at the non-negative integers. We conjecture that IDP polytopes have a log-concave Ehrhart series. Many additional problems and challenges are proposed.
-
Kazhdan-Lusztig polynomials of braid matroids
Comments: 15 pages. Final version, to appear in Communications of the American Mathematical SocietyCategories: math.COWe provide a combinatorial interpretation of the Kazhdan--Lusztig polynomial of the matroid arising from the braid arrangement of type $\mathrm{A}_{n-1}$, which gives an interpretation of the intersection cohomology Betti numbers of the reciprocal plane of the braid arrangement. Moreover, we prove an equivariant version of this result. The key combinatorial object is a class of matroids arising from series-parallel networks. As a consequence, we prove a conjecture of Elias, Proudfoot, and Wakefield on the top coefficient of Kazhdan--Lusztig polynomials of braid matroids, and we provide explicit generating functions for their Kazhdan--Lusztig and $Z$-polynomials.
-
arXiv:2212.03190 (Published 2022-12-06)
Hilbert-Poincaré series of matroid Chow rings and intersection cohomology
Comments: 54 pages, 2 Figures. Comments are welcome!We study the Hilbert series of four objects arising in the Chow-theoretic and Kazhdan-Lusztig framework of matroids. These are, respectively, the Hilbert series of the Chow ring, the augmented Chow ring, the intersection cohomology module, and its stalk at the empty flat. We develop a parallelism between the Kazhdan-Lusztig polynomial of a matroid and the Hilbert series of its Chow ring. This extends to a parallelism between the $Z$-polynomial of a matroid and the Hilbert series of its augmented Chow ring. This suggests to bring ideas from one framework to the other. Our two main motivations are the real-rootedness conjecture for all of these polynomials, and the problem of computing them. We provide several intrinsic definitions of these invariants; also, by leveraging that they are valuations under matroid polytope subdivisions, we deduce a fast way for computing them for a large class of matroids. Uniform matroids are a case of combinatorial interest; we link the resulting polynomials with certain real-rooted families such as the (binomial) Eulerian polynomials, and we settle a conjecture of Hameister, Rao, and Simpson. Furthermore, we prove the real-rootedness of the Hilbert series of the augmented Chow rings of uniform matroids via a result of Haglund and Zhang; and in addition, we prove a version of a conjecture of Gedeon in the Chow setting: uniform matroids maximize coefficient-wisely these polynomials for matroids with fixed rank and size. By relying on the nonnegativity of the Kazhdan-Lusztig polynomials and the semi-small decompositions of Braden, Huh, Matherne, Proudfoot, and Wang, we strengthen the unimodality of the Hilbert series of Chow rings, augmented Chow rings, and intersection cohomologies to $\gamma$-positivity, a property for palindromic polynomials that lies between unimodality and real-rootedness; this settles a conjecture of Ferroni, Nasr, and Vecchi.
-
arXiv:2208.04893 (Published 2022-08-09)
Valuative invariants for large classes of matroids
Comments: 100 pages, 12 figures, comments are welcomeWe study an operation in matroid theory that allows one to transition a given matroid into another with more bases via relaxing a "stressed subset". This framework provides a new combinatorial characterization of the class of elementary split matroids, which is expected to be asymptotically predominant. Moreover, it permits to describe an explicit matroid subdivision of a hypersimplex, which in turn can be used to write down concrete formulas for the evaluations of any valuative invariant on these matroids. This shows that evaluations depend solely on the behavior of the invariant on a well-behaved small subclass of Schubert matroids that we call "cuspidal matroids". Along the way, we make an extensive summary of the tools and methods one might use to prove that an invariant is valuative, and we use them to provide new proofs of the valuativeness of several invariants. We address systematically the consequences of our approach for a comprehensive list of invariants. They include the volume and Ehrhart polynomial of base polytopes, the Tutte polynomial, Kazhdan-Lusztig polynomials, the Whitney numbers of the first and second kind, spectrum polynomials and a generalization of these by Denham, chain polynomials and Speyer's $g$-polynomials, as well as Chow rings of matroids and their Hilbert-Poincar\'e series. The flexibility of this setting allows us to give a unified explanation for several recent results regarding the listed invariants; furthermore, we emphasize it as a powerful computational tool to produce explicit data and concrete examples.
-
arXiv:2204.07132 (Published 2022-04-14)
On Merino--Welsh conjecture for split matroids
Comments: 5 pages, 1 figureCategories: math.COIn 1999 Merino and Welsh conjectured that evaluations of the Tutte polynomial of a graph satisfy an inequality. In this short article we show that the conjecture generalized to matroids holds for the large class of all split matroids by exploiting the structure of their lattice of cyclic flats. This class of matroids strictly contains all paving and copaving matroids.
-
arXiv:2202.11808 (Published 2022-02-23)
Lattice points in slices of prisms
Comments: 24 pages, 1 figure. Comments are welcome!We study the Ehrhart polynomials of certain slices of rectangular prisms. These polytopes are generalizations of the hypersimplex and are contained in the larger class of polypositroids introduced by Lam and Postnikov. We give a combinatorial formula for all the Ehrhart coefficients in terms of the number of weighted permutations satisfying certain compatibility properties. This result proves that all these polytopes are Ehrhart positive. Additionally, inspired by a result due to Early and Kim, we give a combinatorial interpretation for all the coefficients of the $h^*$-polynomial; this solves the problem of providing an interpretation for the numerator of the Hilbert series, also known as the $h$-vector of all algebras of Veronese type. As corollaries of our results, we obtain an expression for the volumes of these slices of prisms as weighted combinations of Eulerian numbers; we use this to provide some generalizations of Laplace's result on the combinatorial interpretation of the volume of the hypersimplex. We discuss an application regarding a generalization of the flag Eulerian numbers and certain refinements, and give a short proof of the Ehrhart positivity of the independence polytope of all uniform matroids.
-
Stressed hyperplanes and Kazhdan-Lusztig gamma-positivity for matroids
Comments: 42 pages. Revised versionCategories: math.COIn this article we make several contributions of independent interest. First, we introduce the notion of stressed hyperplane of a matroid, essentially a type of cyclic flat that permits to transition from a given matroid into another with more bases. Second, we prove that the framework provided by the stressed hyperplanes allows one to write very concise closed formulas for the Kazhdan--Lusztig, inverse Kazhdan--Lusztig and $Z$-polynomials of all paving matroids, a class which is conjectured to predominate among matroids. Third, noticing the palindromicity of the $Z$-polynomial, we address its $\gamma$-positivity, a midpoint between unimodality and real-rootedness. To this end, we introduce the \emph{$\gamma$-polynomial} associated to it, we study some of its basic properties and we find closed expressions for it in the case of paving matroids. Also, we prove that it has positive coefficients in many interesting cases, particularly in the large family of sparse paving matroids, and other smaller classes such as projective geometries, thagomizer matroids and other particular graphs. Our last contribution consists of providing explicit combinatorial interpretations for the coefficients of many of the polynomials addressed in this article by enumerating fillings in certain Young tableaux and skew Young tableaux.
-
arXiv:2106.08183 (Published 2021-06-15)
Ehrhart polynomials of rank two matroids
Comments: 12 pagesCategories: math.COOver a decade ago De Loera, Haws and K\"oppe conjectured that Ehrhart polynomials of matroid polytopes have only positive coefficients. This intensively studied conjecture has recently been disproved by the first author who gave counterexamples of all ranks greater or equal to three. In this article we complete the picture by showing that Ehrhart polynomials of matroids of lower rank have indeed only positive coefficients. Moreover, we show that they are coefficient-wise bounded by the minimal and the uniform matroid.
-
arXiv:2105.04465 (Published 2021-05-10)
Matroids are not Ehrhart positive
Comments: 6 pagesCategories: math.COIn this article we disprove the conjectures asserting the positivity of the coefficients of the Ehrhart polynomial of matroid polytopes by De Loera, Haws and K\"oppe (2007) and of generalized permutohedra by Castillo and Liu (2018). We prove the existence of a matroid with $20$ elements and rank $9$ whose Ehrhart polynomial has some negative coefficients.
-
arXiv:2104.14531 (Published 2021-04-29)
Matroid relaxations and Kazhdan-Lusztig non-degeneracy
Comments: 16 pagesCategories: math.COIn this paper we address a variant of the Kazhdan-Lusztig non-degeneracy conjecture posed by Gedeon, Proudfoot and Young. We prove that if $M$ has a free basis (something that conjecturally asymptotically all matroids are expected to possess), then $M$ is non-degenerate. To this end, we study the behavior of Kazhdan-Lusztig polynomials of matroids with respect to the operation of circuit-hyperplane relaxation. This yields a family of polynomials that relate the Kazhdan-Lusztig, the inverse Kazhdan-Lusztig and the $Z$-polynomial of a matroid with those of its relaxations and do not depend on the matroid. As an application of our results, we deduce that uniform matroids maximize coefficient-wise the Kazhdan-Lusztig polynomials, inverse Kazhdan-Lusztig polynomials and the $Z$-polynomials, when restricted to sparse paving matroids.
-
arXiv:2012.04711 (Published 2020-12-08)
Integer point enumeration on independence polytopes and half-open hypersimplices
Comments: 7 pagesCategories: math.COIn this paper we investigate the Ehrhart Theory of the independence matroid polytope of uniform matroids. It is proved that these polytopes have an Ehrhart polynomial with positive coefficients. To do that, we prove that indeed all half-open-hypersimplices are Ehrhart positive, and tile disjointly our polytope using them.
-
arXiv:2003.02679 (Published 2020-03-05)
On the Ehrhart Polynomial of Minimal Matroids
Comments: 14 pages, 1 figureCategories: math.COWe provide a formula for the Ehrhart polynomial of the connected matroid of size $n$ and rank $k$ with the least number of bases, also known as a minimal matroid [9]. We prove that their polytopes are Ehrhart positive and $h^*$-real-rooted (and hence unimodal). We use our formula for these Ehrhart polynomials to prove that the operation of circuit-hyperplane relaxation of a matroid preserves Ehrhart positivity. We state two conjectures: that indeed all matroids are $h^*$-real-rooted, and that the coefficients of the Ehrhart polynomial of a connected matroid of fixed rank and cardinality are bounded by those of the corresponding minimal matroid and the corresponding uniform matroid.
-
arXiv:1911.10146 (Published 2019-11-22)
Uniform Matroids are Ehrhart Positive
Comments: 10 pages, 2 tablesCategories: math.COIn [1] De Loera et al. conjectured that the Ehrhart polynomial of the basis polytope of a matroid has positive coefficients. We prove this conjecture for all uniform matroids. In other words, we prove that every hypersimplex is Ehrhart positive. In order to do that, we introduce the notion of weighted Lah numbers and study some of their properties. Then we provide a formula for the coefficients of the Ehrhart polynomial of a hypersimplex in terms of these numbers.