EUVIMEDEUVIMED entdecken
Crossref

Ultra Log-Concavity and Real-Rootedness of Dependence Polynomials

Yan-Ting Xie, Shou-Jun Xu

The Electronic Journal of Combinatorics · 09.10.2026 · 33 (4)

DOI: 10.37236/13310 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 09.10.2026. Verfasst von Yan-Ting Xie und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For some positive integer $m$, a real polynomial $P(x)=\sum\limits_{k=0}^ma_kx^k$ with $a_k\geqslant 0$ is called {log-concave} (resp. ultra log-concave) if $a_k^2\geqslant a_{k-1}a_{k+1}$ (resp. $a_k^2\geqslant \left(1+\frac{1}{k}\right)\left(1+\frac{1}{m-k}\right)\cdot$ $a_{k-1}a_{k+1}$) for all $1\leqslant k\leqslant 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):=\sum\limits_{k\geqslant 0}d_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\cup 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.

Zitieren

APA

Xie, Y., & Xu, S. (2026). Ultra Log-Concavity and Real-Rootedness of Dependence Polynomials. The Electronic Journal of Combinatorics, 33(4). https://doi.org/10.37236/13310

Vancouver

Xie Y, Xu S. Ultra Log-Concavity and Real-Rootedness of Dependence Polynomials. The Electronic Journal of Combinatorics. 2026;33(4). doi:10.37236/13310

BibTeX
@article{Xie2026,
  author = {Xie, Yan-Ting and Xu, Shou-Jun},
  title = {Ultra Log-Concavity and Real-Rootedness of Dependence Polynomials},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {4},
  doi = {10.37236/13310}
}
Kostenlos starten →