Ultra Log-Concavity and Real-Rootedness of Dependence Polynomials
Abstract
For some positive integer m, a real polynomial P(x)=∑k=0makxk with akgeqslant 0 is called {log-concave} (resp. ultra log-concave) if ak2geqslant ak−1ak+1 (resp. ak2geqslant (1+1/k)(1+1/(m−k))· ak−1ak+1) for all 1leqslant kleqslant m−1. If P(x) has only real roots, then it is called {real-rooted}. It is well-known that the conditions of log-concavity, ultra log-concavity and real-rootedness are ever-stronger. %A famous theorem due to Newton states that if a real polynomial with non-negative coefficients is real-rooted, then it is log-concave. For a graph G, a dependent set is a set of vertices which is not independent, i.e., the set of vertices whose induced subgraph contains at least one edge. The dependence polynomial of G is defined as D(G, x):=∑kgeqslant 0dk(G)xk, where dk(G) is the number of dependent sets of size k in G. Horrocks proved that $D(G, x)$ is log-concave for every graph G [J. Combin. Theory, Ser. B, 84 (2002) 180--185]. In the present paper, we prove that, for a graph G, $D(G, x)$ is ultra log-concave if G is (K2∪ 2K1)-free or contains an independent set of size |V(G)|−2, and give the characterization of graphs whose dependence polynomials are real-rooted. Finally, we focus more attention to the problems of log-concavity about independence systems and pose several conjectures closely related the famous Mason's Conjecture.
Related
- Real-rootedness and ultra log-concavity of rank-two matroid Ehrhart h*-polynomials
- The real-rootedness of the toric g-contribution polynomials
- Real-rootedness of Kazhdan--Lusztig polynomials of sparse paving matroids
- Real-rootedness of the Z-polynomials of sparse paving matroids and strict interlacing for uniform matroids
- Generalised hyperbolic polynomials: combinatorial interpretation and real-rootedness
BibTeX
@article{xie2026ultra,
title = {{Ultra Log-Concavity and Real-Rootedness of Dependence Polynomials}},
author = {Yan-Ting Xie and Shou-Jun Xu},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
month = oct,
doi = {10.37236/13310},
url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p9},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Ultra Log-Concavity and Real-Rootedness of Dependence Polynomials
AU - Yan-Ting Xie
AU - Shou-Jun Xu
PY - 2026
DA - 2026/10/09
JO - The Electronic Journal of Combinatorics
DO - 10.37236/13310
UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p9
AB - For some positive integer m, a real polynomial P(x)=∑_k=0^ma_kx^k with a_kgeqslant 0 is called {log-concave} (resp. ultra log-concave) if a_k^2geqslant a_k−1a_k+1 (resp. a_k^2geqslant (1+1/k)(1+1/(m−k))· a_k−1a_k+1) for all 1leqslant kleqslant m−1. If P(x) has only real roots, then it is called {real-rooted}. It is well-known that the conditions of log-concavity, ultra log-concavity and real-rootedness are ever-stronger. %A famous theorem due to Newton states that if a real polynomial with non-negative coefficients is real-rooted, then it is log-concave. For a graph G, a dependent set is a set of vertices which is not independent, i.e., the set of vertices whose induced subgraph contains at least one edge. The dependence polynomial of G is defined as D(G, x):=∑_kgeqslant 0d_k(G)x^k, where d_k(G) is the number of dependent sets of size k in G. Horrocks proved that $D(G, x)$ is log-concave for every graph G [J. Combin. Theory, Ser. B, 84 (2002) 180--185]. In the present paper, we prove that, for a graph G, $D(G, x)$ is ultra log-concave if G is (K_2∪ 2K_1)-free or contains an independent set of size |V(G)|−2, and give the characterization of graphs whose dependence polynomials are real-rooted. Finally, we focus more attention to the problems of log-concavity about independence systems and pose several conjectures closely related the famous Mason's Conjecture.
SN - 1077-8926
ER -