betaFeedback

WorksMathematics

Goodman-type lower bounds for graph homomorphism densities

Abstract

For a finite graph HH with v(H)v(H) vertices, chromatic number χ(H)χ(H), and chromatic polynomial PHP_H, define ΦH(p)=(1−p)v(H)PH((1−p)−1)Φ_H(p)=(1-p)^{v(H)}P_H((1-p)^{-1}). This polynomial interpolates the homomorphism densities of HH in balanced complete multipartite graphons. We study the lower bound t(H,W)≥ΦH(p)t(H,W)\geΦ_H(p) on the homomorphism density of HH in graphons WW of edge density p>1−1/(χ(H)−1)p>1-1/(χ(H)-1), which generalises Goodman's triangle bound. We prove the inequality for chordal graphs whose maximal cliques have equal size, for trivially perfect graphs, and for joins of a clique and an odd cycle. The proofs use entropy along clique trees and a convexity criterion for adding a universal vertex. We also prove that a nonbipartite graph satisfies the inequality at all sufficiently high edge densities if and only if its girth is odd. For a graph on nn vertices whose girth is odd, the bound holds whenever p>1−(72n12)−1p>1-(72n^{12})^{-1}. The proof combines Whitney's forest expansion with a spectral comparison of cycle densities. Finally, among the 117117 nonbipartite graphs on at most six vertices with no isolated vertices or isolated edges, exactly 9494 satisfy the bound. The main results are formally verified in Lean 4.

Introduction

Goodman’s inequality [5] gives the lower bound p(2p−1)p(2p-1) for the triangle homomorphism density of a graphon of edge density pp. Equality holds for balanced complete kk-partite graphons, whose edge densities are 1−1/k1-1/k. The exact minimum clique density at a given edge density was determined by Razborov [12] for triangles, by Nikiforov [11] for K4K_4, and by Reiher [14] for all cliques. In this paper we ask which graphs HH satisfy the polynomial lower bound obtained by interpolating their densities in balanced complete multipartite graphons.

All graphs are finite and simple. For a graph HH, write V(H)V(H) and E(H)E(H) for its vertex and edge sets, v(H)v(H) and e(H)e(H) for their cardinalities, dH(v)d_H(v) for the degree of a vertex vv, and χ(H)\chi(H) for the chromatic number. Let KsK_s, PsP_s, and CsC_s denote the complete graph, path, and cycle, respectively, each on ss vertices; K0K_0 is the empty graph. We use ⊔\sqcup for disjoint union. A graphon is a symmetric measurable function W ⁣:[0,1]2→[0,1]W\colon[0,1]^2 \to[0,1]; see Lovász [9]. The homomorphism densities of WW are defined by

t(H,W)=∫[0,1]V(H)∏uv∈E(H)W(xu,xv)∏v∈V(H)dxv,p=t(K2,W).t(H,W)=\int_{[0,1]^{V(H)}} \prod_{uv\in E(H)} W(x_u,x_v)\prod_{v\in V(H)} dx_v,\qquad p=t(K_2,W).

Let PHP_H be the chromatic polynomial of HH and define

ΦH(p)=(1−p)v(H)PH(11−p).(1)\Phi_H(p)=(1-p)^{v(H)}P_H\left(\frac{1}{1-p}\right). \tag*{(1)}

The expression in (1), initially defined for p<1p < 1, extends to a polynomial with ΦH(1)=1\Phi_H(1) = 1, since PHP_H is monic of degree v(H)v(H). For χ(H)≥2\chi(H) \ge2, we say that HH satisfies the Goodman-type lower bound if every graphon WW satisfies

t(H,W)≥ΦH(p)wheneverp>pH:=1−1χ(H)−1.(2)t(H,W) \ge\Phi_H(p) \qquad\text{whenever} \qquad p > p_H := 1 - \frac{1}{\chi(H)-1}. \tag*{(2)}

For H=K3H = K_3, we have ΦH(p)=p(2p−1)\Phi_H(p) = p(2p - 1).

For an integer k≥1k \ge1, the Turán graphon TkT_k is obtained by partitioning [0,1][0,1] into kk sets of equal size and assigning value zero within each part and value one between distinct parts. It satisfies

t(K2,Tk)=1−1k,t(H,Tk)=PH(k)kv(H)=ΦH(1−1/k).(3)t(K_2,T_k) = 1 - \frac{1}{k}, \qquad t(H,T_k) = \frac{P_H(k)}{k^{v(H)}} = \Phi_H(1 - 1/k). \tag*{(3)}

Indeed, t(H,Tk)t(H,T_k) is the fraction of maps V(H)→{1,…,k}V(H) \to\{1,\ldots,k\} that are proper colourings. We call the numbers 1−1/k1 - 1/k Turán densities, and we say that TkT_k is optimal for HH if it minimises t(H,W)t(H,W) among graphons WW of edge density 1−1/k1 - 1/k, that is, if

t(K2,W)=1−1k⟹t(H,W)≥t(H,Tk).(4)t(K_2,W) = 1 - \frac{1}{k} \quad\Longrightarrow\quad t(H,W) \ge t(H,T_k). \tag*{(4)}

Thus (2) implies that TkT_k is optimal for HH for every integer k≥χ(H)k \ge\chi(H).

Im, Kim, and Yang [6, Section 8] introduced the polynomial (1) and the problem of classifying the graphs that satisfy (2). They also announced the chordal theorem for maximal cliques of equal size (Theorem 1.1), the results on clique joins in Section 3, and the obstruction for graphs of even girth (Proposition 4.17). We give complete proofs of these results and establish the further criteria and classifications stated below.

Chordal graphs

A graph is chordal if it has no induced cycle of length at least four. A clique tree of a graph is a tree whose vertices are its maximal cliques and in which the cliques containing any fixed vertex form a connected subtree. Such a tree exists for every connected chordal graph; see Gavril [3] and the account of clique trees by Blair and Peyton [1].

Theorem 1.1 (Chordal graphs with maximal cliques of equal size). Let HH be a connected chordal graph whose maximal cliques all have the same size k≥3k \ge3. Then HH satisfies the Goodman-type lower bound.

We deduce Theorem 1.1 from the following criterion, which also allows maximal cliques of different sizes.

Lemma 1.2. Let HH be a connected chordal graph of clique number k≥3k \ge3. Let C1,…,CmC_1,\ldots,C_m be its maximal cliques, and let TT be a clique tree. Let ri=∣Ci∣r_i = |C_i| and se=∣Ci∩Cj∣s_e = |C_i \cap C_j| for e=ij∈E(T)e = ij \in E(T), and define

bj=#{i:ri≥j}−#{e∈E(T):se≥j},1≤j≤k.(5)b_j = \#\{i : r_i \ge j\} - \#\{e \in E(T) : s_e \ge j\}, \qquad1 \le j \le k. \tag*{(5)}

If b1≤b2≤⋯≤bkb_1 \le b_2 \le\cdots\le b_k, then HH satisfies the Goodman-type lower bound.

As we show in Section 2, bjb_j is the multiplicity of j−1j - 1 as a root of PHP_H. The criterion therefore depends only on the chromatic polynomial. If every maximal clique has size kk, then bj=m−#{e:se≥j}b_j = m - \#\{e : s_e \ge j\} is nondecreasing, giving Theorem 1.1. The proof combines Lee’s entropy construction along a tree [7 Theorem 2.6] with the Moon–Moser recurrence for clique densities [10].

Trivially perfect graphs and clique joins

A graph is trivially perfect if it has no induced P4P_4 or C4C_4; see Golumbic [4]. Equivalently, these graphs are generated from K1K_1 by disjoint union and addition of a universal vertex, a vertex adjacent to every existing vertex [2].

Theorem 1.3 (Trivially perfect graphs). Every trivially perfect graph with at least one edge satisfies the Goodman-type lower bound.

Write F∨GF \vee G for the join of FF and GG, obtained from their disjoint union by adding every edge between the two vertex sets. We prove Theorem 1.3 by showing that addition of a universal vertex preserves the bound under a convexity hypothesis. Specifically, Proposition 3.2 shows that if FF satisfies the Goodman-type lower bound and ΦF\Phi_F is nonnegative, nondecreasing, and convex on [pF,1][p_F,1] with ΦF(pF)=0\Phi_F(p_F)=0, then K1∨FK_1 \vee F satisfies the bound, and ΦK1∨F\Phi_{K_1\vee F} has the same properties on the corresponding interval. This also applies to odd cycles, using the following result.

Theorem 1.4 (Im, Kim, and Yang [6]). For every odd integer ℓ≥3\ell\ge3 and every graphon WW of edge density p>1/2p > 1/2,

t(Cℓ,W)≥pℓ−p(1−p)ℓ−1=ΦCℓ(p).(6)t(C_\ell,W) \ge p^\ell- p(1-p)^{\ell-1} = \Phi_{C_\ell}(p). \tag*{(6)}

The range p≥2/3p \ge2/3 is proved in [6 Theorem 1.1], and the extension to p>1/2p > 1/2 is announced in [6 Section 8]. The accompanying Lean development includes the proof on the full range; see the paragraph on formal verification. The polynomial ΦCℓ\Phi_{C_\ell} satisfies the required convexity conditions on [1/2,1][1/2,1], so repeated addition of universal vertices gives the following consequence.

Corollary 1.5 (Clique joins of odd cycles). For every integer s≥0s \ge0 and every odd integer ℓ≥3\ell\ge3, the graph Ks∨CℓK_s \vee C_\ell satisfies the Goodman-type lower bound.

High densities and girth

We say that HH eventually satisfies the Goodman-type lower bound if there exists pH<1p_H < 1 such that t(H,W)≥ΦH(p)t(H,W) \ge\Phi_H(p) holds for every graphon of edge density p>pHp > p_H. For a graph containing a cycle, the girth is the length of a shortest cycle.

Theorem 1.6 (Eventual validity and girth). Let HH be a nonbipartite graph. The following are equivalent:

(i) For all sufficiently large integers kk, TkT_k minimises t(H,W)t(H,W) among graphons of edge density 1−1/k1-1/k.

(ii) The graph HH eventually satisfies the Goodman-type lower bound.

(iii) The girth of HH is odd.

Moreover, if the girth of HH is odd, then t(H,W)≥ΦH(p)t(H,W) \ge\Phi_H(p) for every graphon WW of edge density p>pHp > p_H, where

pH=1−172v(H)12;(7)p_H = 1-\frac{1}{72v(H)^{12}}; \tag*{(7)}

in particular, TkT_k is optimal for every integer k>72v(H)12k > 72v(H)^{12}.

The proof in § 4 writes W=1−UW=1-U and expands t(H,1−U)t(H,1-U), then groups the terms over forests using Whitney’s broken-circuit theorem. We estimate this sum through a spectral comparison of cycle densities and bounds on the number of cycles in HH. For even girth, the constant graphon violates the bound at every density sufficiently close to one.

Graphs on at most six vertices

Our last main result is a computer-assisted classification of small graphs. We identify graphs by their numbers in Read and Wilson’s An Atlas of Graphs [13].

Theorem 1.7 (Classification on at most six vertices). There are 117 unlabelled nonbipartite graphs on at most six vertices with no isolated vertices and no isolated edges. Of these, the 23 graphs in Figure 2 violate the Goodman-type lower bound, and the other 94 satisfy it.

Removing an isolated vertex or an isolated edge from HH divides both sides of (1.2) by 1 or by pp, respectively, and does not change χ(H)\chi(H). Hence a nonbipartite graph on at most six vertices satisfies the Goodman-type lower bound if and only if the graph obtained by deleting all its isolated vertices and isolated edges does.

The proof combines general density inequalities, estimates for individual graphs, and exact rational sum-of-squares certificates. Explicit graphons give the counterexamples. Each of the 117 cases has been formally verified in Lean. In § 5, we also give density ranges on which the violating graphs satisfy the bound and show that, for exactly 100 of the 117 graphs, TkT_k is optimal for every integer k≥χ(H)k \ge\chi(H).

The 23 graphs that violate the Goodman-type lower bound, labelled by their numbers in the Graph Atlas

Figure 2. The 23 graphs that violate the Goodman-type lower bound, labelled by their numbers in the Graph Atlas.

Organisation

§ 2 proves the criterion for chordal graphs. § 3 establishes the bound for trivially perfect graphs and clique joins of odd cycles. § 4 proves the characterisation by girth and the quantitative threshold. § 5 treats the classification on at most six vertices and optimality at Turán densities. § 6 discusses open problems, formal verification, and the use of AI tools.

A criterion for chordal graphs

We first express the chromatic polynomial through a clique tree. An entropy inequality then reduces the desired bound to a comparison of successive clique densities.

Clique-tree identities

References

  1. [1]J. R. S. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In A. George, J. R. Gilbert, and J. W. H. Liu, editors, Graph Theory and Sparse Matrix Computation, volume 56 of The IMA Volumes in Mathematics and its Applications, pages 1–29. Springer, New York, 1993. doi:10.1007/978-1-4613-8369-7_1.DOI
  2. [2]P. G. Drange and M. Pilipczuk. A polynomial kernel for trivially perfect editing. Algorithmica, 80(12):3481–3524, 2018. doi:10.1007/s00453-017-0401-6.DOI
  3. [3]F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1):47–56, 1974. doi:10.1016/0095-8956(74)90094-X.DOI
  4. [4]M. C. Golumbic. Trivially perfect graphs. Discrete Mathematics, 24(1):105–107, 1978. doi:10.1016/0012-365X(78)90178-4.DOI
  5. [5]A. W. Goodman. On sets of acquaintances and strangers at any party. The American Mathematical Monthly, 66(9):778–783, 1959. doi:10.1080/00029890.1959.11989408.DOI
  6. [6]S. Im, T. Kim, and H. Yang. Goodman-type lower bounds for odd cycles I: The dense regime, 2026. URL https://arxiv.org/abs/2610.18277. arXiv:2610.18277.
  7. [7]J. Lee. On some graph densities in locally dense graphs. Random Structures & Algorithms, 58(2):322–344, 2021. doi:10.1002/rsa.20974. URL https://arxiv.org/abs/1707.02916.
  8. [8]J. L. X. Li and B. Szegedy. On the logarithimic calculus and Sidorenko’s conjecture, 2011. URL https://arxiv.org/abs/1107.1153. arXiv:1107.1153.
  9. [9]L. Lovász. Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012. doi:10.1090/coll/060.DOI
  10. [10]J. W. Moon and L. Moser. On a problem of Turán. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 7:283–286, 1962. URL https://real.mtak.hu/201267/.
  11. [11]V. Nikiforov. The number of cliques in graphs of given order and size. Transactions of the American Mathematical Society, 363(3):1599–1618, 2011. doi:10.1090/S0002-9947-2010-05189-X.DOI
  12. [12]A. A. Razborov. On the minimal density of triangles in graphs. Combinatorics, Probability and Computing, 17(4):603–618, 2008. doi:10.1017/S0963548308009085.DOI
  13. [13]R. C. Read and R. J. Wilson. An Atlas of Graphs. Oxford University Press, Oxford, 1998. doi:10.1093/oso/9780198532897.001.0001.DOI
  14. [14]C. Reiher. The clique density theorem. Annals of Mathematics, 184(3):683–707, 2016. doi:10.4007/annals.2016.184.3.1.DOI
  15. [15]A. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combinatorics, 9:201–204, 1993. doi:10.1007/BF02988307.DOI
  16. [16]A. Sidorenko. A partially ordered set of functionals corresponding to graphs. Discrete Mathematics, 131(1–3):263–277, 1994. doi:10.1016/0012-365X(94)90388-3.DOI
  17. [17]A. D. Sokal. Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combinatorics, Probability and Computing, 10(1):41–77, 2001. doi:10.1017/S0963548300004612.DOI
  18. [18]B. Szegedy. An information theoretic approach to Sidorenko’s conjecture, 2014. URL https://arxiv.org/abs/1406.6738. arXiv:1406.6738, revised 2015.
  19. [19]H. Whitney. The coloring of graphs. Proceedings of the National Academy of Sciences of the United States of America, 17(2):122–125, 1931. doi:10.1073/pnas.17.2.122.DOI
  20. [20]H. Whitney. A logical expansion in mathematics. Bulletin of the American Mathematical Society, 38(8):572–579, 1932. doi:10.1090/S0002-9904-1932-05460-X.DOI

Paper details

vlnc:W_amvc7zy3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents