2024/08/17 by Yan-Ting Xie, Xie, Yan-Ting, Shou‐Jun Xu +1
Economics, Econometrics and Finance · Mathematics · #05B35 #05C31 #05E45 #Combinatorics (math.CO) #FOS: Mathematics #Functional Equations Stability Results #Stochastic processes and financial applications
paper · pdf · doi:10.48550/arxiv.2408.09152
openalex publication_date 2024/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For some positive integer m, a real polynomial P(x)=∑k=0makxk with ak\geqslant 0 is called log-concave (resp. ultra log-concave) if ak2\geqslant ak-1ak+1 (resp. ak2\geqslant (1+(1)/(k))(1+(1)/(m-k))⋅ ak-1ak+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. 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):=∑k\geqslant 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.