Search

Eulerian polynomials are fundamental in combinatorics and algebra. In this paper we study the linear transformation \mathcal {A}: \mathbb {R}[t] \to \mathbb {R}[t] defined by \mathcal {A}(t^n) = A_n(t), where A_n(t) denotes the n-th Eulerian polynomial. We give combinatorial, topological and Ehrhart theoretic interpretations of the operator \mathcal {A}, and investigate questions of unimodality and real-rootedness. In particular, we disprove a conjecture by Brenti (1989) concerning the preservation of real zeros, and generalize and strengthen recent results of Haglund and Zhang (2019) on binomial Eulerian polynomials. [ABSTRACT FROM AUTHOR]

In algebraic, topological, and geometric combinatorics, inequalities among the coefficients of combinatorial polynomials are frequently studied. Recently, a notion called the alternatingly increasing property, which is stronger than unimodality, was introduced. In this paper, we relate the alternatingly increasing property to real-rootedness of the symmetric decomposition of a polynomial to develop a systematic approach for proving the alternatingly increasing property for several classes of polynomials. We apply our results to strengthen and generalize real-rootedness, unimodality, and alternatingly increasing results pertaining to colored Eulerian and derangement polynomials, Ehrhart |$h^\ast$| -polynomials for lattice zonotopes, |$h$| -polynomials of barycentric subdivisions of doubly Cohen–Macaulay level simplicial complexes, and certain local |$h$| -polynomials for subdivisions of simplices. In particular, we prove two conjectures of Athanasiadis. [ABSTRACT FROM AUTHOR]

The generalized Lax conjecture asserts that each hyperbolicity cone is a linear slice of the cone of positive semidefinite matrices. Hyperbolic polynomials give rise to a class of (hyperbolic) matroids which properly contains the class of matroids representable over the complex numbers. This connection was used by the second author to construct counterexamples to algebraic (stronger) versions of the generalized Lax conjecture by considering a non-representable hyperbolic matroid. The Vámos matroid and a generalization of it are, prior to this work, the only known instances of non-representable hyperbolic matroids. We prove that the Non-Pappus and Non-Desargues matroids are non-representable hyperbolic matroids by exploiting a connection between Euclidean Jordan algebras and projective geometries. We further identify a large class of hyperbolic matroids which contains the Vámos matroid and the generalized Vámos matroids recently studied by Burton, Vinzant and Youm. This proves a conjecture of Burton et al . We also prove that many of the matroids considered here are non-representable. The proof of hyperbolicity for the matroids in the class depends on proving nonnegativity of certain symmetric polynomials. In particular we generalize and strengthen several inequalities in the literature, such as the Laguerre–Turán inequality and an inequality due to Jensen. Finally we explore consequences to algebraic versions of the generalized Lax conjecture. [ABSTRACT FROM AUTHOR]

McNamara and Sagan conjectured that if a0, a1, a2, ... is a Pólya frequency (PF) sequence, then so is a0², a1²- a0a2, a2² - a1a3, ... . We prove this conjecture for a natural class of PF-sequences which are interpolated by polynomials. In particular, this proves that the columns of Pascal's triangle are infinitely log-concave, as conjectured by McNamara and Sagan. We also give counterexamples to the first mentioned conjecture. Our methods provide families of nonlinear operators that preserve the property of having only real and nonpositive zeros. [ABSTRACT FROM AUTHOR]

We introduce an arithmetic version of the multivariate Tutte polynomial and a quasi-polynomial that interpolates between the two. A generalized Fortuin-Kasteleyn representation with applications to arithmetic colorings and flows is obtained. We give a new and more general proof of the positivity of the coefficients of the arithmetic Tutte polynomial and (in the representable case) a geometrical interpretation of them. [ABSTRACT FROM AUTHOR]

We give a complete characterization of multiplier sequences for generalized Laguerre bases. We also apply our methods to give a short proof of the characterization of Hermite multiplier sequences achieved by Piotrowski. [ABSTRACT FROM AUTHOR]

We characterize linear operators preserving zero-restrictions on entire functions in weighted Bargmann-Fock spaces. This extends the characterization of linear operators on polynomials preserv- ing stability (due to Borcea and the author) to the realm of entire functions, and translates into an optimal, albeit formal, Lee-Yang theorem. [ABSTRACT FROM AUTHOR]

. The strong Rayleigh property is a new and robust negative dependence property that implies negative association; in fact it implies conditional negative association closed under external fields (CNA+). Suppose that and are two families of 0-1 random variables that satisfy the strong Rayleigh property and let . We show that { Z i} conditioned on is also strongly Rayleigh; this turns out to be an easy consequence of the results on preservation of stability of polynomials of Borcea & Brändén ( Invent. Math., 177, 2009, 521-569). This entails that a number of important π ps sampling algorithms, including Sampford sampling and Pareto sampling, are CNA+. As a consequence, statistics based on such samples automatically satisfy a version of the Central Limit Theorem for triangular arrays. [ABSTRACT FROM AUTHOR]

Abstract: In this note we settle two open problems in the theory of permanents by using recent results from other areas of mathematics. Both problems were recently discussed in Bapat’s survey [[2]R.B. Bapat, Recent developments and open problems in the theory of permanents, Math. Student 76 (2007) 55–69.]. Bapat conjectured that certain quotients of permanents, which generalize symmetric function means, are concave. We prove this conjecture by using concavity properties of hyperbolic polynomials. Motivated by problems on random point processes, Shirai and Takahashi raised the problem: Determine all real numbers for which the -permanent (or -determinant) is nonnegative for all positive semidefinite matrices. We give a complete solution to this problem by using recent results of Scott and Sokal on completely monotone functions. It turns out that the conjectured answer to the problem is false. [Copyright &y& Elsevier]

We study the effect on the zeros of generating functions of sequences under certain non-linear transformations. Characterizations of Pólya-Schur type are given of the transformations that preserve the property of having only real and non-positive zeros. In particular, if a polynomial a0 + a1 z + ⋯⋯ + anzn has only real and non-positive zeros, then so does the polynomial . This confirms a conjecture of Fisk, McNamara-Sagan and Stanley, respectively. A consequence is that if a polynomial has only real and non-positive zeros, then its Taylor coefficients form an infinitely log-concave sequence. We extend the results to transcendental entire functions in the Laguerre-Pólya class, and discuss the consequences to problems on iterated Turán inequalities, studied by Craven and Csordas. Finally, we propose a new approach to a conjecture of Boros and Moll. [ABSTRACT FROM AUTHOR]

The Heine-Stieltjes theorem describes the polynomial solutions, ( v, f) such that T( f)= vf, to specific second-order differential operators, T, with polynomial coefficients. We extend the theorem to concern all (nondegenerate) differential operators preserving the property of having only real zeros, thus solving a conjecture of B. Shapiro. The new methods developed are used to describe intricate interlacing relations between the zeros of different pairs of solutions. This extends recent results of Bourget, McMillen and Vargas for the Heun equation and answers their question of how to generalize their results to higher degrees. Many of the results are new even for the classical case. [ABSTRACT FROM AUTHOR]

Abstract: There has recently been ample interest in the question of which sets can be represented by linear matrix inequalities (LMIs). A necessary condition is that the set is rigidly convex, and it has been conjectured that rigid convexity is also sufficient. To this end Helton and Vinnikov conjectured that any real zero polynomial admits a determinantal representation with symmetric matrices. We disprove this conjecture. By relating the question of finding LMI representations to the problem of determining whether a polymatroid is representable over the complex numbers, we find a real zero polynomial such that no power of it admits a determinantal representation. The proof uses recent results of Wagner and Wei on matroids with the half-plane property, and the polymatroids associated to hyperbolic polynomials introduced by Gurvits. [Copyright &y& Elsevier]

Murota et al. have recently developed a theory of discrete convex analysis which concerns M-convex functions on jump systems. We introduce here a family of M-concave functions arising naturally from polynomials (over a field of generalized Puiseux series) with prescribed non-vanishing properties. This family contains several of the most well studied M-concave functions in the literature. In the language of tropical geometry, we study the tropicalization of the space of polynomials with the half-plane property and show that it is strictly contained in the space of M-concave functions. We also provide a short proof of Speyer's "hive theorem" which he used to give a new proof of Horn's conjecture on eigenvalues of sums of Hermitian matrices. [ABSTRACT FROM AUTHOR]

Abstract: A multivariate polynomial is stable if it is non-vanishing whenever all variables have positive imaginary parts. A matroid has the weak half-plane property (WHPP) if there exists a stable polynomial with support equal to the set of bases of the matroid. If the polynomial can be chosen with all of its non-zero coefficients equal to one then the matroid has the half-plane property (HPP). We describe a systematic method that allows us to reduce the WHPP to the HPP for large families of matroids. This method makes use of the Tutte group of a matroid. We prove that no projective geometry has the WHPP and that a binary matroid has the WHPP if and only if it is regular. We also prove that and fail to have the WHPP. [Copyright &y& Elsevier]

Abstract: The majorization order on induces a natural partial ordering on the space of univariate hyperbolic polynomials of degree n. We characterize all linear operators on polynomials that preserve majorization, and show that it is sufficient (modulo obvious degree constraints) to preserve hyperbolicity. [ABSTRACT FROM AUTHOR]

We prove that the symmetrizer of a permutation group preserves stability if and only if the group is orbit homogeneous. A consequence is that the hypothesis of permutation invariance in the Grace-Walsh-Szegő Coincidence Theorem cannot be relaxed. In the process we obtain a new characterization of the Grace-like polynomials, introduced by D. Ruelle, and prove that the class of such polynomials can be endowed with a natural multiplication. [ABSTRACT FROM AUTHOR]

In 1952 Lee and Yang proposed the program of analyzing phase transitions in terms of zeros of partition functions. Linear operators preserving non-vanishing properties are essential in this program and various contexts in complex analysis, probability theory, combinatorics, and matrix theory. We characterize all linear operators on finite or infinite-dimensional spaces of multivariate polynomials preserving the property of being non-vanishing whenever the variables are in prescribed open circular domains. In particular, this solves the higher dimensional counterpart of a long-standing classification problem originating from classical works of Hermite, Laguerre, Hurwitz and Pólya-Schur on univariate polynomials with such properties. [ABSTRACT FROM AUTHOR]

We describe all linear operators on spaces of multivariate polynomials preserving the property of being non-vanishing in open circular domains. This completes the multivariate generalization of the classification program initiated by Pólya–Schur for univariate real polynomials and provides a natural framework for dealing in a uniform way with Lee–Yang type problems in statistical mechanics, combinatorics, and geometric function theory. [ABSTRACT FROM AUTHOR]

Abstract: We study a group action on permutations due to Foata and Strehl and use it to prove that the descent generating polynomial of certain sets of permutations has a non-negative expansion in the basis , . This property implies symmetry and unimodality. We prove that the action is invariant under stack sorting which strengthens recent unimodality results of Bóna. We prove that the generalized permutation patterns (13–2) and (2–31) are invariant under the action and use this to prove unimodality properties for a -analog of the Eulerian numbers recently studied by Corteel, Postnikov, Steingrímsson and Williams. We also extend the action to linear extensions of sign-graded posets to give a new proof of the unimodality of the -Eulerian polynomials of sign-graded posets and a combinatorial interpretations (in terms of Stembridge’s peak polynomials) of the corresponding coefficients when expanded in the above basis. Finally, we prove that the statistic defined as the number of vertices of even height in the unordered decreasing tree of a permutation has the same distribution as the number of descents on any set of permutations invariant under the action. On restricting to the set of stack sortable permutations we recover a result of Kreweras. [Copyright &y& Elsevier]

Abstract: A polynomial f is said to have the half-plane property if there is an open half-plane , whose boundary contains the origin, such that f is non-zero whenever all the variables are in H. This paper answers several open questions relating multivariate polynomials with the half-plane property to matroid theory. [(1)] We prove that the support of a multivariate polynomial with the half-plane property is a jump system. This answers an open question posed by Choe, Oxley, Sokal and Wagner and generalizes their recent result claiming that the same is true whenever the polynomial is also homogeneous. [(2)] We prove that a multivariate multi-affine polynomial has the half-plane property (with respect to the upper half-plane) if and only if for all and . This is used to answer two open questions posed by Choe and Wagner regarding strongly Rayleigh matroids. [(3)] We prove that the Fano matroid is not the support of a polynomial with the half-plane property. This is the first instance of a matroid which does not appear as the support of a polynomial with the half-plane property and answers a question posed by Choe et al. We also discuss further directions and open problems. [Copyright &y& Elsevier]

Abstract: We say that a word w on a totally ordered alphabet avoids the word if there are no subsequences in w order-equivalent to . In this paper we suggest a new approach to the enumeration of words on at most k letters avoiding a given pattern. By studying an automaton which for fixed k generates the words avoiding a given pattern we derive several previously known results for these kind of problems, as well as many new. In particular, we give a simple proof of the formula (Electron. J. Combin. 5(1998) #R15) for exact asymptotics for the number of words on k letters of length n that avoids the pattern . Moreover, we give the first combinatorial proof of the exact formula (Enumeration of words with forbidden patterns, Ph.D. Thesis, University of Pennsylvania, 1998) for the number of words on k letters of length n avoiding a three letter permutation pattern. [Copyright &y& Elsevier]

The Narayana numbers are N(n,k)=(1/n)n/kn/k+1n/k+1. There are several natural statistics on Dyck paths with a distribution given by N(n,k). We show the equidistribution of Narayana statistics by computing the flag h-vector of J(2×n) in different ways. In the process we discover new Narayana statistics and provide co-statistics for the Narayana statistics so that the bi-statistics have a distribution given by Fu¨rlinger and Hofbauer's q-Narayana numbers. We interpret the flag h-vector in terms of semi-standard Young tableaux, which enables us to express the q-Narayana numbers in terms of Schur functions. We also introduce what we call pre-shellings of simplicial complexes. [Copyright &y& Elsevier]

We call a Stieltjes continued fraction with monic monomial numerators a Catalan continued fraction. Let ek(π) be the number of increasing subsequences of length k+1 in the permutation π. We prove that any Catalan continued fraction is the multivariate generating function of a family of statistics on the 132-avoiding permutations, each consisting of a (possibly infinite) linear combination of the eks. Moreover, there is an invertible linear transformation that translates between linear combinations of eks and the corresponding continued fractions. Some applications are given, one of which relates fountains of coins to 132-avoiding permutations according to number of inversions. Another relates ballot numbers to such permutations according to number of right-to-left maxima. [Copyright &y& Elsevier]