Introduction
Goodman’s inequality [5 ] gives the lower bound p ( 2 p − 1 ) p(2p-1) p ( 2 p − 1 ) for the triangle homomorphism density of a graphon of edge density p p p . Equality holds for balanced complete k k k -partite graphons, whose edge densities are 1 − 1 / k 1-1/k 1 − 1/ k . The exact minimum clique density at a given edge density was determined by Razborov [12 ] for triangles, by Nikiforov [11 ] for K 4 K_4 K 4 , and by Reiher [14 ] for all cliques. In this paper we ask which graphs H H H satisfy the polynomial lower bound obtained by interpolating their densities in balanced complete multipartite graphons.
All graphs are finite and simple. For a graph H H H , write V ( H ) V(H) V ( H ) and E ( H ) E(H) E ( H ) for its vertex and edge sets, v ( H ) v(H) v ( H ) and e ( H ) e(H) e ( H ) for their cardinalities, d H ( v ) d_H(v) d H ( v ) for the degree of a vertex v v v , and χ ( H ) \chi(H) χ ( H ) for the chromatic number. Let K s K_s K s , P s P_s P s , and C s C_s C s denote the complete graph, path, and cycle, respectively, each on s s s vertices; K 0 K_0 K 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] W : [ 0 , 1 ] 2 → [ 0 , 1 ] ; see Lovász [9 ] . The homomorphism densities of W W W are defined by
t ( H , W ) = ∫ [ 0 , 1 ] V ( H ) ∏ u v ∈ E ( H ) W ( x u , x v ) ∏ v ∈ V ( H ) d x v , p = t ( K 2 , 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). t ( H , W ) = ∫ [ 0 , 1 ] V ( H ) uv ∈ E ( H ) ∏ W ( x u , x v ) v ∈ V ( H ) ∏ d x v , p = t ( K 2 , W ) .
Let P H P_H P H be the chromatic polynomial of H H H and define
Φ H ( p ) = ( 1 − p ) v ( H ) P H ( 1 1 − p ) . (1) \Phi_H(p)=(1-p)^{v(H)}P_H\left(\frac{1}{1-p}\right). \tag*{(1)} Φ H ( p ) = ( 1 − p ) v ( H ) P H ( 1 − p 1 ) . (1)
The expression in (1) , initially defined for p < 1 p < 1 p < 1 , extends to a polynomial with Φ H ( 1 ) = 1 \Phi_H(1) = 1 Φ H ( 1 ) = 1 , since P H P_H P H is monic of degree v ( H ) v(H) v ( H ) . For χ ( H ) ≥ 2 \chi(H) \ge2 χ ( H ) ≥ 2 , we say that H H H satisfies the Goodman-type lower bound if every graphon W W W satisfies
t ( H , W ) ≥ Φ H ( p ) whenever p > p H : = 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)} t ( H , W ) ≥ Φ H ( p ) whenever p > p H := 1 − χ ( H ) − 1 1 . (2)
For H = K 3 H = K_3 H = K 3 , we have Φ H ( p ) = p ( 2 p − 1 ) \Phi_H(p) = p(2p - 1) Φ H ( p ) = p ( 2 p − 1 ) .
For an integer k ≥ 1 k \ge1 k ≥ 1 , the Turán graphon T k T_k T k is obtained by partitioning [ 0 , 1 ] [0,1] [ 0 , 1 ] into k k k sets of equal size and assigning value zero within each part and value one between distinct parts. It satisfies
t ( K 2 , T k ) = 1 − 1 k , t ( H , T k ) = P H ( k ) k v ( 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)} t ( K 2 , T k ) = 1 − k 1 , t ( H , T k ) = k v ( H ) P H ( k ) = Φ H ( 1 − 1/ k ) . (3)
Indeed, t ( H , T k ) t(H,T_k) t ( H , T k ) is the fraction of maps V ( H ) → { 1 , … , k } V(H) \to\{1,\ldots,k\} V ( H ) → { 1 , … , k } that are proper colourings. We call the numbers 1 − 1 / k 1 - 1/k 1 − 1/ k Turán densities , and we say that T k T_k T k is optimal for H H H if it minimises t ( H , W ) t(H,W) t ( H , W ) among graphons W W W of edge density 1 − 1 / k 1 - 1/k 1 − 1/ k , that is, if
t ( K 2 , W ) = 1 − 1 k ⟹ t ( H , W ) ≥ t ( H , T k ) . (4) t(K_2,W) = 1 - \frac{1}{k} \quad\Longrightarrow\quad t(H,W) \ge t(H,T_k). \tag*{(4)} t ( K 2 , W ) = 1 − k 1 ⟹ t ( H , W ) ≥ t ( H , T k ) . (4)
Thus (2) implies that T k T_k T k is optimal for H H H for every integer k ≥ χ ( H ) k \ge\chi(H) k ≥ χ ( 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 H H H be a connected chordal graph whose maximal cliques all have the same size k ≥ 3 k \ge3 k ≥ 3 . Then H H H 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 H H H be a connected chordal graph of clique number k ≥ 3 k \ge3 k ≥ 3 . Let C 1 , … , C m C_1,\ldots,C_m C 1 , … , C m be its maximal cliques, and let T T T be a clique tree. Let r i = ∣ C i ∣ r_i = |C_i| r i = ∣ C i ∣ and s e = ∣ C i ∩ C j ∣ s_e = |C_i \cap C_j| s e = ∣ C i ∩ C j ∣ for e = i j ∈ E ( T ) e = ij \in E(T) e = ij ∈ E ( T ) , and define
b j = # { i : r i ≥ j } − # { e ∈ E ( T ) : s e ≥ 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)} b j = # { i : r i ≥ j } − # { e ∈ E ( T ) : s e ≥ j } , 1 ≤ j ≤ k . (5) If b 1 ≤ b 2 ≤ ⋯ ≤ b k b_1 \le b_2 \le\cdots\le b_k b 1 ≤ b 2 ≤ ⋯ ≤ b k , then H H H satisfies the Goodman-type lower bound .
As we show in Section 2, b j b_j b j is the multiplicity of j − 1 j - 1 j − 1 as a root of P H P_H P H . The criterion therefore depends only on the chromatic polynomial. If every maximal clique has size k k k , then b j = m − # { e : s e ≥ j } b_j = m - \#\{e : s_e \ge j\} b j = m − # { e : s e ≥ 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 P 4 P_4 P 4 or C 4 C_4 C 4 ; see Golumbic [4 ] . Equivalently, these graphs are generated from K 1 K_1 K 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 ∨ G F \vee G F ∨ G for the join of F F F and G G G , 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 F F F satisfies the Goodman-type lower bound and Φ F \Phi_F Φ F is nonnegative, nondecreasing, and convex on [ p F , 1 ] [p_F,1] [ p F , 1 ] with Φ F ( p F ) = 0 \Phi_F(p_F)=0 Φ F ( p F ) = 0 , then K 1 ∨ F K_1 \vee F K 1 ∨ F satisfies the bound, and Φ K 1 ∨ F \Phi_{K_1\vee F} Φ K 1 ∨ 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 ℓ ≥ 3 and every graphon W W W of edge density p > 1 / 2 p > 1/2 p > 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)} t ( C ℓ , W ) ≥ p ℓ − p ( 1 − p ) ℓ − 1 = Φ C ℓ ( p ) . (6)
The range p ≥ 2 / 3 p \ge2/3 p ≥ 2/3 is proved in [6 Theorem 1.1] , and the extension to p > 1 / 2 p > 1/2 p > 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} Φ C ℓ satisfies the required convexity conditions on [ 1 / 2 , 1 ] [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 ≥ 0 s \ge0 s ≥ 0 and every odd integer ℓ ≥ 3 \ell\ge3 ℓ ≥ 3 , the graph K s ∨ C ℓ K_s \vee C_\ell K s ∨ C ℓ satisfies the Goodman-type lower bound.
High densities and girth
We say that H H H eventually satisfies the Goodman-type lower bound if there exists p H < 1 p_H < 1 p H < 1 such that t ( H , W ) ≥ Φ H ( p ) t(H,W) \ge\Phi_H(p) t ( H , W ) ≥ Φ H ( p ) holds for every graphon of edge density p > p H p > p_H p > 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 H H H be a nonbipartite graph. The following are equivalent:
(i) For all sufficiently large integers k k k , T k T_k T k minimises t ( H , W ) t(H,W) t ( H , W ) among graphons of edge density 1 − 1 / k 1-1/k 1 − 1/ k .
(ii) The graph H H H eventually satisfies the Goodman-type lower bound.
(iii) The girth of H H H is odd.
Moreover, if the girth of H H H is odd, then t ( H , W ) ≥ Φ H ( p ) t(H,W) \ge\Phi_H(p) t ( H , W ) ≥ Φ H ( p ) for every graphon W W W of edge density p > p H p > p_H p > p H , where
p H = 1 − 1 72 v ( H ) 12 ; (7) p_H = 1-\frac{1}{72v(H)^{12}}; \tag*{(7)} p H = 1 − 72 v ( H ) 12 1 ; (7) in particular, T k T_k T k is optimal for every integer k > 72 v ( H ) 12 k > 72v(H)^{12} k > 72 v ( H ) 12 .
The proof in § 4 writes W = 1 − U W=1-U W = 1 − U and expands t ( H , 1 − U ) 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 H H H . 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 H H H divides both sides of (1.2) by 1 or by p p p , respectively, and does not change χ ( H ) \chi(H) χ ( 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, T k T_k T k is optimal for every integer k ≥ χ ( H ) k \ge\chi(H) k ≥ χ ( H ) .
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
We use the clique tree and notation of Lemma 1.2. For the standard structural properties, see [1 ] . Root the tree at C 1 C_1 C 1 and order its cliques so that each parent precedes its children. Set S 1 = ∅ S_1 = \varnothing S 1 = ∅ . For each C i C_i C i with parent C π ( i ) C_{\pi(i)} C π ( i ) , set S i = C i ∩ C π ( i ) S_i = C_i \cap C_{\pi(i)} S i = C i ∩ C π ( i ) . For every i i i , let N i = C i ∖ S i N_i = C_i \setminus S_i N i = C i ∖ S i . The defining property of a clique tree gives
C i ∩ ⋃ h < i C h = S i . C_i \cap\bigcup_{h<i} C_h = S_i. C i ∩ h < i ⋃ C h = S i .
The sets N i N_i N i partition V ( H ) V(H) V ( H ) , and ∣ N i ∣ = r i − ∣ S i ∣ |N_i| = r_i - |S_i| ∣ N i ∣ = r i − ∣ S i ∣ . Among the ( r i 2 ) \binom{r_i}{2} ( 2 r i ) edges of C i C_i C i , precisely the ( ∣ S i ∣ 2 ) \binom{|S_i|}{2} ( 2 ∣ S i ∣ ) edges within S i S_i S i have appeared in an earlier clique. Counting each vertex and edge in the first clique containing it therefore gives
v ( H ) = ∑ i = 1 m ( r i − ∣ S i ∣ ) = ∑ i = 1 m r i − ∑ e ∈ E ( T ) s e , e ( H ) = ∑ i = 1 m ( ( r i 2 ) − ( ∣ S i ∣ 2 ) ) = ∑ i = 1 m ( r i 2 ) − ∑ e ∈ E ( T ) ( s e 2 ) . (8) \begin{aligned}
v(H) &= \sum_{i=1}^{m}(r_i-|S_i|)=\sum_{i=1}^{m}r_i-\sum_{e\in E(T)}s_e,\\
e(H) &= \sum_{i=1}^{m}\left(\binom{r_i}{2}-\binom{|S_i|}{2}\right)=\sum_{i=1}^{m}\binom{r_i}{2}-\sum_{e\in E(T)}\binom{s_e}{2}. \tag*{(8)}
\end{aligned} v ( H ) e ( H ) = i = 1 ∑ m ( r i − ∣ S i ∣ ) = i = 1 ∑ m r i − e ∈ E ( T ) ∑ s e , = i = 1 ∑ m ( ( 2 r i ) − ( 2 ∣ S i ∣ ) ) = i = 1 ∑ m ( 2 r i ) − e ∈ E ( T ) ∑ ( 2 s e ) . (8)
The last equality in each line uses S 1 = ∅ S_1=\varnothing S 1 = ∅ and the correspondence between each nonroot clique C i C_i C i and its edge to its parent in T T T .
Now fix an integer x ≥ k x \ge k x ≥ k and colour the cliques in the same order. When C i C_i C i is reached, its already coloured vertices are exactly those in S i S_i S i , and their colours are distinct. The vertices in N i N_i N i must receive distinct colours chosen from the remaining x − ∣ S i ∣ x-|S_i| x − ∣ S i ∣ colours. Thus each colouring of the preceding cliques has ∏ h = ∣ S i ∣ r i − 1 ( x − h ) \prod_{h=|S_i|}^{r_i-1}(x-h) ∏ h = ∣ S i ∣ r i − 1 ( x − h ) extensions to C i C_i C i . Multiplying these numbers of choices gives
P H ( x ) = ∏ i = 1 m ∏ h = ∣ S i ∣ r i − 1 ( x − h ) = ∏ j = 1 k ( x − j + 1 ) b j . P_H(x)=\prod_{i=1}^{m}\prod_{h=|S_i|}^{r_i-1}(x-h)=\prod_{j=1}^{k}(x-j+1)^{b_j}. P H ( x ) = i = 1 ∏ m h = ∣ S i ∣ ∏ r i − 1 ( x − h ) = j = 1 ∏ k ( x − j + 1 ) b j .
where the exponent of x − j + 1 x-j+1 x − j + 1 is # { i : ∣ S i ∣ < j ≤ r i } = b j \#\{i:|S_i|<j\le r_i\}=b_j # { i : ∣ S i ∣ < j ≤ r i } = b j by (1.5). Both sides are polynomials in x x x and agree for every integer x ≥ k x\ge k x ≥ k , so the identity holds for all x x x . In particular, b j b_j b j is the multiplicity of j − 1 j-1 j − 1 as a root of P H P_H P H . Each b j b_j b j is positive because H H H contains K k K_k K k . The colouring argument also gives χ ( H ) = k \chi(H)=k χ ( H ) = k . Since v ( H ) = ∑ j b j v(H)=\sum_j b_j v ( H ) = ∑ j b j , we obtain
Φ H ( p ) = ∏ j = 1 k c j ( p ) b j , c j ( p ) = 1 − ( j − 1 ) ( 1 − p ) . (9) \Phi_H(p)=\prod_{j=1}^{k}c_j(p)^{b_j},\qquad c_j(p)=1-(j-1)(1-p). \tag*{(9)} Φ H ( p ) = j = 1 ∏ k c j ( p ) b j , c j ( p ) = 1 − ( j − 1 ) ( 1 − p ) . (9)
An entropy inequality
We use entropy gluing as developed by Li and Szegedy [8 ] , Szegedy [18 ] , and Lee [7 ] . The construction below adapts Lee’s Markov-tree theorem [7 Theorem 2.6] to graphons. When all maximal cliques have the same size, the resulting bound is the clique case of [7 Theorem 2.7] . The monotonicity of ( b j ) (b_j) ( b j ) extends the entropy comparison to cliques of different sizes.
Proposition 2.1. Under the hypotheses of Lemma 1.2, every graphon W W W satisfies
t ( H , W ) ∏ j = 1 k − 1 t ( K j , W ) b j + 1 − b j ≥ t ( K k , W ) b k . (10) t(H,W)\prod_{j=1}^{k-1}t(K_j,W)^{b_{j+1}-b_j}\ge t(K_k,W)^{b_k}. \tag*{(10)} t ( H , W ) j = 1 ∏ k − 1 t ( K j , W ) b j + 1 − b j ≥ t ( K k , W ) b k . (10) Proof. First assume ε ≤ W ≤ 1 \varepsilon\le W\le1 ε ≤ W ≤ 1 for some ε > 0 \varepsilon>0 ε > 0 , so that all the entropies below are finite. For a random vector Z Z Z with coordinates in [ 0 , 1 ] [0,1] [ 0 , 1 ] and probability density f f f , write H ( Z ) = − ∫ f log f \mathcal{H}(Z)=-\int f\log f H ( Z ) = − ∫ f log f for its entropy. For a graph F F F , let p F p_F p F be the probability density on [ 0 , 1 ] V ( F ) [0,1]^{V(F)} [ 0 , 1 ] V ( F ) obtained by normalising the product of its edge values. Evaluated at Z = ( Z v ) v ∈ V ( F ) Z=(Z_v)_{v\in V(F)} Z = ( Z v ) v ∈ V ( F ) , it is
p F ( ( Z v ) v ∈ V ( F ) ) = 1 t ( F , W ) ∏ u v ∈ E ( F ) W ( Z u , Z v ) . p_F((Z_v)_{v\in V(F)})=\frac{1}{t(F,W)}\prod_{uv\in E(F)}W(Z_u,Z_v). p F (( Z v ) v ∈ V ( F ) ) = t ( F , W ) 1 uv ∈ E ( F ) ∏ W ( Z u , Z v ) . Applying Gibbs’ inequality to f f f and p F p_F p F gives
log t ( F , W ) ≥ H ( Z ) + ∑ u v ∈ E ( F ) E log W ( Z u , Z v ) . (11) \log t(F,W)\ge\mathcal{H}(Z)+\sum_{uv\in E(F)}\mathbb{E}\log W(Z_u,Z_v). \tag*{(11)} log t ( F , W ) ≥ H ( Z ) + uv ∈ E ( F ) ∑ E log W ( Z u , Z v ) . (11) Equality holds when Z Z Z has density p F p_F p F .
Let ( X 1 , … , X k ) (X_1,\ldots,X_k) ( X 1 , … , X k ) have joint density
p ( x 1 , … , x k ) = 1 t ( K k , W ) ∏ 1 ≤ a < b ≤ k W ( x a , x b ) . p(x_1,\ldots,x_k)=\frac{1}{t(K_k,W)}\prod_{1\le a<b\le k}W(x_a,x_b). p ( x 1 , … , x k ) = t ( K k , W ) 1 1 ≤ a < b ≤ k ∏ W ( x a , x b ) . For 1 ≤ j < k 1\le j<k 1 ≤ j < k , its first j j j coordinates have density
1 t ( K k , W ) ∫ [ 0 , 1 ] k − j ∏ 1 ≤ a < b ≤ k W ( x a , x b ) d x j + 1 ⋯ d x k . \frac{1}{t(K_k,W)}\int_{[0,1]^{k-j}}\prod_{1\le a<b\le k}W(x_a,x_b)\,\mathrm{d}x_{j+1}\cdots\mathrm{d}x_k. t ( K k , W ) 1 ∫ [ 0 , 1 ] k − j 1 ≤ a < b ≤ k ∏ W ( x a , x b ) d x j + 1 ⋯ d x k .
The joint density is invariant under coordinate permutations, so any j j j distinct coordinates have the same law as ( X 1 , … , X j ) (X_1,\ldots,X_j) ( X 1 , … , X j ) .
We will construct a random vector Y = ( Y v ) v ∈ V ( H ) Y=(Y_v)_{v\in V(H)} Y = ( Y v ) v ∈ V ( H ) along the rooted clique tree. On C 1 C_1 C 1 , use the law of ( X 1 , … , X r 1 ) (X_1,\ldots,X_{r_1}) ( X 1 , … , X r 1 ) defined above. For each subsequent clique C i C_i C i , order its vertices with those in S i = C i ∩ C π ( i ) S_i=C_i\cap C_{\pi(i)} S i = C i ∩ C π ( i ) first. Conditional on their assigned values, sample the coordinates in N i N_i N i according to the conditional law of ( X ∣ S i ∣ + 1 , … , X r i ) (X_{|S_i|+1},\ldots,X_{r_i}) ( X ∣ S i ∣ + 1 , … , X r i ) given ( X 1 , … , X ∣ S i ∣ ) (X_1,\ldots,X_{|S_i|}) ( X 1 , … , X ∣ S i ∣ ) ,
p ( x ∣ S i ∣ + 1 , … , x r i ∣ x 1 , … , x ∣ S i ∣ ) ∝ ∫ [ 0 , 1 ] k − r i ∏ 1 ≤ a < b ≤ k W ( x a , x b ) d x r i + 1 ⋯ d x k . p(x_{|S_i|+1},\ldots,x_{r_i}\mid x_1,\ldots,x_{|S_i|})
\propto\int_{[0,1]^{k-r_i}}\prod_{1\leq a<b\leq k}W(x_a,x_b)\,dx_{r_i+1}\cdots dx_k. p ( x ∣ S i ∣ + 1 , … , x r i ∣ x 1 , … , x ∣ S i ∣ ) ∝ ∫ [ 0 , 1 ] k − r i 1 ≤ a < b ≤ k ∏ W ( x a , x b ) d x r i + 1 ⋯ d x k .
The law already assigned to S i S_i S i agrees with this marginal, since S i S_i S i lies in the parent clique. Induction therefore shows that the coordinates on every C i C_i C i have the law of ( X 1 , … , X r i ) (X_1,\ldots,X_{r_i}) ( X 1 , … , X r i ) . By (1.5), with b k + 1 = 0 b_{k+1}=0 b k + 1 = 0 ,
b j − b j + 1 = # { i : r i = j } − # { e ∈ E ( T ) : s e = j } . b_j-b_{j+1}=\#\{i:r_i=j\}-\#\{e\in E(T):s_e=j\}. b j − b j + 1 = # { i : r i = j } − # { e ∈ E ( T ) : s e = j } .
The entropy chain rule gives
H ( Y ) = ∑ i H ( X 1 , … , X r i ) − ∑ e ∈ E ( T ) H ( X 1 , … , X s e ) = ∑ j = 1 k # { i : r i = j } H ( X 1 , … , X j ) − ∑ j = 1 k # { e ∈ E ( T ) : s e = j } H ( X 1 , … , X j ) = ∑ j = 1 k ( # { i : r i = j } − # { e ∈ E ( T ) : s e = j } ) H ( X 1 , … , X j ) = ∑ j = 1 k ( b j − b j + 1 ) H ( X 1 , … , X j ) . \begin{aligned}
\mathcal{H}(Y)
&=\sum_i\mathcal{H}(X_1,\ldots,X_{r_i})-\sum_{e\in E(T)}\mathcal{H}(X_1,\ldots,X_{s_e})\\
&=\sum_{j=1}^{k}\#\{i:r_i=j\}\mathcal{H}(X_1,\ldots,X_j)-\sum_{j=1}^{k}\#\{e\in E(T):s_e=j\}\mathcal{H}(X_1,\ldots,X_j)\\
&=\sum_{j=1}^{k}\left(\#\{i:r_i=j\}-\#\{e\in E(T):s_e=j\}\right)\mathcal{H}(X_1,\ldots,X_j)\\
&=\sum_{j=1}^{k}(b_j-b_{j+1})\mathcal{H}(X_1,\ldots,X_j).
\end{aligned} H ( Y ) = i ∑ H ( X 1 , … , X r i ) − e ∈ E ( T ) ∑ H ( X 1 , … , X s e ) = j = 1 ∑ k # { i : r i = j } H ( X 1 , … , X j ) − j = 1 ∑ k # { e ∈ E ( T ) : s e = j } H ( X 1 , … , X j ) = j = 1 ∑ k ( # { i : r i = j } − # { e ∈ E ( T ) : s e = j } ) H ( X 1 , … , X j ) = j = 1 ∑ k ( b j − b j + 1 ) H ( X 1 , … , X j ) .
Similarly, (2.1) gives
e ( H ) = ∑ i ( r i 2 ) − ∑ e ∈ E ( T ) ( s e 2 ) = ∑ j = 1 k ( # { i : r i = j } − # { e ∈ E ( T ) : s e = j } ) ( j 2 ) = ∑ j = 1 k ( b j − b j + 1 ) ( j 2 ) . \begin{aligned}
e(H)
&=\sum_i\binom{r_i}{2}-\sum_{e\in E(T)}\binom{s_e}{2}\\
&=\sum_{j=1}^{k}\left(\#\{i:r_i=j\}-\#\{e\in E(T):s_e=j\}\right)\binom{j}{2}\\
&=\sum_{j=1}^{k}(b_j-b_{j+1})\binom{j}{2}.
\end{aligned} e ( H ) = i ∑ ( 2 r i ) − e ∈ E ( T ) ∑ ( 2 s e ) = j = 1 ∑ k ( # { i : r i = j } − # { e ∈ E ( T ) : s e = j } ) ( 2 j ) = j = 1 ∑ k ( b j − b j + 1 ) ( 2 j ) .
Every edge of H H H lies in a clique, so its two coordinates in Y Y Y have the law of ( X 1 , X 2 ) (X_1,X_2) ( X 1 , X 2 ) . Applying (2.4) to Y Y Y and substituting these two identities, we obtain
log t ( H , W ) ≥ H ( Y ) + e ( H ) E log W ( X 1 , X 2 ) = ∑ j = 1 k ( b j − b j + 1 ) ( H ( X 1 , … , X j ) + ( j 2 ) E log W ( X 1 , X 2 ) ) . (12) \begin{aligned}
\log t(H,W)&\geq\mathcal{H}(Y)+e(H)\mathbb{E}\log W(X_1,X_2)\\
&=\sum_{j=1}^{k}(b_j-b_{j+1})\left(\mathcal{H}(X_1,\ldots,X_j)+\binom{j}{2}\mathbb{E}\log W(X_1,X_2)\right). \tag*{(12)}
\end{aligned} log t ( H , W ) ≥ H ( Y ) + e ( H ) E log W ( X 1 , X 2 ) = j = 1 ∑ k ( b j − b j + 1 ) ( H ( X 1 , … , X j ) + ( 2 j ) E log W ( X 1 , X 2 ) ) . (12)
Applying (2.4) to ( X 1 , … , X j ) (X_1,\ldots,X_j) ( X 1 , … , X j ) and K j K_j K j gives
H ( X 1 , … , X j ) + ( j 2 ) E log W ( X 1 , X 2 ) ≤ log t ( K j , W ) , \mathcal{H}(X_1,\ldots,X_j)+\binom{j}{2}\mathbb{E}\log W(X_1,X_2)\leq\log t(K_j,W), H ( X 1 , … , X j ) + ( 2 j ) E log W ( X 1 , X 2 ) ≤ log t ( K j , W ) ,
with equality for j = k j=k j = k by the choice of the joint density. Since b j − b j + 1 ≤ 0 b_j-b_{j+1}\le0 b j − b j + 1 ≤ 0 for j < k j<k j < k , substitution in (12) yields
log t ( H , W ) ≥ b k log t ( K k , W ) − ∑ j = 1 k − 1 ( b j + 1 − b j ) log t ( K j , W ) . \log t(H,W) \ge b_k\log t(K_k,W)-\sum_{j=1}^{k-1}(b_{j+1}-b_j)\log t(K_j,W). log t ( H , W ) ≥ b k log t ( K k , W ) − j = 1 ∑ k − 1 ( b j + 1 − b j ) log t ( K j , W ) .
Exponentiating proves (10) . For an arbitrary graphon, apply this result to W ε = ε + ( 1 − ε ) W W_\varepsilon=\varepsilon+(1-\varepsilon)W W ε = ε + ( 1 − ε ) W and let ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 . A telescoping product estimate gives ∣ t ( F , W ε ) − t ( F , W ) ∣ ≤ e ( F ) ε |t(F,W_\varepsilon)-t(F,W)|\le e(F)\varepsilon ∣ t ( F , W ε ) − t ( F , W ) ∣ ≤ e ( F ) ε for every fixed finite graph F F F . All powers in (10) are nonnegative integers, so the inequality passes to the limit.
Adjacent clique densities
The following is the graphon form of the classical clique recurrence of Moon and Moser [10 inequality (10)] .
Lemma 2.2. For every j ≥ 2 j\ge2 j ≥ 2 and every graphon,
j t ( K j , W ) 2 ≤ t ( K j − 1 , W ) t ( K j , W ) + ( j − 1 ) t ( K j − 1 , W ) t ( K j + 1 , W ) . (13) j t(K_j,W)^2\le t(K_{j-1},W)t(K_j,W)+(j-1)t(K_{j-1},W)t(K_{j+1},W). \tag*{(13)} j t ( K j , W ) 2 ≤ t ( K j − 1 , W ) t ( K j , W ) + ( j − 1 ) t ( K j − 1 , W ) t ( K j + 1 , W ) . (13)
Lemma 2.3. If p > 1 − 1 / ( k − 1 ) p>1-1/(k-1) p > 1 − 1/ ( k − 1 ) , then t ( K j , W ) > 0 t(K_j,W)>0 t ( K j , W ) > 0 for 1 ≤ j ≤ k 1\le j\le k 1 ≤ j ≤ k and
t ( K j , W ) t ( K j − 1 , W ) ≥ 1 − ( j − 1 ) ( 1 − p ) , 2 ≤ j ≤ k . \frac{t(K_j,W)}{t(K_{j-1},W)}\ge1-(j-1)(1-p),\qquad2\le j\le k. t ( K j − 1 , W ) t ( K j , W ) ≥ 1 − ( j − 1 ) ( 1 − p ) , 2 ≤ j ≤ k .
Proof. We have t ( K 1 , W ) = 1 t(K_1,W)=1 t ( K 1 , W ) = 1 and t ( K 2 , W ) = p > 0 t(K_2,W)=p>0 t ( K 2 , W ) = p > 0 , giving the bound for j = 2 j=2 j = 2 . Suppose 2 ≤ j < k 2\le j<k 2 ≤ j < k and both inequalities hold up to j j j . Then (13) gives
t ( K j + 1 , W ) ≥ t ( K j , W ) j − 1 ( j t ( K j , W ) t ( K j − 1 , W ) − 1 ) ≥ t ( K j , W ) j − 1 ( j ( 1 − ( j − 1 ) ( 1 − p ) ) − 1 ) = ( 1 − j ( 1 − p ) ) t ( K j , W ) > 0. \begin{aligned}
t(K_{j+1},W)\ge\frac{t(K_j,W)}{j-1}\left(j\frac{t(K_j,W)}{t(K_{j-1},W)}-1\right) \\
&\ge\frac{t(K_j,W)}{j-1}\left(j(1-(j-1)(1-p))-1\right) \\
&=(1-j(1-p))t(K_j,W)>0.
\end{aligned} t ( K j + 1 , W ) ≥ j − 1 t ( K j , W ) ( j t ( K j − 1 , W ) t ( K j , W ) − 1 ) ≥ j − 1 t ( K j , W ) ( j ( 1 − ( j − 1 ) ( 1 − p )) − 1 ) = ( 1 − j ( 1 − p )) t ( K j , W ) > 0.
Here 1 − j ( 1 − p ) > 0 1-j(1-p)>0 1 − j ( 1 − p ) > 0 because j ≤ k − 1 j\le k-1 j ≤ k − 1 and p > 1 − 1 / ( k − 1 ) p>1-1/(k-1) p > 1 − 1/ ( k − 1 ) . This proves the lemma by induction.
Proof of Lemma 1.2. Since t ( K 0 , W ) = t ( K 1 , W ) = 1 t(K_0,W)=t(K_1,W)=1 t ( K 0 , W ) = t ( K 1 , W ) = 1 , Proposition 2.1 and Lemma 2.3 give, for p > 1 − 1 / ( k − 1 ) p>1-1/(k-1) p > 1 − 1/ ( k − 1 ) ,
t ( H , W ) ≥ t ( K k , W ) b k ∏ j < k t ( K j , W ) b j + 1 − b j = ∏ j = 1 k ( t ( K j , W ) t ( K j − 1 , W ) ) b j ≥ ∏ j = 1 k c j ( p ) b j = Φ H ( p ) . t(H,W)\ge\frac{t(K_k,W)^{b_k}}{\prod_{j<k}t(K_j,W)^{b_{j+1}-b_j}}=\prod_{j=1}^{k}\left(\frac{t(K_j,W)}{t(K_{j-1},W)}\right)^{b_j}\ge\prod_{j=1}^{k}c_j(p)^{b_j}=\Phi_H(p). t ( H , W ) ≥ ∏ j < k t ( K j , W ) b j + 1 − b j t ( K k , W ) b k = j = 1 ∏ k ( t ( K j − 1 , W ) t ( K j , W ) ) b j ≥ j = 1 ∏ k c j ( p ) b j = Φ H ( p ) .
The graph H H H in Figure 1 has maximal cliques C 1 = { 1 , 2 , 3 , 5 } C_1=\{1,2,3,5\} C 1 = { 1 , 2 , 3 , 5 } , C 2 = { 1 , 2 , 3 , 4 } C_2=\{1,2,3,4\} C 2 = { 1 , 2 , 3 , 4 } , and C 3 = { 4 , 6 , 7 } C_3=\{4,6,7\} C 3 = { 4 , 6 , 7 } . The path C 1 C_1 C 1 -C 2 C_2 C 2 -C 3 C_3 C 3 is a clique tree, with clique sizes 4 , 4 , 3 4,4,3 4 , 4 , 3 and intersections of sizes 3 , 1 3,1 3 , 1 . Thus ( b 1 , b 2 , b 3 , b 4 ) = ( 1 , 2 , 2 , 2 ) (b_1,b_2,b_3,b_4)=(1,2,2,2) ( b 1 , b 2 , b 3 , b 4 ) = ( 1 , 2 , 2 , 2 ) , and Lemma 1.2 proves the Goodman-type lower bound for H H H .
Figure 1. The chordal graph H H H and its maximal cliques C 1 C_1 C 1 , C 2 C_2 C 2 , C 3 C_3 C 3 .
Universal vertices
We prove that adding a universal vertex preserves the bound when Φ F \Phi_F Φ F is nonnegative, nondecreasing, and convex on the relevant interval. The proof begins with a weighted inequality for triangle densities.
A weighted triangle inequality
For a graphon W W W , let d W ( x ) = ∫ W ( x , y ) d y d_W(x)=\int W(x,y)\,\mathrm{d}y d W ( x ) = ∫ W ( x , y ) d y be its degree function. Set
τ W ( x ) = ∫ W ( x , y ) W ( x , z ) W ( y , z ) d y d z , \tau_W(x)=\int W(x,y)W(x,z)W(y,z)\,\mathrm{d}y\,\mathrm{d}z, τ W ( x ) = ∫ W ( x , y ) W ( x , z ) W ( y , z ) d y d z ,
M j ( W ) = ∫ d W ( x ) j d x ( j ≥ 0 ) . M_j(W)=\int d_W(x)^j\,\mathrm{d}x\quad(j\geq0). M j ( W ) = ∫ d W ( x ) j d x ( j ≥ 0 ) .
Thus τ W ( x ) \tau_W(x) τ W ( x ) is the triangle density in W W W with one vertex fixed at x x x . For a graphon V V V , let ( T V f ) ( x ) = ∫ V ( x , y ) f ( y ) d y (T_Vf)(x)=\int V(x,y)f(y)\,\mathrm{d}y ( T V f ) ( x ) = ∫ V ( x , y ) f ( y ) d y denote its integral operator. We use the inner product ⟨ f , g ⟩ = ∫ f ( x ) g ( x ) d x \langle f,g\rangle=\int f(x)g(x)\,\mathrm{d}x ⟨ f , g ⟩ = ∫ f ( x ) g ( x ) d x on real L 2 [ 0 , 1 ] L^2[0,1] L 2 [ 0 , 1 ] .
Lemma 3.1. If p = ∫ W ( x , y ) d x d y > 0 p=\int W(x,y)\,\mathrm{d}x\,\mathrm{d}y>0 p = ∫ W ( x , y ) d x d y > 0 , then, for every integer h ≥ 0 h\geq0 h ≥ 0 ,
∫ d W ( x ) h τ W ( x ) d x ≥ ( 2 − 1 p ) M h + 2 ( W ) . (14) \int d_W(x)^h\tau_W(x)\,\mathrm{d}x\geq\left(2-\frac{1}{p}\right)M_{h+2}(W). \tag*{(14)} ∫ d W ( x ) h τ W ( x ) d x ≥ ( 2 − p 1 ) M h + 2 ( W ) . (14) Proof. Applying a b ≥ a + b − 1 ab\geq a+b-1 ab ≥ a + b − 1 to a = W ( x , y ) a=W(x,y) a = W ( x , y ) and b = W ( x , z ) b=W(x,z) b = W ( x , z ) , and then using the symmetry of W W W , we obtain
τ W ( x ) = ∫ W ( x , y ) W ( x , z ) W ( y , z ) d y d z ≥ ∫ ( W ( x , y ) + W ( x , z ) − 1 ) W ( y , z ) d y d z = ∫ W ( x , y ) d W ( y ) d y + ∫ W ( x , z ) d W ( z ) d z − p = 2 ( T W d W ) ( x ) − p . \begin{aligned}
\tau_W(x)&=\int W(x,y)W(x,z)W(y,z)\,\mathrm{d}y\,\mathrm{d}z\\
&\geq\int\bigl(W(x,y)+W(x,z)-1\bigr)W(y,z)\,\mathrm{d}y\,\mathrm{d}z\\
&=\int W(x,y)d_W(y)\,\mathrm{d}y+\int W(x,z)d_W(z)\,\mathrm{d}z-p\\
&=2(T_Wd_W)(x)-p.
\end{aligned} τ W ( x ) = ∫ W ( x , y ) W ( x , z ) W ( y , z ) d y d z ≥ ∫ ( W ( x , y ) + W ( x , z ) − 1 ) W ( y , z ) d y d z = ∫ W ( x , y ) d W ( y ) d y + ∫ W ( x , z ) d W ( z ) d z − p = 2 ( T W d W ) ( x ) − p . Multiplying by d W ( x ) h ≥ 0 d_W(x)^h\geq0 d W ( x ) h ≥ 0 and integrating in x x x gives
∫ d W ( x ) h τ W ( x ) d x ≥ 2 ∫ d W ( x ) h ( T W d W ) ( x ) d x − p ∫ d W ( x ) h d x = 2 ⟨ d W h , T W d W ⟩ − p M h ( W ) . \begin{aligned}
\int d_W(x)^h\tau_W(x)\,\mathrm{d}x
&\geq2\int d_W(x)^h(T_Wd_W)(x)\,\mathrm{d}x-p\int d_W(x)^h\,\mathrm{d}x\\
&=2\langle d_W^h,T_Wd_W\rangle-pM_h(W).
\end{aligned} ∫ d W ( x ) h τ W ( x ) d x ≥ 2 ∫ d W ( x ) h ( T W d W ) ( x ) d x − p ∫ d W ( x ) h d x = 2 ⟨ d W h , T W d W ⟩ − p M h ( W ) . Set U = 1 − W U=1-W U = 1 − W and q = 1 − p q=1-p q = 1 − p , so that d U = 1 − d W d_U=1-d_W d U = 1 − d W . Since T W d W = d W − q + T U d U T_Wd_W=d_W-q+T_Ud_U T W d W = d W − q + T U d U ,
⟨ d W h , T W d W ⟩ = ∫ d W ( x ) h ( T W d W ) ( x ) d x = ∫ d W ( x ) h ( d W ( x ) − q + ( T U d U ) ( x ) ) d x = ∫ d W ( x ) h + 1 d x − q ∫ d W ( x ) h d x + ∫ d W ( x ) h ( T U d U ) ( x ) d x = M h + 1 ( W ) − q M h ( W ) + ⟨ d W h , T U d U ⟩ . \begin{aligned}
\langle d_W^h,T_Wd_W\rangle
&=\int d_W(x)^h(T_Wd_W)(x)\,\mathrm{d}x\\
&=\int d_W(x)^h\bigl(d_W(x)-q+(T_Ud_U)(x)\bigr)\,\mathrm{d}x\\
&=\int d_W(x)^{h+1}\,\mathrm{d}x-q\int d_W(x)^h\,\mathrm{d}x+\int d_W(x)^h(T_Ud_U)(x)\,\mathrm{d}x\\
&=M_{h+1}(W)-qM_h(W)+\langle d_W^h,T_Ud_U\rangle.
\end{aligned} ⟨ d W h , T W d W ⟩ = ∫ d W ( x ) h ( T W d W ) ( x ) d x = ∫ d W ( x ) h ( d W ( x ) − q + ( T U d U ) ( x ) ) d x = ∫ d W ( x ) h + 1 d x − q ∫ d W ( x ) h d x + ∫ d W ( x ) h ( T U d U ) ( x ) d x = M h + 1 ( W ) − q M h ( W ) + ⟨ d W h , T U d U ⟩ .
Since d U ( x ) = ∫ U ( x , y ) d y d_U(x)=\int U(x,y)\,dy d U ( x ) = ∫ U ( x , y ) d y , symmetry of U U U gives
2 ( ⟨ d W h , T U d U ⟩ − ∫ d W ( x ) h d U ( x ) 2 d x ) = 2 ∫ U ( x , y ) d W ( x ) h d U ( y ) d x d y − 2 ∫ U ( x , y ) d W ( x ) h d U ( x ) d x d y = 2 ∫ U ( x , y ) d W ( x ) h ( d U ( y ) − d U ( x ) ) d x d y = ∫ U ( x , y ) d W ( x ) h ( d U ( y ) − d U ( x ) ) d x d y + ∫ U ( x , y ) d W ( y ) h ( d U ( x ) − d U ( y ) ) d x d y = ∫ U ( x , y ) ( d U ( y ) − d U ( x ) ) ( d W ( x ) h − d W ( y ) h ) d x d y \begin{aligned}
2\left(\langle d_W^h,T_Ud_U\rangle-\int d_W(x)^h d_U(x)^2\,dx\right)
=2\int U(x,y)d_W(x)^h d_U(y)\,dx\,dy-2\int U(x,y)d_W(x)^h d_U(x)\,dx\,dy \\
&=2\int U(x,y)d_W(x)^h(d_U(y)-d_U(x))\,dx\,dy \\
&=\int U(x,y)d_W(x)^h(d_U(y)-d_U(x))\,dx\,dy
+\int U(x,y)d_W(y)^h(d_U(x)-d_U(y))\,dx\,dy \\
&=\int U(x,y)(d_U(y)-d_U(x))(d_W(x)^h-d_W(y)^h)\,dx\,dy
\end{aligned} 2 ( ⟨ d W h , T U d U ⟩ − ∫ d W ( x ) h d U ( x ) 2 d x ) = 2 ∫ U ( x , y ) d W ( x ) h d U ( y ) d x d y − 2 ∫ U ( x , y ) d W ( x ) h d U ( x ) d x d y = 2 ∫ U ( x , y ) d W ( x ) h ( d U ( y ) − d U ( x )) d x d y = ∫ U ( x , y ) d W ( x ) h ( d U ( y ) − d U ( x )) d x d y + ∫ U ( x , y ) d W ( y ) h ( d U ( x ) − d U ( y )) d x d y = ∫ U ( x , y ) ( d U ( y ) − d U ( x )) ( d W ( x ) h − d W ( y ) h ) d x d y
where the last inequality follows from d U ( y ) − d U ( x ) = d W ( x ) − d W ( y ) d_U(y)-d_U(x)=d_W(x)-d_W(y) d U ( y ) − d U ( x ) = d W ( x ) − d W ( y ) and the monotonicity of t ↦ t h t\mapsto t^h t ↦ t h on [ 0 , 1 ] [0,1] [ 0 , 1 ] . Since d U = 1 − d W d_U=1-d_W d U = 1 − d W ,
∫ d W ( x ) h d U ( x ) 2 d x = ∫ d W ( x ) h ( 1 − d W ( x ) ) 2 d x = M h ( W ) − 2 M h + 1 ( W ) + M h + 2 ( W ) . \int d_W(x)^h d_U(x)^2\,dx=\int d_W(x)^h(1-d_W(x))^2\,dx
=M_h(W)-2M_{h+1}(W)+M_{h+2}(W). ∫ d W ( x ) h d U ( x ) 2 d x = ∫ d W ( x ) h ( 1 − d W ( x ) ) 2 d x = M h ( W ) − 2 M h + 1 ( W ) + M h + 2 ( W ) .
Combining these estimates and using q = 1 − p q=1-p q = 1 − p , we obtain
∫ d W ( x ) h τ W ( x ) d x ≥ 2 ⟨ d W h , T W d W ⟩ − p M h ( W ) = 2 M h + 1 ( W ) − ( 2 q + p ) M h ( W ) + 2 ⟨ d W h , T U d U ⟩ ≥ 2 M h + 1 ( W ) − ( 2 q + p ) M h ( W ) + 2 ∫ d W ( x ) h d U ( x ) 2 d x = 2 M h + 1 ( W ) − ( 2 q + p ) M h ( W ) + 2 ( M h ( W ) − 2 M h + 1 ( W ) + M h + 2 ( W ) ) = 2 M h + 2 ( W ) − 2 M h + 1 ( W ) + p M h ( W ) = ( 2 − 1 p ) M h + 2 ( W ) + 1 p ( M h + 2 ( W ) − 2 p M h + 1 ( W ) + p 2 M h ( W ) ) = ( 2 − 1 p ) M h + 2 ( W ) + 1 p ∫ d W ( x ) h ( d W ( x ) − p ) 2 d x ≥ ( 2 − 1 p ) M h + 2 ( W ) . \begin{aligned}
\int d_W(x)^h\tau_W(x)\,dx
&\ge2\langle d_W^h,T_Wd_W\rangle-pM_h(W)\\
&=2M_{h+1}(W)-(2q+p)M_h(W)+2\langle d_W^h,T_Ud_U\rangle\\
&\ge2M_{h+1}(W)-(2q+p)M_h(W)+2\int d_W(x)^h d_U(x)^2\,dx\\
&=2M_{h+1}(W)-(2q+p)M_h(W)+2(M_h(W)-2M_{h+1}(W)+M_{h+2}(W))\\
&=2M_{h+2}(W)-2M_{h+1}(W)+pM_h(W)\\
&=\left(2-\frac{1}{p}\right)M_{h+2}(W)+\frac{1}{p}(M_{h+2}(W)-2pM_{h+1}(W)+p^2M_h(W))\\
&=\left(2-\frac{1}{p}\right)M_{h+2}(W)+\frac{1}{p}\int d_W(x)^h(d_W(x)-p)^2\,dx\\
&\ge\left(2-\frac{1}{p}\right)M_{h+2}(W).
\end{aligned} ∫ d W ( x ) h τ W ( x ) d x ≥ 2 ⟨ d W h , T W d W ⟩ − p M h ( W ) = 2 M h + 1 ( W ) − ( 2 q + p ) M h ( W ) + 2 ⟨ d W h , T U d U ⟩ ≥ 2 M h + 1 ( W ) − ( 2 q + p ) M h ( W ) + 2 ∫ d W ( x ) h d U ( x ) 2 d x = 2 M h + 1 ( W ) − ( 2 q + p ) M h ( W ) + 2 ( M h ( W ) − 2 M h + 1 ( W ) + M h + 2 ( W )) = 2 M h + 2 ( W ) − 2 M h + 1 ( W ) + p M h ( W ) = ( 2 − p 1 ) M h + 2 ( W ) + p 1 ( M h + 2 ( W ) − 2 p M h + 1 ( W ) + p 2 M h ( W )) = ( 2 − p 1 ) M h + 2 ( W ) + p 1 ∫ d W ( x ) h ( d W ( x ) − p ) 2 d x ≥ ( 2 − p 1 ) M h + 2 ( W ) .
This proves the claim.
Adding a universal vertex
Proposition 3.2. Let F F F have n ≥ 2 n\ge2 n ≥ 2 vertices, and let 0 ≤ p < 1 0\le p<1 0 ≤ p < 1 . Suppose Φ F \Phi_F Φ F is nondecreasing and convex on [ p , 1 ] [p,1] [ p , 1 ] , with Φ F ( p ) = 0 \Phi_F(p)=0 Φ F ( p ) = 0 , and t ( F , V ) ≥ Φ F ( z ) t(F,V)\ge\Phi_F(z) t ( F , V ) ≥ Φ F ( z ) for every graphon V V V of edge density z > p z>p z > p . Then every graphon W W W of edge density p > 1 / ( 2 − p ) p>1/(2-p) p > 1/ ( 2 − p ) satisfies
t ( K 1 ∨ F , W ) ≥ Φ K 1 ∨ F ( p ) . t(K_1\vee F,W)\ge\Phi_{K_1\vee F}(p). t ( K 1 ∨ F , W ) ≥ Φ K 1 ∨ F ( p ) . Moreover, Φ K 1 ∨ F \Phi_{K_1\vee F} Φ K 1 ∨ F is nondecreasing and convex on [ 1 / ( 2 − p ) , 1 ] [1/(2-p),1] [ 1/ ( 2 − p ) , 1 ] , with Φ K 1 ∨ F ( 1 / ( 2 − p ) ) = 0 \Phi_{K_1\vee F}(1/(2-p))=0 Φ K 1 ∨ F ( 1/ ( 2 − p )) = 0 . Thus K 1 ∨ F K_1\vee F K 1 ∨ F satisfies the hypotheses of the proposition with 1 / ( 2 − p ) 1/(2-p) 1/ ( 2 − p ) in place of p p p .
Proof. For any c ∈ [ p , 1 ] c \in[p,1] c ∈ [ p , 1 ] , the tangent line to Φ F \Phi_F Φ F at c c c gives
t ( F , V ) ≥ Φ F ( c ) + Φ F ′ ( c ) ( z − c ) , 0 ≤ z ≤ 1. (15) t(F,V) \ge\Phi_F(c)+\Phi_F'(c)(z-c), \qquad0\le z\le1. \tag*{(15)} t ( F , V ) ≥ Φ F ( c ) + Φ F ′ ( c ) ( z − c ) , 0 ≤ z ≤ 1. (15)
For z > p z>p z > p , this follows from the assumed bound and convexity. For z ≤ p z\le p z ≤ p , nonnegativity of Φ F ′ ( c ) \Phi_F'(c) Φ F ′ ( c ) and convexity give
Φ F ( c ) + Φ F ′ ( c ) ( z − c ) ≤ Φ F ( c ) + Φ F ′ ( c ) ( p − c ) ≤ Φ F ( p ) = 0 ≤ t ( F , V ) . \begin{aligned}
\Phi_F(c)+\Phi_F'(c)(z-c)&\le\Phi_F(c)+\Phi_F'(c)(p-c)\\
&\le\Phi_F(p)=0\le t(F,V).
\end{aligned} Φ F ( c ) + Φ F ′ ( c ) ( z − c ) ≤ Φ F ( c ) + Φ F ′ ( c ) ( p − c ) ≤ Φ F ( p ) = 0 ≤ t ( F , V ) .
By definition,
t ( K 1 ∨ F , W ) = ∫ ( ∫ ∏ u v ∈ E ( F ) W ( y u , y v ) ∏ v ∈ V ( F ) W ( x , y v ) ∏ v ∈ V ( F ) d y v ) d x . t(K_1\vee F,W)=\int\left(\int\prod_{uv\in E(F)}W(y_u,y_v)\prod_{v\in V(F)}W(x,y_v)\prod_{v\in V(F)}dy_v\right)dx. t ( K 1 ∨ F , W ) = ∫ ∫ uv ∈ E ( F ) ∏ W ( y u , y v ) v ∈ V ( F ) ∏ W ( x , y v ) v ∈ V ( F ) ∏ d y v d x .
Fix x ∈ [ 0 , 1 ] x\in[0,1] x ∈ [ 0 , 1 ] with d W ( x ) > 0 d_W(x)>0 d W ( x ) > 0 , and define the map Q x : [ 0 , 1 ] → [ 0 , 1 ] Q_x:[0,1]\to[0,1] Q x : [ 0 , 1 ] → [ 0 , 1 ] by
Q x ( s ) : = inf { y ∈ [ 0 , 1 ] : ∫ 0 y W ( x , z ) d z ≥ s d W ( x ) } , s ∈ [ 0 , 1 ] . Q_x(s):=\inf\left\{y\in[0,1]:\int_0^y W(x,z)\,dz\ge s d_W(x)\right\},\qquad s\in[0,1]. Q x ( s ) := inf { y ∈ [ 0 , 1 ] : ∫ 0 y W ( x , z ) d z ≥ s d W ( x ) } , s ∈ [ 0 , 1 ] .
The map Q x Q_x Q x is nondecreasing and satisfies
∫ 1 { Q x ( s ) ≤ y } d s = 1 d W ( x ) ∫ 0 y W ( x , z ) d z , y ∈ [ 0 , 1 ] . \int\mathbf{1}_{\{Q_x(s)\le y\}}\,ds=\frac{1}{d_W(x)}\int_0^y W(x,z)\,dz,\qquad y\in[0,1]. ∫ 1 { Q x ( s ) ≤ y } d s = d W ( x ) 1 ∫ 0 y W ( x , z ) d z , y ∈ [ 0 , 1 ] .
Consequently, for every bounded measurable f : [ 0 , 1 ] → R f:[0,1]\to\mathbb{R} f : [ 0 , 1 ] → R ,
∫ f ( Q x ( s ) ) d s = 1 d W ( x ) ∫ f ( y ) W ( x , y ) d y . \int f(Q_x(s))\,ds=\frac{1}{d_W(x)}\int f(y)W(x,y)\,dy. ∫ f ( Q x ( s )) d s = d W ( x ) 1 ∫ f ( y ) W ( x , y ) d y .
Define the reweighted graphon
W x ( s , t ) = W ( Q x ( s ) , Q x ( t ) ) . W_x(s,t)=W(Q_x(s),Q_x(t)). W x ( s , t ) = W ( Q x ( s ) , Q x ( t )) .
Applying the integration identity for Q x Q_x Q x successively to the variables ( s v ) v ∈ V ( F ) (s_v)_{v\in V(F)} ( s v ) v ∈ V ( F ) , we obtain
t ( F , W x ) = ∫ ∏ u v ∈ E ( F ) W x ( s u , s v ) ∏ v ∈ V ( F ) d s v = ∫ ∏ u v ∈ E ( F ) W ( Q x ( s u ) , Q x ( s v ) ) ∏ v ∈ V ( F ) d s v = ∫ ∏ u v ∈ E ( F ) W ( y u , y v ) ( ∏ v ∈ V ( F ) W ( x , y v ) d W ( x ) ) ∏ v ∈ V ( F ) d y v = 1 d W ( x ) n ∫ ∏ u v ∈ E ( F ) W ( y u , y v ) ∏ v ∈ V ( F ) W ( x , y v ) ∏ v ∈ V ( F ) d y v . \begin{aligned}
t(F,W_x)&=\int\prod_{uv\in E(F)}W_x(s_u,s_v)\prod_{v\in V(F)}ds_v\\
&=\int\prod_{uv\in E(F)}W(Q_x(s_u),Q_x(s_v))\prod_{v\in V(F)}ds_v\\
&=\int\prod_{uv\in E(F)}W(y_u,y_v)\left(\prod_{v\in V(F)}\frac{W(x,y_v)}{d_W(x)}\right)\prod_{v\in V(F)}dy_v\\
&=\frac{1}{d_W(x)^n}\int\prod_{uv\in E(F)}W(y_u,y_v)\prod_{v\in V(F)}W(x,y_v)\prod_{v\in V(F)}dy_v.
\end{aligned} t ( F , W x ) = ∫ uv ∈ E ( F ) ∏ W x ( s u , s v ) v ∈ V ( F ) ∏ d s v = ∫ uv ∈ E ( F ) ∏ W ( Q x ( s u ) , Q x ( s v )) v ∈ V ( F ) ∏ d s v = ∫ uv ∈ E ( F ) ∏ W ( y u , y v ) v ∈ V ( F ) ∏ d W ( x ) W ( x , y v ) v ∈ V ( F ) ∏ d y v = d W ( x ) n 1 ∫ uv ∈ E ( F ) ∏ W ( y u , y v ) v ∈ V ( F ) ∏ W ( x , y v ) v ∈ V ( F ) ∏ d y v .
In particular, its edge density is
t ( K 2 , W x ) = 1 d W ( x ) 2 ∫ W ( y , z ) W ( x , y ) W ( x , z ) d y d z = τ W ( x ) d W ( x ) 2 . t(K_2,W_x)=\frac{1}{d_W(x)^2}\int W(y,z)W(x,y)W(x,z)\,dy\,dz=\frac{\tau_W(x)}{d_W(x)^2}. t ( K 2 , W x ) = d W ( x ) 2 1 ∫ W ( y , z ) W ( x , y ) W ( x , z ) d y d z = d W ( x ) 2 τ W ( x ) .
Multiplying the expression for t ( F , W x ) t(F,W_x) t ( F , W x ) by d W ( x ) n d_W(x)^n d W ( x ) n and integrating in x x x gives
t ( K 1 ∨ F , W ) = ∫ d W ( x ) n t ( F , W x ) d x . t(K_1\vee F,W)=\int d_W(x)^n t(F,W_x)\,dx. t ( K 1 ∨ F , W ) = ∫ d W ( x ) n t ( F , W x ) d x .
When d W ( x ) = 0 d_W(x)=0 d W ( x ) = 0 , the contribution of x x x is zero; we set W x = 0 W_x=0 W x = 0 there. Lemma 3.1, with h = n − 2 h=n-2 h = n − 2 , gives
∫ d W ( x ) n t ( K 2 , W x ) d x = ∫ d W ( x ) n − 2 τ W ( x ) d x ≥ ( 2 − 1 p ) M n ( W ) . \int d_W(x)^n t(K_2,W_x)\,dx=\int d_W(x)^{n-2}\tau_W(x)\,dx
\ge\left(2-\frac{1}{p}\right)M_n(W). ∫ d W ( x ) n t ( K 2 , W x ) d x = ∫ d W ( x ) n − 2 τ W ( x ) d x ≥ ( 2 − p 1 ) M n ( W ) .
For p > 1 / ( 2 − p ) p>1/(2-p) p > 1/ ( 2 − p ) , the point 2 − 1 / p 2-1/p 2 − 1/ p lies in ( p , 1 ] (p,1] ( p , 1 ] . Applying (3.2) at this point to each W x W_x W x and integrating gives
t ( K 1 ∨ F , W ) = ∫ d W ( x ) n t ( F , W x ) d x ≥ ∫ d W ( x ) n [ Φ F ( 2 − 1 p ) + Φ F ′ ( 2 − 1 p ) ( t ( K 2 , W x ) − ( 2 − 1 p ) ) ] d x = M n ( W ) Φ F ( 2 − 1 p ) + Φ F ′ ( 2 − 1 p ) ( ∫ d W ( x ) n t ( K 2 , W x ) d x − ( 2 − 1 p ) M n ( W ) ) ≥ M n ( W ) Φ F ( 2 − 1 p ) ≥ ( ∫ d W ( x ) d x ) n Φ F ( 2 − 1 p ) = p n Φ F ( 2 − 1 p ) . \begin{aligned}
t(K_1\vee F,W)
&=\int d_W(x)^n t(F,W_x)\,dx\\
&\ge\int d_W(x)^n\left[\Phi_F\left(2-\frac{1}{p}\right)+\Phi_F'\left(2-\frac{1}{p}\right)\left(t(K_2,W_x)-\left(2-\frac{1}{p}\right)\right)\right]\,dx\\
&=M_n(W)\Phi_F\left(2-\frac{1}{p}\right)+\Phi_F'\left(2-\frac{1}{p}\right)\left(\int d_W(x)^n t(K_2,W_x)\,dx-\left(2-\frac{1}{p}\right)M_n(W)\right)\\
&\ge M_n(W)\Phi_F\left(2-\frac{1}{p}\right)\\
&\ge\left(\int d_W(x)\,dx\right)^n\Phi_F\left(2-\frac{1}{p}\right)\\
&=p^n\Phi_F\left(2-\frac{1}{p}\right).
\end{aligned} t ( K 1 ∨ F , W ) = ∫ d W ( x ) n t ( F , W x ) d x ≥ ∫ d W ( x ) n [ Φ F ( 2 − p 1 ) + Φ F ′ ( 2 − p 1 ) ( t ( K 2 , W x ) − ( 2 − p 1 ) ) ] d x = M n ( W ) Φ F ( 2 − p 1 ) + Φ F ′ ( 2 − p 1 ) ( ∫ d W ( x ) n t ( K 2 , W x ) d x − ( 2 − p 1 ) M n ( W ) ) ≥ M n ( W ) Φ F ( 2 − p 1 ) ≥ ( ∫ d W ( x ) d x ) n Φ F ( 2 − p 1 ) = p n Φ F ( 2 − p 1 ) .
Here we use Φ F ′ ( 2 − 1 / p ) , Φ F ( 2 − 1 / p ) ≥ 0 \Phi_F'\left(2-1/p\right),\Phi_F\left(2-1/p\right)\ge0 Φ F ′ ( 2 − 1/ p ) , Φ F ( 2 − 1/ p ) ≥ 0 and the preceding bound on ∫ d W ( x ) n t ( K 2 , W x ) d x \int d_W(x)^n t(K_2,W_x)\,dx ∫ d W ( x ) n t ( K 2 , W x ) d x ; the last inequality follows from Jensen’s inequality. Since P K 1 ∨ F ( x ) = x P F ( x − 1 ) P_{K_1\vee F}(x)=xP_F(x-1) P K 1 ∨ F ( x ) = x P F ( x − 1 ) ,
Φ K 1 ∨ F ( p ) = p n Φ F ( 2 − 1 p ) . \Phi_{K_1\vee F}(p)=p^n\Phi_F\left(2-\frac{1}{p}\right). Φ K 1 ∨ F ( p ) = p n Φ F ( 2 − p 1 ) .
Thus K 1 ∨ F K_1\vee F K 1 ∨ F also satisfies the lower bound for p > 1 / ( 2 − p ) p>1/(2-p) p > 1/ ( 2 − p ) . For the second assertion, differentiating gives
Φ K 1 ∨ F ′ ( p ) = n p n − 1 Φ F ( 2 − 1 p ) + p n − 2 Φ F ′ ( 2 − 1 p ) , \Phi_{K_1\vee F}'(p)=np^{n-1}\Phi_F\left(2-\frac{1}{p}\right)+p^{n-2}\Phi_F'\left(2-\frac{1}{p}\right), Φ K 1 ∨ F ′ ( p ) = n p n − 1 Φ F ( 2 − p 1 ) + p n − 2 Φ F ′ ( 2 − p 1 ) ,
Φ K 1 ∨ F ′ ′ ( p ) = n ( n − 1 ) p n − 2 Φ F ( 2 − 1 p ) + 2 ( n − 1 ) p n − 3 Φ F ′ ( 2 − 1 p ) + p n − 4 Φ F ′ ′ ( 2 − 1 p ) . \Phi_{K_1\vee F}''(p)=n(n-1)p^{n-2}\Phi_F\left(2-\frac{1}{p}\right)+2(n-1)p^{n-3}\Phi_F'\left(2-\frac{1}{p}\right)
+p^{n-4}\Phi_F''\left(2-\frac{1}{p}\right). Φ K 1 ∨ F ′′ ( p ) = n ( n − 1 ) p n − 2 Φ F ( 2 − p 1 ) + 2 ( n − 1 ) p n − 3 Φ F ′ ( 2 − p 1 ) + p n − 4 Φ F ′′ ( 2 − p 1 ) .
These are nonnegative on [ 1 / ( 2 − p ) , 1 ] [1/(2-p),1] [ 1/ ( 2 − p ) , 1 ] , since 2 − 1 / p 2-1/p 2 − 1/ p lies in [ p , 1 ] [p,1] [ p , 1 ] there and Φ F , Φ F ′ , Φ F ′ ′ ≥ 0 \Phi_F,\Phi_F',\Phi_F''\ge0 Φ F , Φ F ′ , Φ F ′′ ≥ 0 on [ p , 1 ] [p,1] [ p , 1 ] . Finally,
Φ K 1 ∨ F ( 1 2 − p ) = Φ F ( p ) ( 2 − p ) n = 0. \Phi_{K_1\vee F}\left(\frac{1}{2-p}\right)=\frac{\Phi_F(p)}{(2-p)^n}=0. Φ K 1 ∨ F ( 2 − p 1 ) = ( 2 − p ) n Φ F ( p ) = 0.
Iterating Proposition 3.2 shows that, under its hypotheses, t ( K s ∨ F , W ) ≥ Φ K s ∨ F ( p ) t(K_s\vee F,W)\ge\Phi_{K_s\vee F}(p) t ( K s ∨ F , W ) ≥ Φ K s ∨ F ( p ) for every integer s ≥ 0 s\ge0 s ≥ 0 and every graphon W W W of edge density
p > 1 − 1 s + 1 / ( 1 − p ) . (16) p>1-\frac{1}{s+1/(1-p)}. \tag*{(16)} p > 1 − s + 1/ ( 1 − p ) 1 . (16)
Indeed, with p = p 0 p=p_0 p = p 0 , the thresholds obey p j + 1 = 1 / ( 2 − p j ) p_{j+1}=1/(2-p_j) p j + 1 = 1/ ( 2 − p j ) , or equivalently ( 1 − p j + 1 ) − 1 = ( 1 − p j ) − 1 + 1 (1-p_{j+1})^{-1}=(1-p_j)^{-1}+1 ( 1 − p j + 1 ) − 1 = ( 1 − p j ) − 1 + 1 ; by the second part of Proposition 3.2, the hypotheses are preserved at every step.
Proof of Corollary 1.5. For odd ℓ ≥ 3 \ell\ge3 ℓ ≥ 3 ,
Φ C ℓ ( p ) = p ( p ℓ − 1 − ( 1 − p ) ℓ − 1 ) . \Phi_{C_\ell}(p) = p(p^{\ell-1} - (1-p)^{\ell-1}). Φ C ℓ ( p ) = p ( p ℓ − 1 − ( 1 − p ) ℓ − 1 ) .
This polynomial is nonnegative on [ 1 / 2 , 1 ] [1/2,1] [ 1/2 , 1 ] , with Φ C ℓ ( 1 / 2 ) = 0 \Phi_{C_\ell}(1/2)=0 Φ C ℓ ( 1/2 ) = 0 . On the same interval, its derivatives satisfy
Φ C ℓ ′ ( p ) = p ℓ − 1 − ( 1 − p ) ℓ − 1 + ( ℓ − 1 ) p ( p ℓ − 2 + ( 1 − p ) ℓ − 2 ) ≥ 0 , \Phi'_{C_\ell}(p)=p^{\ell-1}-(1-p)^{\ell-1}+(\ell-1)p(p^{\ell-2}+(1-p)^{\ell-2})\ge0, Φ C ℓ ′ ( p ) = p ℓ − 1 − ( 1 − p ) ℓ − 1 + ( ℓ − 1 ) p ( p ℓ − 2 + ( 1 − p ) ℓ − 2 ) ≥ 0 ,
Φ C ℓ ′ ′ ( p ) = 2 ( ℓ − 1 ) ( p ℓ − 2 + ( 1 − p ) ℓ − 2 ) + ( ℓ − 1 ) ( ℓ − 2 ) p ( p ℓ − 3 − ( 1 − p ) ℓ − 3 ) ≥ 0. \Phi''_{C_\ell}(p)=2(\ell-1)(p^{\ell-2}+(1-p)^{\ell-2})+(\ell-1)(\ell-2)p(p^{\ell-3}-(1-p)^{\ell-3})\ge0. Φ C ℓ ′′ ( p ) = 2 ( ℓ − 1 ) ( p ℓ − 2 + ( 1 − p ) ℓ − 2 ) + ( ℓ − 1 ) ( ℓ − 2 ) p ( p ℓ − 3 − ( 1 − p ) ℓ − 3 ) ≥ 0.
Apply Theorem 1.4 and Proposition 3.2 and (16) with p = 1 / 2 p=1/2 p = 1/2 . Since χ ( K s ∨ C ℓ ) = s + 3 \chi(K_s\vee C_\ell)=s+3 χ ( K s ∨ C ℓ ) = s + 3 , the resulting threshold is the required one.
Trivially perfect graphs
Proof of Theorem 1.3. We use strong induction on v ( H ) v(H) v ( H ) , assuming that every trivially perfect graph F F F with at least one edge and v ( F ) < v ( H ) v(F)<v(H) v ( F ) < v ( H ) satisfies the Goodman-type lower bound, with Φ F \Phi_F Φ F nondecreasing and convex on [ p F , 1 ] [p_F,1] [ p F , 1 ] and Φ F ( p F ) = 0 \Phi_F(p_F)=0 Φ F ( p F ) = 0 .
The base case is a star H H H with m ≥ 1 m\ge1 m ≥ 1 leaves. Here p H = 0 p_H=0 p H = 0 , and Jensen’s inequality gives
t ( H , W ) = ∫ d W ( x ) m d x ≥ p m = Φ H ( p ) . t(H,W)=\int d_W(x)^m\,dx\ge p^m=\Phi_H(p). t ( H , W ) = ∫ d W ( x ) m d x ≥ p m = Φ H ( p ) .
The polynomial p m p^m p m is nondecreasing and convex on [ 0 , 1 ] [0,1] [ 0 , 1 ] and equals zero at p = 0 p=0 p = 0 .
If H H H is disconnected, write H = H 1 ⊔ H 2 H=H_1\sqcup H_2 H = H 1 ⊔ H 2 , where H 1 , H 2 H_1,H_2 H 1 , H 2 are nonempty. Since χ ( H ) = max { χ ( H 1 ) , χ ( H 2 ) } \chi(H)=\max\{\chi(H_1),\chi(H_2)\} χ ( H ) = max { χ ( H 1 ) , χ ( H 2 )} ,
t ( H , W ) = t ( H 1 , W ) t ( H 2 , W ) ≥ Φ H 1 ( p ) Φ H 2 ( p ) = Φ H ( p ) , p > p H . t(H,W)=t(H_1,W)t(H_2,W)\ge\Phi_{H_1}(p)\Phi_{H_2}(p)=\Phi_H(p),\qquad p>p_H. t ( H , W ) = t ( H 1 , W ) t ( H 2 , W ) ≥ Φ H 1 ( p ) Φ H 2 ( p ) = Φ H ( p ) , p > p H .
Here P H = P H 1 P H 2 P_H=P_{H_1}P_{H_2} P H = P H 1 P H 2 and v ( H ) = v ( H 1 ) + v ( H 2 ) v(H)=v(H_1)+v(H_2) v ( H ) = v ( H 1 ) + v ( H 2 ) give the last equality; if H i H_i H i is edgeless, then t ( H i , W ) = Φ H i ( p ) = 1 t(H_i,W)=\Phi_{H_i}(p)=1 t ( H i , W ) = Φ H i ( p ) = 1 . The product rule gives nonnegativity of Φ H ′ \Phi'_H Φ H ′ and Φ H ′ ′ \Phi''_H Φ H ′′ on [ p H , 1 ] [p_H,1] [ p H , 1 ] . Relabelling so that χ ( H 1 ) = χ ( H ) \chi(H_1)=\chi(H) χ ( H 1 ) = χ ( H ) , we have
Φ H ( p H ) = Φ H 1 ( p H 1 ) Φ H 2 ( p H ) = 0. \Phi_H(p_H)=\Phi_{H_1}(p_{H_1})\Phi_{H_2}(p_H)=0. Φ H ( p H ) = Φ H 1 ( p H 1 ) Φ H 2 ( p H ) = 0.
It remains to consider H = K 1 ∨ F H=K_1\vee F H = K 1 ∨ F , where F F F is trivially perfect and has an edge [2 ] . The induction hypothesis allows us to apply Proposition 3.2 with p = p F p=p_F p = p F . This gives the required bound and the required properties of Φ H \Phi_H Φ H , since χ ( H ) = χ ( F ) + 1 \chi(H)=\chi(F)+1 χ ( H ) = χ ( F ) + 1 and
1 2 − p F = 1 − 1 χ ( F ) = p H . \frac{1}{2-p_F}=1-\frac{1}{\chi(F)}=p_H. 2 − p F 1 = 1 − χ ( F ) 1 = p H .
Eventual validity and girth
We first expand t ( H , 1 − U ) − Φ H ( 1 − q ) t(H,1-U)-\Phi_H(1-q) t ( H , 1 − U ) − Φ H ( 1 − q ) over forests, where q = t ( K 2 , U ) q=t(K_2,U) q = t ( K 2 , U ) . When the girth is odd, estimates for tree and cycle densities give the lower bound for small maximum degree. We then pass from small maximum degree to small edge density. The section ends with the obstruction for even girth and the proof of Theorem 1.6 .
For a graphon U U U of edge density q q q , we use
d U ( x ) = ∫ U ( x , y ) d y , Δ U = ∥ d U ∥ ∞ , d_U(x)=\int U(x,y)\,dy,\qquad\Delta_U=\lVert d_U\rVert_\infty, d U ( x ) = ∫ U ( x , y ) d y , Δ U = ∥ d U ∥ ∞ ,
M j ( U ) = ∫ d U ( x ) j d x ( j ≥ 0 ) , Var ( d U ) = ∫ ( d U ( x ) − q ) 2 d x = M 2 ( U ) − q 2 . (17) M_j(U)=\int d_U(x)^j\,dx\quad(j\ge0),\qquad\operatorname{Var}(d_U)=\int(d_U(x)-q)^2\,dx=M_2(U)-q^2. \tag*{(17)} M j ( U ) = ∫ d U ( x ) j d x ( j ≥ 0 ) , Var ( d U ) = ∫ ( d U ( x ) − q ) 2 d x = M 2 ( U ) − q 2 . (17)
Here Var ( d U ) \operatorname{Var}(d_U) Var ( d U ) is the variance of the degree function, and the norm is the essential supremum. Thus 0 ≤ q ≤ Δ U ≤ 1 0\le q\le\Delta_U\le1 0 ≤ q ≤ Δ U ≤ 1 .
Expansion over forests
For A ⊆ E ( H ) A \subseteq E(H) A ⊆ E ( H ) , let H A = ( V ( H ) , A ) H_A=(V(H),A) H A = ( V ( H ) , A ) and define
r ( A ) = v ( H ) − comp ( H A ) , r(A)=v(H)-\operatorname{comp}(H_A), r ( A ) = v ( H ) − comp ( H A ) ,
where comp ( H A ) \operatorname{comp}(H_A) comp ( H A ) counts all connected components, including isolated vertices. Thus r ( A ) r(A) r ( A ) is the number of edges in a spanning forest of H A H_A H A .
Lemma 4.1. For every graph H H H and every graphon U U U of edge density q q q ,
Φ H ( 1 − q ) = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ q r ( A ) . (18) \Phi_H(1-q)=\sum_{A\subseteq E(H)}(-1)^{|A|}q^{r(A)}. \tag*{(18)} Φ H ( 1 − q ) = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ q r ( A ) . (18) t ( H , 1 − U ) = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ t ( H A , U ) . (19) t(H,1-U)=\sum_{A\subseteq E(H)}(-1)^{|A|}t(H_A,U). \tag*{(19)} t ( H , 1 − U ) = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ t ( H A , U ) . (19)
Proof. Whitney’s spanning-subgraph expansion [19 ] follows by inclusion–exclusion over monochromatic edges:
P H ( k ) = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ k comp ( H A ) ( k ∈ N ) . P_H(k)=\sum_{A\subseteq E(H)}(-1)^{|A|}k^{\operatorname{comp}(H_A)}
\qquad(k\in\mathbb{N}). P H ( k ) = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ k comp ( H A ) ( k ∈ N ) .
Both sides are polynomials in k k k , so the identity holds for all k ∈ R k\in\mathbb{R} k ∈ R . For q > 0 q>0 q > 0 , substituting k = 1 / q k=1/q k = 1/ q gives
Φ H ( 1 − q ) = q v ( H ) P H ( 1 / q ) = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ q v ( H ) − comp ( H A ) . \Phi_H(1-q)=q^{v(H)}P_H(1/q)=\sum_{A\subseteq E(H)}(-1)^{|A|}q^{v(H)-\operatorname{comp}(H_A)}. Φ H ( 1 − q ) = q v ( H ) P H ( 1/ q ) = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ q v ( H ) − comp ( H A ) .
Continuity gives the same formula at q = 0 q=0 q = 0 . Also,
t ( H , 1 − U ) = ∫ ∏ u v ∈ E ( H ) ( 1 − U ( x u , x v ) ) ∏ v ∈ V ( H ) d x v = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ ∫ ∏ u v ∈ A U ( x u , x v ) ∏ v ∈ V ( H ) d x v = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ t ( H A , U ) . \begin{aligned}
t(H,1-U)
&=\int\prod_{uv\in E(H)}(1-U(x_u,x_v))\prod_{v\in V(H)}dx_v\\
&=\sum_{A\subseteq E(H)}(-1)^{|A|}\int\prod_{uv\in A}U(x_u,x_v)\prod_{v\in V(H)}dx_v\\
&=\sum_{A\subseteq E(H)}(-1)^{|A|}t(H_A,U).
\end{aligned} t ( H , 1 − U ) = ∫ uv ∈ E ( H ) ∏ ( 1 − U ( x u , x v )) v ∈ V ( H ) ∏ d x v = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ ∫ uv ∈ A ∏ U ( x u , x v ) v ∈ V ( H ) ∏ d x v = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ t ( H A , U ) .
Subtracting the two identities gives
t ( H , 1 − U ) − Φ H ( 1 − q ) = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ ( t ( H A , U ) − q r ( A ) ) . t(H,1-U)-\Phi_H(1-q)=\sum_{A\subseteq E(H)}(-1)^{|A|}\left(t(H_A,U)-q^{r(A)}\right). t ( H , 1 − U ) − Φ H ( 1 − q ) = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ ( t ( H A , U ) − q r ( A ) ) .
The summands with r ( A ) = 0 r(A)=0 r ( A ) = 0 or r ( A ) = 1 r(A)=1 r ( A ) = 1 are zero: the empty edge set contributes 1 − 1 = 0 1-1=0 1 − 1 = 0 , and each single edge contributes − ( q − q ) = 0 -(q-q)=0 − ( q − q ) = 0 .
Fix a total order < < < on E ( H ) E(H) E ( H ) , and regard each forest F ⊆ E ( H ) F\subseteq E(H) F ⊆ E ( H ) as the spanning graph ( V ( H ) , F ) (V(H),F) ( V ( H ) , F ) . Let B ( F ) B(F) B ( F ) be the set of edges e ∈ E ( H ) ∖ F e\in E(H)\setminus F e ∈ E ( H ) ∖ F such that adding e e e to F F F creates a cycle and every other edge of this cycle precedes e e e in the fixed order. Set
I F ( U ) = ∫ ∏ u v ∈ F U ( x u , x v ) ∏ u v ∈ B ( F ) ( 1 − U ( x u , x v ) ) ∏ v ∈ V ( H ) d x v . I_F(U)=\int\prod_{uv\in F}U(x_u,x_v)\prod_{uv\in B(F)}(1-U(x_u,x_v))\prod_{v\in V(H)}dx_v. I F ( U ) = ∫ uv ∈ F ∏ U ( x u , x v ) uv ∈ B ( F ) ∏ ( 1 − U ( x u , x v )) v ∈ V ( H ) ∏ d x v .
Lemma 4.2. For every graphon U U U of edge density q q q ,
Φ H ( 1 − q ) = ∑ F f o r e s t B ( F ) = ∅ ( − 1 ) ∣ F ∣ q ∣ F ∣ , (20) \Phi_H(1-q)=\sum_{\substack{F\ \mathrm{forest}\\B(F)=\varnothing}}(-1)^{|F|}q^{|F|}, \tag*{(20)} Φ H ( 1 − q ) = F forest B ( F ) = ∅ ∑ ( − 1 ) ∣ F ∣ q ∣ F ∣ , (20) t ( H , 1 − U ) = ∑ F f o r e s t ( − 1 ) ∣ F ∣ I F ( U ) . (21) t(H,1-U)=\sum_{F\ \mathrm{forest}}(-1)^{|F|}I_F(U). \tag*{(21)} t ( H , 1 − U ) = F forest ∑ ( − 1 ) ∣ F ∣ I F ( U ) . (21) Here the sums range over forests F ⊆ E ( H ) F\subseteq E(H) F ⊆ E ( H ) .
Identity (4.4) is also known as Whitney’s broken-circuit theorem [20 ] , where a broken circuit is a cycle with its largest edge removed; B ( F ) = ∅ B(F)=\varnothing B ( F ) = ∅ if and only if F F F contains no broken circuit.
Proof. We first show that every A ⊆ E ( H ) A\subseteq E(H) A ⊆ E ( H ) has a unique representation
A = F ∪ ˙ D , F a forest , D ⊆ B ( F ) . A=F\mathbin{\dot\cup}D,\qquad F\text{ a forest},\quad D\subseteq B(F). A = F ∪ ˙ D , F a forest , D ⊆ B ( F ) .
Assign the weights 2 , 4 , … , 2 e ( H ) 2,4,\ldots,2^{e(H)} 2 , 4 , … , 2 e ( H ) to the edges of H H H in the fixed order. Given A ⊆ E ( H ) A\subseteq E(H) A ⊆ E ( H ) , let F F F be the minimum spanning forest of H A H_A H A . It is unique because different edge sets have different total weights. Adding an edge e ∈ A ∖ F e\in A\setminus F e ∈ A ∖ F to F F F creates a cycle. Every other edge in this cycle has smaller weight than e e e : otherwise, replacing a heavier edge by e e e would give a spanning forest of smaller total weight. Hence e ∈ B ( F ) e\in B(F) e ∈ B ( F ) , giving the required representation with D = A ∖ F D=A\setminus F D = A ∖ F .
For uniqueness, suppose A = F ∪ ˙ D A=F\mathbin{\dot\cup}D A = F ∪ ˙ D with F F F a forest and D ⊆ B ( F ) D\subseteq B(F) D ⊆ B ( F ) . Since every edge of D D D has its endpoints in the same component of F F F , the graphs F F F and H A H_A H A have the same components. Let F ′ F' F ′ be the minimum spanning forest of H A H_A H A . If F ≠ F ′ F\ne F' F = F ′ , choose e ∈ F ′ ∖ F ⊆ D e\in F'\setminus F\subseteq D e ∈ F ′ ∖ F ⊆ D . Adding e e e to F F F creates a cycle whose other edges all have smaller weight than e e e . As the weights are distinct powers of 2 2 2 , the sum of their weights is smaller than the weight of e e e . Replacing e e e in F ′ F' F ′ by these other edges gives a graph with the same components as H A H_A H A and smaller total weight than F ′ F' F ′ . A spanning forest of this graph would also have smaller total weight than F ′ F' F ′ , contradicting its minimality. Thus F = F ′ F=F' F = F ′ , so A A A determines F F F and then D = A ∖ F D=A\setminus F D = A ∖ F . We also have r ( A ) = ∣ F ∣ r(A)=|F| r ( A ) = ∣ F ∣ .
Using this decomposition in the expansion of t ( H , 1 − U ) t(H,1-U) t ( H , 1 − U ) , we obtain
t ( H , 1 − U ) = ∑ F f o r e s t ∑ D ⊆ B ( F ) ( − 1 ) ∣ F ∣ + ∣ D ∣ ∫ ∏ u v ∈ F ∪ ˙ D U ( x u , x v ) ∏ v ∈ V ( H ) d x v = ∑ F f o r e s t ( − 1 ) ∣ F ∣ ∫ ∏ u v ∈ F U ( x u , x v ) ∏ u v ∈ B ( F ) ( 1 − U ( x u , x v ) ) ∏ v ∈ V ( H ) d x v = ∑ F f o r e s t ( − 1 ) ∣ F ∣ I F ( U ) . \begin{aligned}
t(H,1-U)
&=\sum_{F\ \mathrm{forest}}\sum_{D\subseteq B(F)}(-1)^{|F|+|D|}
\int\prod_{uv\in F\mathbin{\dot\cup}D}U(x_u,x_v)\prod_{v\in V(H)}dx_v\\
&=\sum_{F\ \mathrm{forest}}(-1)^{|F|}
\int\prod_{uv\in F}U(x_u,x_v)\prod_{uv\in B(F)}(1-U(x_u,x_v))\prod_{v\in V(H)}dx_v\\
&=\sum_{F\ \mathrm{forest}}(-1)^{|F|}I_F(U).
\end{aligned} t ( H , 1 − U ) = F forest ∑ D ⊆ B ( F ) ∑ ( − 1 ) ∣ F ∣ + ∣ D ∣ ∫ uv ∈ F ∪ ˙ D ∏ U ( x u , x v ) v ∈ V ( H ) ∏ d x v = F forest ∑ ( − 1 ) ∣ F ∣ ∫ uv ∈ F ∏ U ( x u , x v ) uv ∈ B ( F ) ∏ ( 1 − U ( x u , x v )) v ∈ V ( H ) ∏ d x v = F forest ∑ ( − 1 ) ∣ F ∣ I F ( U ) .
For each forest F F F , the corresponding terms in (4.2) sum to
( − 1 ) ∣ F ∣ q ∣ F ∣ ∑ D ⊆ B ( F ) ( − 1 ) ∣ D ∣ = { ( − 1 ) ∣ F ∣ q ∣ F ∣ , B ( F ) = ∅ , 0 , B ( F ) ≠ ∅ . (-1)^{|F|}q^{|F|}\sum_{D\subseteq B(F)}(-1)^{|D|}
=
\begin{cases}
(-1)^{|F|}q^{|F|},&B(F)=\varnothing,\\
0,&B(F)\ne\varnothing.
\end{cases} ( − 1 ) ∣ F ∣ q ∣ F ∣ D ⊆ B ( F ) ∑ ( − 1 ) ∣ D ∣ = { ( − 1 ) ∣ F ∣ q ∣ F ∣ , 0 , B ( F ) = ∅ , B ( F ) = ∅ .
Summing over F F F proves (4.4). ▫
Since I F ( U ) = t ( F , U ) I_F(U)=t(F,U) I F ( U ) = t ( F , U ) when B ( F ) = ∅ B(F)=\varnothing B ( F ) = ∅ , subtracting the two identities gives
t ( H , 1 − U ) − Φ H ( 1 − q ) = ∑ F forest B ( F ) = ∅ ( − 1 ) ∣ F ∣ ( t ( F , U ) − q ∣ F ∣ ) + ∑ F forest B ( F ) ≠ ∅ ( − 1 ) ∣ F ∣ I F ( U ) . (22) t(H,1-U)-\Phi_H(1-q)=\sum_{\substack{F\text{ forest}\\B(F)=\varnothing}}(-1)^{|F|}\left(t(F,U)-q^{|F|}\right)
+\sum_{\substack{F\text{ forest}\\B(F)\ne\varnothing}}(-1)^{|F|}I_F(U). \tag*{(22)} t ( H , 1 − U ) − Φ H ( 1 − q ) = F forest B ( F ) = ∅ ∑ ( − 1 ) ∣ F ∣ ( t ( F , U ) − q ∣ F ∣ ) + F forest B ( F ) = ∅ ∑ ( − 1 ) ∣ F ∣ I F ( U ) . (22)
Tree and forest densities
The lower bound below is the tree case of Sidorenko’s inequality [15 ] ; the upper bound is his comparison with the star having the same number of edges [16 ] .
Lemma 4.3. If T T T is a tree with r ≥ 1 r\ge1 r ≥ 1 edges, then
q r ≤ t ( T , U ) ≤ M r ( U ) . (23) q^r\le t(T,U)\le M_r(U). \tag*{(23)} q r ≤ t ( T , U ) ≤ M r ( U ) . (23)
Sidorenko’s inequality for trees holds with equality whenever U U U is regular, that is, d U ( x ) = q d_U(x)=q d U ( x ) = q almost everywhere. The following lemma bounds the gap t ( F , U ) − q e ( F ) t(F,U)-q^{e(F)} t ( F , U ) − q e ( F ) for forests F F F in terms of the variance of the degree function.
Lemma 4.4. If F F F is a forest with r ≥ 2 r\ge2 r ≥ 2 edges, then
0 ≤ t ( F , U ) − q r ≤ ( r 2 ) Δ U r − 2 Var ( d U ) . (24) 0\le t(F,U)-q^r\le\binom{r}{2}\Delta_U^{r-2}\operatorname{Var}(d_U). \tag*{(24)} 0 ≤ t ( F , U ) − q r ≤ ( 2 r ) Δ U r − 2 Var ( d U ) . (24)
In particular, taking F F F to be the star K 1 , r K_{1,r} K 1 , r gives
0 ≤ M r ( U ) − q r ≤ ( r 2 ) Δ U r − 2 Var ( d U ) . (25) 0\le M_r(U)-q^r\le\binom{r}{2}\Delta_U^{r-2}\operatorname{Var}(d_U). \tag*{(25)} 0 ≤ M r ( U ) − q r ≤ ( 2 r ) Δ U r − 2 Var ( d U ) . (25)
Proof. Assume Δ U > 0 \Delta_U>0 Δ U > 0 , since the case Δ U = 0 \Delta_U=0 Δ U = 0 is immediate. Let T 1 , … , T ℓ T_1,\ldots,T_\ell T 1 , … , T ℓ be the components of F F F containing an edge, and write r i = e ( T i ) r_i=e(T_i) r i = e ( T i ) , so that ∑ i r i = r \sum_i r_i=r ∑ i r i = r . By Lemma 4.3 and Hölder’s inequality,
q r = ∏ i = 1 ℓ q r i ≤ t ( F , U ) = ∏ i = 1 ℓ t ( T i , U ) ≤ ∏ i = 1 ℓ M r i ( U ) ≤ ∏ i = 1 ℓ M r ( U ) r i / r = M r ( U ) . \begin{aligned}
q^r=\prod_{i=1}^{\ell}q^{r_i}\le t(F,U)=\prod_{i=1}^{\ell}t(T_i,U) \\
&\le\prod_{i=1}^{\ell}M_{r_i}(U)\le\prod_{i=1}^{\ell}M_r(U)^{r_i/r}=M_r(U).
\end{aligned} q r = i = 1 ∏ ℓ q r i ≤ t ( F , U ) = i = 1 ∏ ℓ t ( T i , U ) ≤ i = 1 ∏ ℓ M r i ( U ) ≤ i = 1 ∏ ℓ M r ( U ) r i / r = M r ( U ) .
On [ 0 , Δ U ] [0,\Delta_U] [ 0 , Δ U ] , the function s ↦ s r s\mapsto s^r s ↦ s r has second derivative at most r ( r − 1 ) Δ U r − 2 r(r-1)\Delta_U^{r-2} r ( r − 1 ) Δ U r − 2 . Since q , d U ( x ) ∈ [ 0 , Δ U ] q,d_U(x)\in[0,\Delta_U] q , d U ( x ) ∈ [ 0 , Δ U ] for almost every x x x , Taylor’s theorem at s = q s=q s = q gives
d U ( x ) r ≤ q r + r q r − 1 ( d U ( x ) − q ) + ( r 2 ) Δ U r − 2 ( d U ( x ) − q ) 2 . d_U(x)^r\le q^r+rq^{r-1}(d_U(x)-q)+\binom{r}{2}\Delta_U^{r-2}(d_U(x)-q)^2. d U ( x ) r ≤ q r + r q r − 1 ( d U ( x ) − q ) + ( 2 r ) Δ U r − 2 ( d U ( x ) − q ) 2 .
Integrating and using ∫ ( d U ( x ) − q ) d x = 0 \int(d_U(x)-q)\,dx=0 ∫ ( d U ( x ) − q ) d x = 0 , we obtain
0 ≤ t ( F , U ) − q r ≤ M r ( U ) − q r ≤ ( r 2 ) Δ U r − 2 Var ( d U ) . 0\le t(F,U)-q^r\le M_r(U)-q^r\le\binom{r}{2}\Delta_U^{r-2}\operatorname{Var}(d_U). 0 ≤ t ( F , U ) − q r ≤ M r ( U ) − q r ≤ ( 2 r ) Δ U r − 2 Var ( d U ) .
The star case follows from t ( K 1 , r , U ) = M r ( U ) t(K_{1,r},U)=M_r(U) t ( K 1 , r , U ) = M r ( U ) . ▫
Path and cycle densities
We bound the difference between the densities of a path and the cycle obtained by joining its endpoints.
Lemma 4.5. Let F F F be a forest with r r r edges, and let u , v ∈ V ( F ) u,v \in V(F) u , v ∈ V ( F ) have distance s − 1 ≥ 2 s-1 \ge2 s − 1 ≥ 2 . Then
0 ≤ ∫ ( ∏ a b ∈ E ( F ) U ( x a , x b ) ) ( 1 − U ( x u , x v ) ) ∏ w ∈ V ( F ) d x w ≤ Δ U r − s + 1 ( t ( P s , U ) − t ( C s , U ) ) . (26) 0 \le\int\left(\prod_{ab\in E(F)} U(x_a,x_b)\right)(1-U(x_u,x_v))\prod_{w\in V(F)}\mathrm{d}x_w
\le\Delta_U^{r-s+1}(t(P_s,U)-t(C_s,U)). \tag*{(26)} 0 ≤ ∫ ab ∈ E ( F ) ∏ U ( x a , x b ) ( 1 − U ( x u , x v )) w ∈ V ( F ) ∏ d x w ≤ Δ U r − s + 1 ( t ( P s , U ) − t ( C s , U )) . (26)
Proof. Write the u u u –v v v path as u = v 1 , … , v s = v u=v_1,\ldots,v_s=v u = v 1 , … , v s = v . If a a a is a leaf outside this path with neighbour b b b , then x a x_a x a occurs only in the factor U ( x a , x b ) U(x_a,x_b) U ( x a , x b ) . Hence
∫ ( ∏ c d ∈ E ( F ) U ( x c , x d ) ) ( 1 − U ( x u , x v ) ) d x a = d U ( x b ) ( ∏ c d ∈ E ( F ) ∖ { a b } U ( x c , x d ) ) ( 1 − U ( x u , x v ) ) ≤ Δ U ( ∏ c d ∈ E ( F ) ∖ { a b } U ( x c , x d ) ) ( 1 − U ( x u , x v ) ) . \int\left(\prod_{cd\in E(F)}U(x_c,x_d)\right)(1-U(x_u,x_v))\mathrm{d}x_a
=\mathrm{d}_U(x_b)\left(\prod_{cd\in E(F)\setminus\{ab\}}U(x_c,x_d)\right)(1-U(x_u,x_v))
\le\Delta_U\left(\prod_{cd\in E(F)\setminus\{ab\}}U(x_c,x_d)\right)(1-U(x_u,x_v)). ∫ c d ∈ E ( F ) ∏ U ( x c , x d ) ( 1 − U ( x u , x v )) d x a = d U ( x b ) c d ∈ E ( F ) ∖ { ab } ∏ U ( x c , x d ) ( 1 − U ( x u , x v )) ≤ Δ U c d ∈ E ( F ) ∖ { ab } ∏ U ( x c , x d ) ( 1 − U ( x u , x v )) .
Repeating this for the r − s + 1 r-s+1 r − s + 1 edges outside the path and integrating isolated vertices, which contribute 1 1 1 , gives
0 ≤ ∫ ( ∏ a b ∈ E ( F ) U ( x a , x b ) ) ( 1 − U ( x u , x v ) ) ∏ w ∈ V ( F ) d x w ≤ Δ U r − s + 1 ∫ ( ∏ i = 1 s − 1 U ( x v i , x v i + 1 ) ) ( 1 − U ( x u , x v ) ) ∏ i = 1 s d x v i = Δ U r − s + 1 ( t ( P s , U ) − t ( C s , U ) ) . 0\le\int\left(\prod_{ab\in E(F)}U(x_a,x_b)\right)(1-U(x_u,x_v))\prod_{w\in V(F)}\mathrm{d}x_w
\le\Delta_U^{r-s+1}\int\left(\prod_{i=1}^{s-1}U(x_{v_i},x_{v_{i+1}})\right)(1-U(x_u,x_v))\prod_{i=1}^{s}\mathrm{d}x_{v_i}
=\Delta_U^{r-s+1}(t(P_s,U)-t(C_s,U)). 0 ≤ ∫ ab ∈ E ( F ) ∏ U ( x a , x b ) ( 1 − U ( x u , x v )) w ∈ V ( F ) ∏ d x w ≤ Δ U r − s + 1 ∫ ( i = 1 ∏ s − 1 U ( x v i , x v i + 1 ) ) ( 1 − U ( x u , x v )) i = 1 ∏ s d x v i = Δ U r − s + 1 ( t ( P s , U ) − t ( C s , U )) .
For every s ≥ 3 s\ge3 s ≥ 3 ,
t ( P s , U ) − t ( C s , U ) = ∫ ( ∏ i = 1 s − 1 U ( x i , x i + 1 ) ) ( 1 − U ( x 1 , x s ) ) ∏ i = 1 s d x i . t(P_s,U)-t(C_s,U)=\int\left(\prod_{i=1}^{s-1}U(x_i,x_{i+1})\right)(1-U(x_1,x_s))\prod_{i=1}^{s}\mathrm{d}x_i. t ( P s , U ) − t ( C s , U ) = ∫ ( i = 1 ∏ s − 1 U ( x i , x i + 1 ) ) ( 1 − U ( x 1 , x s )) i = 1 ∏ s d x i .
For s = 3 s=3 s = 3 ,
M 2 ( U ) − t ( C 3 , U ) = t ( P 3 , U ) − t ( C 3 , U ) = ∫ U ( x , y ) U ( y , z ) ( 1 − U ( x , z ) ) d x d y d z . (27) M_2(U)-t(C_3,U)=t(P_3,U)-t(C_3,U)
=\int U(x,y)U(y,z)(1-U(x,z))\mathrm{d}x\,\mathrm{d}y\,\mathrm{d}z. \tag*{(27)} M 2 ( U ) − t ( C 3 , U ) = t ( P 3 , U ) − t ( C 3 , U ) = ∫ U ( x , y ) U ( y , z ) ( 1 − U ( x , z )) d x d y d z . (27)
Lemma 4.6. For every integer s ≥ 3 s\ge3 s ≥ 3 ,
0 ≤ t ( P s , U ) − t ( C s , U ) ≤ ( s − 2 ) Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U ) ) . (28) 0\le t(P_s,U)-t(C_s,U)\le(s-2)\Delta_U^{s-3}(M_2(U)-t(C_3,U)). \tag*{(28)} 0 ≤ t ( P s , U ) − t ( C s , U ) ≤ ( s − 2 ) Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U )) . (28)
Proof. For s = 3 s=3 s = 3 , the claim is immediate by (4.11). Define the iterated kernels recursively by
U ∘ 1 ( x , y ) = U ( x , y ) , U ∘ ( ℓ + 1 ) ( x , y ) = ∫ U ∘ ℓ ( x , z ) U ( z , y ) d z . (29) U^{\circ1}(x,y)=U(x,y),\qquad U^{\circ(\ell+1)}(x,y)=\int U^{\circ\ell}(x,z)U(z,y)\,\mathrm{d}z. \tag*{(29)} U ∘ 1 ( x , y ) = U ( x , y ) , U ∘ ( ℓ + 1 ) ( x , y ) = ∫ U ∘ ℓ ( x , z ) U ( z , y ) d z . (29)
Induction gives
0 ≤ U ∘ ℓ ( x , y ) ≤ Δ U ℓ − 1 0 \le U^{\circ\ell}(x,y) \le\Delta_U^{\ell-1} 0 ≤ U ∘ ℓ ( x , y ) ≤ Δ U ℓ − 1
for almost every ( x , y ) (x,y) ( x , y ) , (4.13)
since U ≤ 1 U \le1 U ≤ 1 and
U ∘ ( ℓ + 1 ) ( x , y ) ≤ Δ U ℓ − 1 ∫ U ( z , y ) d z = Δ U ℓ − 1 d U ( y ) ≤ Δ U ℓ . U^{\circ(\ell+1)}(x,y) \le\Delta_U^{\ell-1} \int U(z,y)\,dz = \Delta_U^{\ell-1}d_U(y) \le\Delta_U^\ell. U ∘ ( ℓ + 1 ) ( x , y ) ≤ Δ U ℓ − 1 ∫ U ( z , y ) d z = Δ U ℓ − 1 d U ( y ) ≤ Δ U ℓ .
We obtain
t ( P s , U ) − t ( C s , U ) = ∫ ( ∏ i = 1 s − 1 U ( x i , x i + 1 ) ) ( 1 − U ( x 1 , x s ) ) ∏ i = 1 s d x i ≤ ∫ ( ∏ i = 1 s − 1 U ( x i , x i + 1 ) ) ( 1 − U ( x 1 , x s − 1 ) ) ∏ i = 1 s d x i + ∫ ( ∏ i = 1 s − 1 U ( x i , x i + 1 ) ) U ( x 1 , x s − 1 ) ( 1 − U ( x 1 , x s ) ) ∏ i = 1 s d x i = ∫ ( ∏ i = 1 s − 2 U ( x i , x i + 1 ) ) d U ( x s − 1 ) ( 1 − U ( x 1 , x s − 1 ) ) ∏ i = 1 s − 1 d x i + ∫ U ∘ ( s − 2 ) ( x , y ) U ( x , y ) U ( y , z ) ( 1 − U ( x , z ) ) d x d y d z ≤ Δ U ( t ( P s − 1 , U ) − t ( C s − 1 , U ) ) + Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U ) ) . \begin{aligned}
t(P_s,U)-t(C_s,U)
&= \int\left(\prod_{i=1}^{s-1} U(x_i,x_{i+1})\right)(1-U(x_1,x_s))\prod_{i=1}^{s}dx_i\\
&\le\int\left(\prod_{i=1}^{s-1} U(x_i,x_{i+1})\right)(1-U(x_1,x_{s-1}))\prod_{i=1}^{s}dx_i\\
&\quad+\int\left(\prod_{i=1}^{s-1} U(x_i,x_{i+1})\right)U(x_1,x_{s-1})(1-U(x_1,x_s))\prod_{i=1}^{s}dx_i\\
&= \int\left(\prod_{i=1}^{s-2} U(x_i,x_{i+1})\right)d_U(x_{s-1})(1-U(x_1,x_{s-1}))\prod_{i=1}^{s-1}dx_i\\
&\quad+\int U^{\circ(s-2)}(x,y)U(x,y)U(y,z)(1-U(x,z))\,dx\,dy\,dz\\
&\le\Delta_U\bigl(t(P_{s-1},U)-t(C_{s-1},U)\bigr)+\Delta_U^{s-3}\bigl(M_2(U)-t(C_3,U)\bigr).
\end{aligned} t ( P s , U ) − t ( C s , U ) = ∫ ( i = 1 ∏ s − 1 U ( x i , x i + 1 ) ) ( 1 − U ( x 1 , x s )) i = 1 ∏ s d x i ≤ ∫ ( i = 1 ∏ s − 1 U ( x i , x i + 1 ) ) ( 1 − U ( x 1 , x s − 1 )) i = 1 ∏ s d x i + ∫ ( i = 1 ∏ s − 1 U ( x i , x i + 1 ) ) U ( x 1 , x s − 1 ) ( 1 − U ( x 1 , x s )) i = 1 ∏ s d x i = ∫ ( i = 1 ∏ s − 2 U ( x i , x i + 1 ) ) d U ( x s − 1 ) ( 1 − U ( x 1 , x s − 1 )) i = 1 ∏ s − 1 d x i + ∫ U ∘ ( s − 2 ) ( x , y ) U ( x , y ) U ( y , z ) ( 1 − U ( x , z )) d x d y d z ≤ Δ U ( t ( P s − 1 , U ) − t ( C s − 1 , U ) ) + Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U ) ) .
where the first inequality follows from
1 − U ( x 1 , x s ) ≤ 1 − U ( x 1 , x s − 1 ) + U ( x 1 , x s − 1 ) ( 1 − U ( x 1 , x s ) ) . 1-U(x_1,x_s)\le1-U(x_1,x_{s-1})+U(x_1,x_{s-1})(1-U(x_1,x_s)). 1 − U ( x 1 , x s ) ≤ 1 − U ( x 1 , x s − 1 ) + U ( x 1 , x s − 1 ) ( 1 − U ( x 1 , x s )) .
and the last follows from d U ≤ Δ U d_U\le\Delta_U d U ≤ Δ U , (4.13), and (4.11). In the second equality, we integrate x s x_s x s in the first term and x 2 , … , x s − 2 x_2,\ldots,x_{s-2} x 2 , … , x s − 2 in the second. Induction on s s s proves (4.12).
Comparison of cycle densities
For odd g ≥ 5 g\ge5 g ≥ 5 , the following comparison provides the estimate needed for cycles of length at least g g g .
Theorem 4.7. Let g ≥ 5 g\ge5 g ≥ 5 be odd and let s ≥ g s\ge g s ≥ g be an integer. For every graphon U U U ,
0 ≤ M s − 1 ( U ) − t ( C s , U ) 0\le M_{s-1}(U)-t(C_s,U) 0 ≤ M s − 1 ( U ) − t ( C s , U ) ≤ ( s − 2 ) ( s − 3 ) ( g − 2 ) ( g − 3 ) Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) . (30) \le\frac{(s-2)(s-3)}{(g-2)(g-3)}\Delta_U^{s-g}\bigl(M_{g-1}(U)-t(C_g,U)\bigr). \tag*{(30)} ≤ ( g − 2 ) ( g − 3 ) ( s − 2 ) ( s − 3 ) Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) . (30)
Lemma 4.8. Let 2 ≤ a ≤ b 2\le a\le b 2 ≤ a ≤ b be integers and let Δ > 0 \Delta>0 Δ > 0 . If a random variable Z Z Z takes values in [ 0 , Δ ] [0,\Delta] [ 0 , Δ ] and 0 ≤ α ≤ E Z 0\le\alpha\le\mathbb{E}Z 0 ≤ α ≤ E Z , then
E Z b − α b ≤ b ( b − 1 ) a ( a − 1 ) Δ b − a ( E Z a − α a ) . (31) \mathbb{E}Z^b-\alpha^b\le\frac{b(b-1)}{a(a-1)}\Delta^{b-a}(\mathbb{E}Z^a-\alpha^a). \tag*{(31)} E Z b − α b ≤ a ( a − 1 ) b ( b − 1 ) Δ b − a ( E Z a − α a ) . (31)
Proof. Equality holds when a = b a=b a = b . For b > a b>a b > a , consider the polynomial
z b − b ( b − 1 ) a ( a − 1 ) Δ b − a z a . z^b-\frac{b(b-1)}{a(a-1)}\Delta^{b-a}z^a. z b − a ( a − 1 ) b ( b − 1 ) Δ b − a z a .
Its first and second derivatives on [ 0 , Δ ] [0,\Delta] [ 0 , Δ ] are, respectively,
b z a − 1 ( z b − a − b − 1 a − 1 Δ b − a ) ≤ 0 , b ( b − 1 ) z a − 2 ( z b − a − Δ b − a ) ≤ 0. bz^{a-1}\left(z^{b-a}-\frac{b-1}{a-1}\Delta^{b-a}\right)\le0,
\qquad
b(b-1)z^{a-2}\left(z^{b-a}-\Delta^{b-a}\right)\le0. b z a − 1 ( z b − a − a − 1 b − 1 Δ b − a ) ≤ 0 , b ( b − 1 ) z a − 2 ( z b − a − Δ b − a ) ≤ 0.
The polynomial is therefore nonincreasing and concave. Jensen’s inequality and α ≤ E Z \alpha\le\mathbb{E}Z α ≤ E Z give
E Z b − b ( b − 1 ) a ( a − 1 ) Δ b − a E Z a ≤ ( E Z ) b − b ( b − 1 ) a ( a − 1 ) Δ b − a ( E Z ) a ≤ α b − b ( b − 1 ) a ( a − 1 ) Δ b − a α a . \mathbb{E}Z^b-\frac{b(b-1)}{a(a-1)}\Delta^{b-a}\mathbb{E}Z^a
\le(\mathbb{E}Z)^b-\frac{b(b-1)}{a(a-1)}\Delta^{b-a}(\mathbb{E}Z)^a
\le\alpha^b-\frac{b(b-1)}{a(a-1)}\Delta^{b-a}\alpha^a. E Z b − a ( a − 1 ) b ( b − 1 ) Δ b − a E Z a ≤ ( E Z ) b − a ( a − 1 ) b ( b − 1 ) Δ b − a ( E Z ) a ≤ α b − a ( a − 1 ) b ( b − 1 ) Δ b − a α a .
Rearranging proves the claim.
We next state the spectral identities for the integral operator T U T_U T U ; see Lovász [9, Chapter 7].
Lemma 4.9. Let ( T U f ) ( x ) = ∫ U ( x , y ) f ( y ) d y (T_Uf)(x)=\int U(x,y)f(y)\,dy ( T U f ) ( x ) = ∫ U ( x , y ) f ( y ) d y on real L 2 [ 0 , 1 ] L^2[0,1] L 2 [ 0 , 1 ] . Choose real orthonormal eigenfunctions f i f_i f i corresponding to all nonzero eigenvalues λ i \lambda_i λ i of T U T_U T U , counted with multiplicity. Then
∣ λ i ∣ ≤ ∫ d U ( x ) f i ( x ) 2 d x ≤ Δ U , ∑ i λ i 2 = ∫ U ( x , y ) 2 d x d y . (32) |\lambda_i|\le\int d_U(x)f_i(x)^2\,dx\le\Delta_U,
\qquad
\sum_i\lambda_i^2=\int U(x,y)^2\,dx\,dy. \tag*{(32)} ∣ λ i ∣ ≤ ∫ d U ( x ) f i ( x ) 2 d x ≤ Δ U , i ∑ λ i 2 = ∫ U ( x , y ) 2 d x d y . (32) For every integer s ≥ 3 s\ge3 s ≥ 3 and every integer j ≥ 1 j\ge1 j ≥ 1 ,
t ( C s , U ) = ∑ i λ i s , (33) t(C_s,U)=\sum_i\lambda_i^s, \tag*{(33)} t ( C s , U ) = i ∑ λ i s , (33) ∑ i λ i 2 ∫ d U ( x ) j f i ( x ) 2 d x = ∫ d U ( x ) j U ( x , y ) 2 d x d y . (34) \sum_i\lambda_i^2\int d_U(x)^j f_i(x)^2\,dx
=\int d_U(x)^j U(x,y)^2\,dx\,dy. \tag*{(34)} i ∑ λ i 2 ∫ d U ( x ) j f i ( x ) 2 d x = ∫ d U ( x ) j U ( x , y ) 2 d x d y . (34) All these series converge absolutely.
Proof. The operator T U T_U T U is compact, self-adjoint, and Hilbert–Schmidt. The spectral theorem gives the eigenfunctions f i f_i f i ; adjoining an orthonormal basis of ker T U \ker T_U ker T U gives a complete eigenbasis. For every real f ∈ L 2 [ 0 , 1 ] f\in L^2[0,1] f ∈ L 2 [ 0 , 1 ] , symmetry gives
∫ d U ( x ) f ( x ) 2 d x ± ⟨ f , T U f ⟩ = 1 2 ∫ U ( x , y ) ( f ( x ) ± f ( y ) ) 2 d x d y ≥ 0. (35) \int d_U(x)f(x)^2\,dx\pm\langle f,T_Uf\rangle
=\frac{1}{2}\int U(x,y)(f(x)\pm f(y))^2\,dx\,dy\ge0. \tag*{(35)} ∫ d U ( x ) f ( x ) 2 d x ± ⟨ f , T U f ⟩ = 2 1 ∫ U ( x , y ) ( f ( x ) ± f ( y ) ) 2 d x d y ≥ 0. (35)
Taking f = f i f=f_i f = f i proves the eigenvalue bound. The formula for ∑ i λ i 2 \sum_i\lambda_i^2 ∑ i λ i 2 is the Hilbert–Schmidt norm identity.
For s ≥ 3 s\ge3 s ≥ 3 , the operators T U T_U T U and T U s − 1 T_U^{s-1} T U s − 1 are both Hilbert–Schmidt, and U ∘ ( s − 1 ) U^{\circ(s-1)} U ∘ ( s − 1 ) is the kernel of T U s − 1 T_U^{s-1} T U s − 1 . Computing their inner product from the kernels and the eigenbasis gives
t ( C s , U ) = ∫ U ( x , y ) U ∘ ( s − 1 ) ( x , y ) d x d y = ⟨ T U , T U s − 1 ⟩ H S = ∑ i λ i s . t(C_s,U)=\int U(x,y)U^{\circ(s-1)}(x,y)\,dx\,dy
=\langle T_U,T_U^{s-1}\rangle_{\mathrm{HS}}
=\sum_i\lambda_i^s. t ( C s , U ) = ∫ U ( x , y ) U ∘ ( s − 1 ) ( x , y ) d x d y = ⟨ T U , T U s − 1 ⟩ HS = i ∑ λ i s .
For almost every x x x , Parseval’s identity also gives
∫ U ( x , y ) 2 d y = ∑ i ( ∫ U ( x , y ) f i ( y ) d y ) 2 = ∑ i λ i 2 f i ( x ) 2 . \int U(x,y)^2\,dy
=\sum_i\left(\int U(x,y)f_i(y)\,dy\right)^2
=\sum_i\lambda_i^2f_i(x)^2. ∫ U ( x , y ) 2 d y = i ∑ ( ∫ U ( x , y ) f i ( y ) d y ) 2 = i ∑ λ i 2 f i ( x ) 2 .
Multiplying by d U ( x ) j d_U(x)^j d U ( x ) j and integrating proves (4.18) by Tonelli’s theorem. Absolute convergence follows from ∣ λ i ∣ ≤ Δ U ≤ 1 |\lambda_i|\le\Delta_U\le1 ∣ λ i ∣ ≤ Δ U ≤ 1 and ∑ i λ i 2 < ∞ \sum_i\lambda_i^2<\infty ∑ i λ i 2 < ∞ .
Lemma 4.10. With the eigenfunctions and eigenvalues above, for every integer s ≥ 3 s \ge3 s ≥ 3 ,
M s − 1 ( U ) − t ( C s , U ) = ∫ d U ( x ) s − 2 U ( x , y ) ( 1 − U ( x , y ) ) d x d y + ∑ i λ i 2 ( ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ) . (36) M_{s-1}(U)-t(C_s,U)=\int d_U(x)^{s-2}U(x,y)(1-U(x,y))\,dx\,dy+\sum_i\lambda_i^2\left(\int d_U(x)^{s-2}f_i(x)^2\,dx-\lambda_i^{s-2}\right). \tag*{(36)} M s − 1 ( U ) − t ( C s , U ) = ∫ d U ( x ) s − 2 U ( x , y ) ( 1 − U ( x , y )) d x d y + i ∑ λ i 2 ( ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ) . (36) The integral and each summand are nonnegative, and the series converges absolutely.
Proof. By (34) ,
M s − 1 ( U ) = ∫ d U ( x ) s − 2 U ( x , y ) d x d y = ∫ d U ( x ) s − 2 U ( x , y ) ( 1 − U ( x , y ) ) d x d y + ∑ i λ i 2 ∫ d U ( x ) s − 2 f i ( x ) 2 d x . \begin{aligned}
M_{s-1}(U)=\int d_U(x)^{s-2}U(x,y)\,dx\,dy \\
&=\int d_U(x)^{s-2}U(x,y)(1-U(x,y))\,dx\,dy+\sum_i\lambda_i^2\int d_U(x)^{s-2}f_i(x)^2\,dx.
\end{aligned} M s − 1 ( U ) = ∫ d U ( x ) s − 2 U ( x , y ) d x d y = ∫ d U ( x ) s − 2 U ( x , y ) ( 1 − U ( x , y )) d x d y + i ∑ λ i 2 ∫ d U ( x ) s − 2 f i ( x ) 2 d x .
Subtracting (33) gives the decomposition. Since ∫ f i ( x ) 2 d x = 1 \int f_i(x)^2\,dx=1 ∫ f i ( x ) 2 d x = 1 , Jensen’s inequality and (32) give, for j ≥ 1 j\ge1 j ≥ 1 ,
∫ d U ( x ) j f i ( x ) 2 d x ≥ ( ∫ d U ( x ) f i ( x ) 2 d x ) j ≥ ∣ λ i ∣ j ≥ λ i j . \int d_U(x)^j f_i(x)^2\,dx\ge\left(\int d_U(x)f_i(x)^2\,dx\right)^j\ge|\lambda_i|^j\ge\lambda_i^j. ∫ d U ( x ) j f i ( x ) 2 d x ≥ ( ∫ d U ( x ) f i ( x ) 2 d x ) j ≥ ∣ λ i ∣ j ≥ λ i j .
Thus the integral and each summand are nonnegative. For absolute convergence, we have
∑ i λ i 2 ∣ ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ∣ ≤ ∑ i λ i 2 ( ∫ d U ( x ) s − 2 f i ( x ) 2 d x + ∣ λ i ∣ s − 2 ) \begin{aligned}
\sum_i\lambda_i^2\left|\int d_U(x)^{s-2}f_i(x)^2\,dx-\lambda_i^{s-2}\right| \\
&\le\sum_i\lambda_i^2\left(\int d_U(x)^{s-2}f_i(x)^2\,dx+|\lambda_i|^{s-2}\right)
\end{aligned} i ∑ λ i 2 ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ≤ i ∑ λ i 2 ( ∫ d U ( x ) s − 2 f i ( x ) 2 d x + ∣ λ i ∣ s − 2 )
≤ 2 Δ U s − 2 ∑ i λ i 2 = 2 Δ U s − 2 ∫ U ( x , y ) 2 d x d y < ∞ , \le2\Delta_U^{s-2}\sum_i\lambda_i^2=2\Delta_U^{s-2}\int U(x,y)^2\,dx\,dy<\infty, ≤ 2 Δ U s − 2 i ∑ λ i 2 = 2 Δ U s − 2 ∫ U ( x , y ) 2 d x d y < ∞ ,
where we used ∫ f i ( x ) 2 d x = 1 \int f_i(x)^2\,dx=1 ∫ f i ( x ) 2 d x = 1 , d U ≤ Δ U d_U\le\Delta_U d U ≤ Δ U , and (32) . □
Proof of Theorem 4.7. If Δ U = 0 \Delta_U=0 Δ U = 0 , then U U U is regular of degree zero, so U = 0 U=0 U = 0 almost everywhere and both sides of (30) are zero. We may therefore assume Δ U > 0 \Delta_U>0 Δ U > 0 .
Fix i i i with λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 . Since ∫ f i ( x ) 2 d x = 1 \int f_i(x)^2\,dx=1 ∫ f i ( x ) 2 d x = 1 , let X X X have probability density f i ( x ) 2 f_i(x)^2 f i ( x ) 2 on [ 0 , 1 ] [0,1] [ 0 , 1 ] , and set Z = d U ( X ) Z=d_U(X) Z = d U ( X ) . Then 0 ≤ Z ≤ Δ U 0\le Z\le\Delta_U 0 ≤ Z ≤ Δ U almost surely, and
E Z j = ∫ d U ( x ) j f i ( x ) 2 d x ( j ≥ 1 ) . \mathbb{E}Z^j=\int d_U(x)^j f_i(x)^2\,dx\qquad(j\ge1). E Z j = ∫ d U ( x ) j f i ( x ) 2 d x ( j ≥ 1 ) .
Moreover, (32) gives
0 ≤ λ i ≤ ∫ d U ( x ) f i ( x ) 2 d x = E Z . 0\le\lambda_i\le\int d_U(x)f_i(x)^2\,dx=\mathbb{E}Z. 0 ≤ λ i ≤ ∫ d U ( x ) f i ( x ) 2 d x = E Z .
Since 2 ≤ g − 2 ≤ s − 2 2\le g-2\le s-2 2 ≤ g − 2 ≤ s − 2 , we can apply Lemma 4.8 with
a = g − 2 , b = s − 2 , α = λ i , Δ = Δ U . a=g-2,\qquad b=s-2,\qquad\alpha=\lambda_i,\qquad\Delta=\Delta_U. a = g − 2 , b = s − 2 , α = λ i , Δ = Δ U .
This gives
∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ≤ ( s − 2 ) ( s − 3 ) ( g − 2 ) ( g − 3 ) Δ U s − g ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) . (37) \int d_U(x)^{s-2}f_i(x)^2\,dx-\lambda_i^{s-2}
\le\frac{(s-2)(s-3)}{(g-2)(g-3)}\Delta_U^{s-g}\left(\int d_U(x)^{g-2}f_i(x)^2\,dx-\lambda_i^{g-2}\right). \tag*{(37)} ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ≤ ( g − 2 ) ( g − 3 ) ( s − 2 ) ( s − 3 ) Δ U s − g ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) . (37)
For λ i < 0 \lambda_i<0 λ i < 0 , use that g − 2 g-2 g − 2 is odd to obtain
∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ≤ ∫ d U ( x ) s − 2 f i ( x ) 2 d x + ∣ λ i ∣ s − 2 ≤ Δ U s − g ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x + ∣ λ i ∣ g − 2 ) = Δ U s − g ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) . (38) \begin{aligned}
\int d_U(x)^{s-2}f_i(x)^2\,\mathrm{d}x-\lambda_i^{s-2}
&\le\int d_U(x)^{s-2}f_i(x)^2\,\mathrm{d}x+|\lambda_i|^{s-2}\\
&\le\Delta_U^{s-g}\left(\int d_U(x)^{g-2}f_i(x)^2\,\mathrm{d}x+|\lambda_i|^{g-2}\right)\\
&=\Delta_U^{s-g}\left(\int d_U(x)^{g-2}f_i(x)^2\,\mathrm{d}x-\lambda_i^{g-2}\right). \tag*{(38)}
\end{aligned} ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ≤ ∫ d U ( x ) s − 2 f i ( x ) 2 d x + ∣ λ i ∣ s − 2 ≤ Δ U s − g ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x + ∣ λ i ∣ g − 2 ) = Δ U s − g ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) . (38)
By (4.20),
M s − 1 ( U ) − t ( C s , U ) = ∫ d U ( x ) s − 2 U ( x , y ) ( 1 − U ( x , y ) ) d x d y + ∑ i λ i 2 ( ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ) ≤ Δ U s − g ∫ d U ( x ) g − 2 U ( x , y ) ( 1 − U ( x , y ) ) d x d y + ( s − 2 ) ( s − 3 ) ( g − 2 ) ( g − 3 ) Δ U s − g ∑ i : λ i ≥ 0 λ i 2 ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) + Δ U s − g ∑ i : λ i < 0 λ i 2 ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) ≤ ( s − 2 ) ( s − 3 ) ( g − 2 ) ( g − 3 ) Δ U s − g ( ∫ d U ( x ) g − 2 U ( x , y ) ( 1 − U ( x , y ) ) d x d y + ∑ i λ i 2 ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) ) = ( s − 2 ) ( s − 3 ) ( g − 2 ) ( g − 3 ) Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) . \begin{aligned}
M_{s-1}(U)-t(C_s,U)
&=\int d_U(x)^{s-2}U(x,y)(1-U(x,y))\,\mathrm{d}x\,\mathrm{d}y\\
&\quad+\sum_i\lambda_i^2\left(\int d_U(x)^{s-2}f_i(x)^2\,\mathrm{d}x-\lambda_i^{s-2}\right)\\
&\le\Delta_U^{s-g}\int d_U(x)^{g-2}U(x,y)(1-U(x,y))\,\mathrm{d}x\,\mathrm{d}y\\
&\quad+\frac{(s-2)(s-3)}{(g-2)(g-3)}\Delta_U^{s-g}\sum_{i:\lambda_i\ge0}\lambda_i^2\left(\int d_U(x)^{g-2}f_i(x)^2\,\mathrm{d}x-\lambda_i^{g-2}\right)\\
&\quad+\Delta_U^{s-g}\sum_{i:\lambda_i<0}\lambda_i^2\left(\int d_U(x)^{g-2}f_i(x)^2\,\mathrm{d}x-\lambda_i^{g-2}\right)\\
&\le\frac{(s-2)(s-3)}{(g-2)(g-3)}\Delta_U^{s-g}\left(\int d_U(x)^{g-2}U(x,y)(1-U(x,y))\,\mathrm{d}x\,\mathrm{d}y\right.\\
&\qquad\left.+\sum_i\lambda_i^2\left(\int d_U(x)^{g-2}f_i(x)^2\,\mathrm{d}x-\lambda_i^{g-2}\right)\right)\\
&=\frac{(s-2)(s-3)}{(g-2)(g-3)}\Delta_U^{s-g}\bigl(M_{g-1}(U)-t(C_g,U)\bigr).
\end{aligned} M s − 1 ( U ) − t ( C s , U ) = ∫ d U ( x ) s − 2 U ( x , y ) ( 1 − U ( x , y )) d x d y + i ∑ λ i 2 ( ∫ d U ( x ) s − 2 f i ( x ) 2 d x − λ i s − 2 ) ≤ Δ U s − g ∫ d U ( x ) g − 2 U ( x , y ) ( 1 − U ( x , y )) d x d y + ( g − 2 ) ( g − 3 ) ( s − 2 ) ( s − 3 ) Δ U s − g i : λ i ≥ 0 ∑ λ i 2 ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) + Δ U s − g i : λ i < 0 ∑ λ i 2 ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) ≤ ( g − 2 ) ( g − 3 ) ( s − 2 ) ( s − 3 ) Δ U s − g ( ∫ d U ( x ) g − 2 U ( x , y ) ( 1 − U ( x , y )) d x d y + i ∑ λ i 2 ( ∫ d U ( x ) g − 2 f i ( x ) 2 d x − λ i g − 2 ) ) = ( g − 2 ) ( g − 3 ) ( s − 2 ) ( s − 3 ) Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) .
The first inequality follows from (4.21), (4.22), and d U ( x ) s − 2 ≤ Δ U s − g d U ( x ) g − 2 d_U(x)^{s-2}\le\Delta_U^{s-g}d_U(x)^{g-2} d U ( x ) s − 2 ≤ Δ U s − g d U ( x ) g − 2 . The second follows from ( s − 2 ) ( s − 3 ) / ( ( g − 2 ) ( g − 3 ) ) ≥ 1 (s-2)(s-3)/((g-2)(g-3))\ge1 ( s − 2 ) ( s − 3 ) / (( g − 2 ) ( g − 3 )) ≥ 1 and the nonnegativity of the integral and summands. The last equality is (4.20) with s = g s=g s = g .
The bound for small maximum degree
For s ≥ 3 s\ge3 s ≥ 3 , let c s ( H ) c_s(H) c s ( H ) be the number of simple s s s -cycles in H H H , counted without a choice of orientation or starting vertex.
In this subsection, H H H has girth g g g , where g g g is odd. Thus c g ( H ) ≥ 1 c_g(H)\ge1 c g ( H ) ≥ 1 and c s ( H ) = 0 c_s(H)=0 c s ( H ) = 0 for s < g s<g s < g .
Lemma 4.11. For g ≤ s ≤ v ( H ) g\le s\le v(H) g ≤ s ≤ v ( H ) ,
2 s c s ( H ) ≤ v ( H ) ⌈ 2 s / ( g − 1 ) ⌉ ≤ v ( H ) s − g + 3 . (39) 2s\,c_s(H)\le v(H)^{\lceil2s/(g-1)\rceil}\le v(H)^{s-g+3}. \tag*{(39)} 2 s c s ( H ) ≤ v ( H ) ⌈ 2 s / ( g − 1 )⌉ ≤ v ( H ) s − g + 3 . (39)
In particular , c g ( H ) ≤ v ( H ) 3 c_g(H)\le v(H)^3 c g ( H ) ≤ v ( H ) 3 .
Proof. Set h = ( g − 1 ) / 2 h=(g-1)/2 h = ( g − 1 ) /2 and k = ⌈ s / h ⌉ k=\lceil s/h\rceil k = ⌈ s / h ⌉ . Two distinct paths P , Q P,Q P , Q of length at most h h h with the same endpoints would contain a cycle in their union, giving
g ≤ e ( P ∪ Q ) ≤ e ( P ) + e ( Q ) ≤ 2 h = g − 1. g\le e(P\cup Q)\le e(P)+e(Q)\le2h=g-1. g ≤ e ( P ∪ Q ) ≤ e ( P ) + e ( Q ) ≤ 2 h = g − 1.
Since 1 ≤ s − ( k − 1 ) h ≤ h 1 \le s-(k-1)h \le h 1 ≤ s − ( k − 1 ) h ≤ h , the map
( v 0 , … , v s − 1 ) ↦ ( v 0 , v h , … , v ( k − 1 ) h ) (v_0,\ldots,v_{s-1}) \mapsto(v_0,v_h,\ldots,v_{(k-1)h}) ( v 0 , … , v s − 1 ) ↦ ( v 0 , v h , … , v ( k − 1 ) h )
is injective on oriented s s s -cycles with a specified starting vertex. Consequently,
2 s c s ( H ) ≤ ∣ V ( H ) k ∣ = v ( H ) k . 2s\,c_s(H) \le|V(H)^k|=v(H)^k. 2 s c s ( H ) ≤ ∣ V ( H ) k ∣ = v ( H ) k .
Finally, s ≥ g = 2 h + 1 s \ge g=2h+1 s ≥ g = 2 h + 1 and h ≥ 1 h \ge1 h ≥ 1 give
k = ⌈ 2 s g − 1 ⌉ = 2 + ⌈ s − g + 1 h ⌉ ≤ 2 + ( s − g + 1 ) = s − g + 3. k=\left\lceil\frac{2s}{g-1}\right\rceil=2+\left\lceil\frac{s-g+1}{h}\right\rceil\le2+(s-g+1)=s-g+3. k = ⌈ g − 1 2 s ⌉ = 2 + ⌈ h s − g + 1 ⌉ ≤ 2 + ( s − g + 1 ) = s − g + 3.
□ \square □
Deleting an edge of C s C_s C s and applying Lemma 4.3 gives
0 ≤ t ( P s , U ) − t ( C s , U ) ≤ M s − 1 ( U ) − t ( C s , U ) ( s ≥ 3 ) . (40) 0\le t(P_s,U)-t(C_s,U)\le M_{s-1}(U)-t(C_s,U)\qquad(s\ge3). \tag*{(40)} 0 ≤ t ( P s , U ) − t ( C s , U ) ≤ M s − 1 ( U ) − t ( C s , U ) ( s ≥ 3 ) . (40)
For g ≤ s ≤ v ( H ) g\le s\le v(H) g ≤ s ≤ v ( H ) , we obtain
t ( P s , U ) − t ( C s , U ) ≤ { M g − 1 ( U ) − t ( C g , U ) , s = g , v ( H ) 2 Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) , g < s ≤ v ( H ) . (41) t(P_s,U)-t(C_s,U)\le
\begin{cases}
M_{g-1}(U)-t(C_g,U), & s=g,\\
v(H)^2\Delta_U^{s-g}\bigl(M_{g-1}(U)-t(C_g,U)\bigr), & g<s\le v(H).
\end{cases} \tag*{(41)} t ( P s , U ) − t ( C s , U ) ≤ { M g − 1 ( U ) − t ( C g , U ) , v ( H ) 2 Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) , s = g , g < s ≤ v ( H ) . (41)
The case s = g s=g s = g follows from (40) . For g = 3 g=3 g = 3 and 3 < s ≤ v ( H ) 3<s\le v(H) 3 < s ≤ v ( H ) ,
t ( P s , U ) − t ( C s , U ) ≤ ( s − 2 ) Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U ) ) ≤ v ( H ) 2 Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U ) ) , \begin{aligned}
t(P_s,U)-t(C_s,U)\le(s-2)\Delta_U^{s-3}\bigl(M_2(U)-t(C_3,U)\bigr) \\
&\le v(H)^2\Delta_U^{s-3}\bigl(M_2(U)-t(C_3,U)\bigr),
\end{aligned} t ( P s , U ) − t ( C s , U ) ≤ ( s − 2 ) Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U ) ) ≤ v ( H ) 2 Δ U s − 3 ( M 2 ( U ) − t ( C 3 , U ) ) ,
where the first inequality is Lemma 4.6 and the last follows from s − 2 ≤ v ( H ) 2 s-2\le v(H)^2 s − 2 ≤ v ( H ) 2 . For odd g ≥ 5 g\ge5 g ≥ 5 and g < s ≤ v ( H ) g<s\le v(H) g < s ≤ v ( H ) ,
t ( P s , U ) − t ( C s , U ) ≤ M s − 1 ( U ) − t ( C s , U ) ≤ ( s − 2 ) ( s − 3 ) ( g − 2 ) ( g − 3 ) Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) ≤ v ( H ) 2 Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) , \begin{aligned}
t(P_s,U)-t(C_s,U)\le M_{s-1}(U)-t(C_s,U) \\
&\le\frac{(s-2)(s-3)}{(g-2)(g-3)}\Delta_U^{s-g}\bigl(M_{g-1}(U)-t(C_g,U)\bigr) \\
&\le v(H)^2\Delta_U^{s-g}\bigl(M_{g-1}(U)-t(C_g,U)\bigr),
\end{aligned} t ( P s , U ) − t ( C s , U ) ≤ M s − 1 ( U ) − t ( C s , U ) ≤ ( g − 2 ) ( g − 3 ) ( s − 2 ) ( s − 3 ) Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) ≤ v ( H ) 2 Δ U s − g ( M g − 1 ( U ) − t ( C g , U ) ) ,
where the first two inequalities follow from (40) and Theorem 4.7 , respectively, and the last follows from ( s − 2 ) ( s − 3 ) / ( ( g − 2 ) ( g − 3 ) ) ≤ s 2 ≤ v ( H ) 2 (s-2)(s-3)/((g-2)(g-3))\le s^2\le v(H)^2 ( s − 2 ) ( s − 3 ) / (( g − 2 ) ( g − 3 )) ≤ s 2 ≤ v ( H ) 2 .
Proposition 4.12. Let H H H have girth g g g , where g g g is odd. If e ( H ) Δ U ≤ 1 / 2 e(H)\Delta_U\le1/2 e ( H ) Δ U ≤ 1/2 and v ( H ) Δ U ≤ 1 / 2 v(H)\Delta_U\le1/2 v ( H ) Δ U ≤ 1/2 , then
t ( H , 1 − U ) − Φ H ( 1 − q ) ≥ ( ∑ v ∈ V ( H ) ( d H ( v ) 2 ) − c 3 ( H ) − 2 v ( H ) 6 Δ U ) Var ( d U ) t(H,1-U)-\Phi_H(1-q)
\ge\left(\sum_{v\in V(H)}\binom{d_H(v)}{2}-c_3(H)-2v(H)^6\Delta_U\right)\operatorname{Var}(d_U) t ( H , 1 − U ) − Φ H ( 1 − q ) ≥ v ∈ V ( H ) ∑ ( 2 d H ( v ) ) − c 3 ( H ) − 2 v ( H ) 6 Δ U Var ( d U ) + c g ( H ) ( 1 − 5 v ( H ) 6 Δ U ) ( M g − 1 ( U ) − t ( C g , U ) ) . (42) \qquad{}+c_g(H)(1-5v(H)^6\Delta_U)\bigl(M_{g-1}(U)-t(C_g,U)\bigr). \tag*{(42)} + c g ( H ) ( 1 − 5 v ( H ) 6 Δ U ) ( M g − 1 ( U ) − t ( C g , U ) ) . (42) In particular, Δ U ≤ ( 6 v ( H ) 6 ) − 1 \Delta_U\le(6v(H)^6)^{-1} Δ U ≤ ( 6 v ( H ) 6 ) − 1 implies t ( H , 1 − U ) ≥ Φ H ( 1 − q ) t(H,1-U)\ge\Phi_H(1-q) t ( H , 1 − U ) ≥ Φ H ( 1 − q ) .
Proof. Each triangle contains three adjacent edge pairs, and an adjacent pair belongs to at most one triangle. Since H H H contains a cycle,
∑ v ∈ V ( H ) ( d H ( v ) 2 ) − c 3 ( H ) ≥ 1. \sum_{v\in V(H)}\binom{d_H(v)}{2}-c_3(H)\ge1. v ∈ V ( H ) ∑ ( 2 d H ( v ) ) − c 3 ( H ) ≥ 1.
Assume Δ U > 0 \Delta_U > 0 Δ U > 0 .
For forests F F F with at most two edges,
t ( F , U ) = { 1 , ∣ F ∣ = 0 , q , ∣ F ∣ = 1 , q 2 , F has two disjoint edges , ∫ d U ( x ) 2 d x = M 2 ( U ) , F has two adjacent edges . t(F,U)=
\begin{cases}
1, & |F|=0,\\
q, & |F|=1,\\
q^2, & F\text{ has two disjoint edges},\\
\int d_U(x)^2\,\mathrm{d}x=M_2(U), & F\text{ has two adjacent edges}.
\end{cases} t ( F , U ) = ⎩ ⎨ ⎧ 1 , q , q 2 , ∫ d U ( x ) 2 d x = M 2 ( U ) , ∣ F ∣ = 0 , ∣ F ∣ = 1 , F has two disjoint edges , F has two adjacent edges .
Their contribution to the first sum of (22) is
∑ F forest , B ( F ) = ∅ ∣ F ∣ ≤ 2 ( − 1 ) ∣ F ∣ ( t ( F , U ) − q ∣ F ∣ ) = ( ∑ v ∈ V ( H ) ( d H ( v ) 2 ) − c 3 ( H ) ) ( M 2 ( U ) − q 2 ) = ( ∑ v ∈ V ( H ) ( d H ( v ) 2 ) − c 3 ( H ) ) Var ( d U ) . \begin{aligned}
\sum_{\substack{F\text{ forest},\,B(F)=\varnothing\\ |F|\le2}}(-1)^{|F|}\bigl(t(F,U)-q^{|F|}\bigr)
&=\left(\sum_{v\in V(H)}\binom{d_H(v)}{2}-c_3(H)\right)\left(M_2(U)-q^2\right)\\
&=\left(\sum_{v\in V(H)}\binom{d_H(v)}{2}-c_3(H)\right)\operatorname{Var}(d_U).
\end{aligned} F forest , B ( F ) = ∅ ∣ F ∣ ≤ 2 ∑ ( − 1 ) ∣ F ∣ ( t ( F , U ) − q ∣ F ∣ ) = v ∈ V ( H ) ∑ ( 2 d H ( v ) ) − c 3 ( H ) ( M 2 ( U ) − q 2 ) = v ∈ V ( H ) ∑ ( 2 d H ( v ) ) − c 3 ( H ) Var ( d U ) .
Here ∑ v ∈ V ( H ) ( d H ( v ) 2 ) \sum_{v\in V(H)}\binom{d_H(v)}{2} ∑ v ∈ V ( H ) ( 2 d H ( v ) ) counts the pairs of adjacent edges, and exactly c 3 ( H ) c_3(H) c 3 ( H ) of these have nonempty B ( F ) B(F) B ( F ) , one for each triangle with its largest edge removed.
If B ( F ) ≠ ∅ B(F)\ne\varnothing B ( F ) = ∅ , choose e = u v ∈ B ( F ) e=uv\in B(F) e = uv ∈ B ( F ) . The edge e e e and the u u u –v v v path in F F F form a cycle, so ∣ F ∣ ≥ g − 1 |F|\ge g-1 ∣ F ∣ ≥ g − 1 . If ∣ F ∣ = g − 1 |F|=g-1 ∣ F ∣ = g − 1 , this cycle has length g g g , and F F F is obtained by deleting its largest edge e e e . Any other edge in B ( F ) B(F) B ( F ) would join two vertices at distance at most g − 2 g-2 g − 2 along the path and create a cycle of length at most g − 1 g-1 g − 1 . Thus B ( F ) = { e } B(F)=\{e\} B ( F ) = { e } , and
I F ( U ) = ∫ ( ∏ a b ∈ F U ( x a , x b ) ) ( 1 − U ( x u , x v ) ) ∏ w ∈ V ( H ) d x w = t ( P g , U ) − t ( C g , U ) . \begin{aligned}
I_F(U)&=\int\left(\prod_{ab\in F}U(x_a,x_b)\right)\left(1-U(x_u,x_v)\right)\prod_{w\in V(H)}\mathrm{d}x_w\\
&=t(P_g,U)-t(C_g,U).
\end{aligned} I F ( U ) = ∫ ( ab ∈ F ∏ U ( x a , x b ) ) ( 1 − U ( x u , x v ) ) w ∈ V ( H ) ∏ d x w = t ( P g , U ) − t ( C g , U ) .
Each g g g -cycle gives exactly one such forest by deleting its largest edge. Hence
∑ F forest , B ( F ) ≠ ∅ ∣ F ∣ = g − 1 ( − 1 ) ∣ F ∣ I F ( U ) = ( − 1 ) g − 1 c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) = c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) , \begin{aligned}
\sum_{\substack{F\text{ forest},\,B(F)\ne\varnothing\\ |F|=g-1}}(-1)^{|F|}I_F(U)
&=(-1)^{g-1}c_g(H)\bigl(t(P_g,U)-t(C_g,U)\bigr)\\
&=c_g(H)\bigl(t(P_g,U)-t(C_g,U)\bigr),
\end{aligned} F forest , B ( F ) = ∅ ∣ F ∣ = g − 1 ∑ ( − 1 ) ∣ F ∣ I F ( U ) = ( − 1 ) g − 1 c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) = c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) ,
where the last equality follows from g g g being odd. Combining these contributions in (22) and bounding the remaining terms in absolute value gives
t ( H , 1 − U ) − Φ H ( 1 − q ) ≥ ( ∑ v ∈ V ( H ) ( d H ( v ) 2 ) − c 3 ( H ) ) Var ( d U ) + c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) − ∑ F forest , B ( F ) = ∅ ∣ F ∣ ≥ 3 ( t ( F , U ) − q ∣ F ∣ ) − ∑ F forest , B ( F ) ≠ ∅ ∣ F ∣ ≥ g I F ( U ) . (43) \begin{aligned}
t(H,1-U)-\Phi_H(1-q)
\ge{}&\left(\sum_{v\in V(H)}\binom{d_H(v)}{2}-c_3(H)\right)\operatorname{Var}(d_U)\\
&+c_g(H)\bigl(t(P_g,U)-t(C_g,U)\bigr)\\
&-\sum_{\substack{F\text{ forest},\,B(F)=\varnothing\\ |F|\ge3}}\bigl(t(F,U)-q^{|F|}\bigr)
-\sum_{\substack{F\text{ forest},\,B(F)\ne\varnothing\\ |F|\ge g}}I_F(U). \tag*{(43)}
\end{aligned} t ( H , 1 − U ) − Φ H ( 1 − q ) ≥ v ∈ V ( H ) ∑ ( 2 d H ( v ) ) − c 3 ( H ) Var ( d U ) + c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) − F forest , B ( F ) = ∅ ∣ F ∣ ≥ 3 ∑ ( t ( F , U ) − q ∣ F ∣ ) − F forest , B ( F ) = ∅ ∣ F ∣ ≥ g ∑ I F ( U ) . (43)
By (24) ,
∑ F f o r e s t , B ( F ) = ∅ ∣ F ∣ ≥ 3 ( t ( F , U ) − q ∣ F ∣ ) ≤ Var ( d U ) ∑ r = 3 e ( H ) ( e ( H ) r ) ( r 2 ) Δ U r − 2 = ( e ( H ) 2 ) ( ( 1 + Δ U ) e ( H ) − 2 − 1 ) Var ( d U ) ≤ 2 e ( H ) 3 Δ U Var ( d U ) . (44) \sum_{\substack{F\ \mathrm{forest},\ B(F)=\emptyset\\ |F|\geq3}} \left(t(F,U)-q^{|F|}\right)
\leq\operatorname{Var}(d_U)\sum_{r=3}^{e(H)} \binom{e(H)}{r}\binom{r}{2}\Delta_U^{r-2}
= \binom{e(H)}{2}\left((1+\Delta_U)^{e(H)-2}-1\right)\operatorname{Var}(d_U)
\leq2e(H)^3\Delta_U\operatorname{Var}(d_U). \tag*{(44)} F forest , B ( F ) = ∅ ∣ F ∣ ≥ 3 ∑ ( t ( F , U ) − q ∣ F ∣ ) ≤ Var ( d U ) r = 3 ∑ e ( H ) ( r e ( H ) ) ( 2 r ) Δ U r − 2 = ( 2 e ( H ) ) ( ( 1 + Δ U ) e ( H ) − 2 − 1 ) Var ( d U ) ≤ 2 e ( H ) 3 Δ U Var ( d U ) . (44)
Here e ( H ) Δ U ≤ 1 / 2 e(H)\Delta_U\leq1/2 e ( H ) Δ U ≤ 1/2 and comparison with a geometric series give
( 1 + Δ U ) e ( H ) ≤ 2 , ( 1 + Δ U ) e ( H ) − 1 ≤ 2 e ( H ) Δ U . (1+\Delta_U)^{e(H)}\leq2,\qquad(1+\Delta_U)^{e(H)}-1\leq2e(H)\Delta_U. ( 1 + Δ U ) e ( H ) ≤ 2 , ( 1 + Δ U ) e ( H ) − 1 ≤ 2 e ( H ) Δ U .
For each e = u v ∈ B ( F ) e=uv\in B(F) e = uv ∈ B ( F ) , Lemma 4.5 gives
I F ( U ) ≤ ∫ ∏ a b ∈ F U ( x a , x b ) ( 1 − U ( x u , x v ) ) ∏ w ∈ V ( H ) d x w ≤ Δ U j ( t ( P s , U ) − t ( C s , U ) ) , I_F(U)\leq\int\prod_{ab\in F}U(x_a,x_b)(1-U(x_u,x_v))\prod_{w\in V(H)}\mathrm{d}x_w\leq\Delta_U^j\left(t(P_s,U)-t(C_s,U)\right), I F ( U ) ≤ ∫ ab ∈ F ∏ U ( x a , x b ) ( 1 − U ( x u , x v )) w ∈ V ( H ) ∏ d x w ≤ Δ U j ( t ( P s , U ) − t ( C s , U ) ) ,
where s s s is the length of the cycle formed by e e e and its path in F F F , and j = ∣ F ∣ − s + 1 j=|F|-s+1 j = ∣ F ∣ − s + 1 . Here e e e is the largest edge of the cycle, and there are at most ( e ( H ) j ) \binom{e(H)}{j} ( j e ( H ) ) choices for the remaining edges of $F. For ∣ F ∣ ≥ g |F|\geq g ∣ F ∣ ≥ g , we have j ≥ 1 j\geq1 j ≥ 1 when s = g s=g s = g and j ≥ 0 j\geq0 j ≥ 0 when s > g s>g s > g . Summing these bounds over all such forests F F F and all edges e ∈ B ( F ) e\in B(F) e ∈ B ( F ) gives
∑ F f o r e s t , B ( F ) ≠ ∅ ∣ F ∣ ≥ g I F ( U ) ≤ c g ( H ) ( ( 1 + Δ U ) e ( H ) − 1 ) ( t ( P g , U ) − t ( C g , U ) ) + ( 1 + Δ U ) e ( H ) ∑ s = g + 1 v ( H ) c s ( H ) ( t ( P s , U ) − t ( C s , U ) ) . (45) \begin{aligned}
\sum_{\substack{F\ \mathrm{forest},\ B(F)\neq\emptyset\\ |F|\geq g}} I_F(U)
&\leq c_g(H)\left((1+\Delta_U)^{e(H)}-1\right)\left(t(P_g,U)-t(C_g,U)\right)\\
&\quad+(1+\Delta_U)^{e(H)}\sum_{s=g+1}^{v(H)}c_s(H)\left(t(P_s,U)-t(C_s,U)\right). \tag*{(45)}
\end{aligned} F forest , B ( F ) = ∅ ∣ F ∣ ≥ g ∑ I F ( U ) ≤ c g ( H ) ( ( 1 + Δ U ) e ( H ) − 1 ) ( t ( P g , U ) − t ( C g , U ) ) + ( 1 + Δ U ) e ( H ) s = g + 1 ∑ v ( H ) c s ( H ) ( t ( P s , U ) − t ( C s , U ) ) . (45)
By (39) and (41) ,
∑ s = g + 1 v ( H ) c s ( H ) ( t ( P s , U ) − t ( C s , U ) ) ≤ v ( H ) 5 ( M g − 1 ( U ) − t ( C g , U ) ) ∑ j = 1 v ( H ) − g ( v ( H ) Δ U ) j ≤ 2 v ( H ) 6 Δ U ( M g − 1 ( U ) − t ( C g , U ) ) . \begin{aligned}
\sum_{s=g+1}^{v(H)}c_s(H)\left(t(P_s,U)-t(C_s,U)\right)
&\leq v(H)^5\left(M_{g-1}(U)-t(C_g,U)\right)\sum_{j=1}^{v(H)-g}\left(v(H)\Delta_U\right)^j\\
&\leq2v(H)^6\Delta_U\left(M_{g-1}(U)-t(C_g,U)\right).
\end{aligned} s = g + 1 ∑ v ( H ) c s ( H ) ( t ( P s , U ) − t ( C s , U ) ) ≤ v ( H ) 5 ( M g − 1 ( U ) − t ( C g , U ) ) j = 1 ∑ v ( H ) − g ( v ( H ) Δ U ) j ≤ 2 v ( H ) 6 Δ U ( M g − 1 ( U ) − t ( C g , U ) ) .
It follows that
∑ F f o r e s t , B ( F ) ≠ ∅ ∣ F ∣ ≥ g I F ( U ) ≤ ( 2 c g ( H ) e ( H ) + 4 v ( H ) 6 ) Δ U ( M g − 1 ( U ) − t ( C g , U ) ) ≤ 5 c g ( H ) v ( H ) 6 Δ U ( M g − 1 ( U ) − t ( C g , U ) ) . (46) \begin{aligned}
\sum_{\substack{F\ \mathrm{forest},\ B(F)\neq\emptyset\\ |F|\geq g}} I_F(U)
&\leq\left(2c_g(H)e(H)+4v(H)^6\right)\Delta_U\left(M_{g-1}(U)-t(C_g,U)\right)\\
&\leq5c_g(H)v(H)^6\Delta_U\left(M_{g-1}(U)-t(C_g,U)\right). \tag*{(46)}
\end{aligned} F forest , B ( F ) = ∅ ∣ F ∣ ≥ g ∑ I F ( U ) ≤ ( 2 c g ( H ) e ( H ) + 4 v ( H ) 6 ) Δ U ( M g − 1 ( U ) − t ( C g , U ) ) ≤ 5 c g ( H ) v ( H ) 6 Δ U ( M g − 1 ( U ) − t ( C g , U ) ) . (46)
where c g ( H ) ≥ 1 c_g(H)\geq1 c g ( H ) ≥ 1 and 2 e ( H ) ≤ v ( H ) 2 ≤ v ( H ) 6 2e(H)\leq v(H)^2\leq v(H)^6 2 e ( H ) ≤ v ( H ) 2 ≤ v ( H ) 6 .
For g = 3 g=3 g = 3 , we have t ( P g , U ) = M g − 1 ( U ) t(P_g,U)=M_{g-1}(U) t ( P g , U ) = M g − 1 ( U ) . For g ≥ 5 g\ge5 g ≥ 5 , Lemma 4.3 and (25) give
0 ≤ M g − 1 ( U ) − t ( P g , U ) ≤ M g − 1 ( U ) − q g − 1 ≤ ( g − 1 2 ) Δ U g − 3 Var ( d U ) . 0\le M_{g-1}(U)-t(P_g,U)\le M_{g-1}(U)-q^{g-1}
\le\binom{g-1}{2}\Delta_U^{g-3}\operatorname{Var}(d_U). 0 ≤ M g − 1 ( U ) − t ( P g , U ) ≤ M g − 1 ( U ) − q g − 1 ≤ ( 2 g − 1 ) Δ U g − 3 Var ( d U ) .
Using c g ( H ) ≤ v ( H ) 3 c_g(H)\le v(H)^3 c g ( H ) ≤ v ( H ) 3 and Δ U ≤ 1 \Delta_U\le1 Δ U ≤ 1 , both cases give
c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) ≥ c g ( H ) ( M g − 1 ( U ) − t ( C g , U ) ) − v ( H ) 5 2 Δ U 2 Var ( d U ) . c_g(H)\bigl(t(P_g,U)-t(C_g,U)\bigr)\ge c_g(H)\bigl(M_{g-1}(U)-t(C_g,U)\bigr)-\frac{v(H)^5}{2}\Delta_U^2\operatorname{Var}(d_U). c g ( H ) ( t ( P g , U ) − t ( C g , U ) ) ≥ c g ( H ) ( M g − 1 ( U ) − t ( C g , U ) ) − 2 v ( H ) 5 Δ U 2 Var ( d U ) .
Combining this with (43) , (44) , and (46) gives (42) , since
2 e ( H ) 3 Δ U + v ( H ) 5 2 Δ U 2 ≤ ( v ( H ) 6 4 + v ( H ) 5 2 ) Δ U ≤ 2 v ( H ) 6 Δ U . 2e(H)^3\Delta_U+\frac{v(H)^5}{2}\Delta_U^2\le\left(\frac{v(H)^6}{4}+\frac{v(H)^5}{2}\right)\Delta_U\le2v(H)^6\Delta_U. 2 e ( H ) 3 Δ U + 2 v ( H ) 5 Δ U 2 ≤ ( 4 v ( H ) 6 + 2 v ( H ) 5 ) Δ U ≤ 2 v ( H ) 6 Δ U .
Finally, Δ U ≤ ( 6 v ( H ) 6 ) − 1 \Delta_U\le(6v(H)^6)^{-1} Δ U ≤ ( 6 v ( H ) 6 ) − 1 satisfies both hypotheses and gives
t ( H , 1 − U ) − Φ H ( 1 − q ) ≥ 2 3 Var ( d U ) + c g ( H ) 6 ( M g − 1 ( U ) − t ( C g , U ) ) ≥ 0. t(H,1-U)-\Phi_H(1-q)
\ge\frac{2}{3}\operatorname{Var}(d_U)+\frac{c_g(H)}{6}\bigl(M_{g-1}(U)-t(C_g,U)\bigr)\ge0. t ( H , 1 − U ) − Φ H ( 1 − q ) ≥ 3 2 Var ( d U ) + 6 c g ( H ) ( M g − 1 ( U ) − t ( C g , U ) ) ≥ 0.
From maximum degree to edge density
For a graphon V V V , define
D H ( V ) = t ( H , 1 − V ) − 1 + e ( H ) t ( K 2 , V ) . D_H(V)=t(H,1-V)-1+e(H)t(K_2,V). D H ( V ) = t ( H , 1 − V ) − 1 + e ( H ) t ( K 2 , V ) .
We write ( a ) + = max { a , 0 } (a)_+=\max\{a,0\} ( a ) + = max { a , 0 } .
Lemma 4.13. For every graphon V V V , D H ( V ) ≥ 0 D_H(V)\ge0 D H ( V ) ≥ 0 . If V 1 , V 2 V_1,V_2 V 1 , V 2 are graphons with V 1 + V 2 ≤ 1 V_1+V_2\le1 V 1 + V 2 ≤ 1 , then
D H ( V 1 + V 2 ) ≥ D H ( V 1 ) + D H ( V 2 ) . (47) D_H(V_1+V_2)\ge D_H(V_1)+D_H(V_2). \tag*{(47)} D H ( V 1 + V 2 ) ≥ D H ( V 1 ) + D H ( V 2 ) . (47)
Proof. Choose independent uniform positions ( Z v ) v ∈ V ( H ) (Z_v)_{v\in V(H)} ( Z v ) v ∈ V ( H ) in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Conditional on these positions, select each edge u v uv uv independently with probability V ( Z u , Z v ) V(Z_u,Z_v) V ( Z u , Z v ) , and let N N N be the number of selected edges. Then E N = e ( H ) t ( K 2 , V ) \mathbb{E}N=e(H)t(K_2,V) E N = e ( H ) t ( K 2 , V ) and P ( N = 0 ) = t ( H , 1 − V ) \mathbb{P}(N=0)=t(H,1-V) P ( N = 0 ) = t ( H , 1 − V ) , so
D H ( V ) = E N − 1 + P ( N = 0 ) = E ( N − 1 + 1 { N = 0 } ) = E ( N − 1 ) + ≥ 0. (48) D_H(V)=\mathbb{E}N-1+\mathbb{P}(N=0)
=\mathbb{E}\bigl(N-1+\mathbf{1}_{\{N=0\}}\bigr)=\mathbb{E}(N-1)_+\ge0. \tag*{(48)} D H ( V ) = E N − 1 + P ( N = 0 ) = E ( N − 1 + 1 { N = 0 } ) = E ( N − 1 ) + ≥ 0. (48)
To prove (47) , assign each edge u v uv uv one of three outcomes with probabilities V 1 ( Z u , Z v ) V_1(Z_u,Z_v) V 1 ( Z u , Z v ) , V 2 ( Z u , Z v ) V_2(Z_u,Z_v) V 2 ( Z u , Z v ) , and 1 − V 1 ( Z u , Z v ) − V 2 ( Z u , Z v ) 1-V_1(Z_u,Z_v)-V_2(Z_u,Z_v) 1 − V 1 ( Z u , Z v ) − V 2 ( Z u , Z v ) , independently conditional on the positions. Let N 1 N_1 N 1 and N 2 N_2 N 2 be the numbers of edges with the first and second outcomes, respectively. Then
( N 1 + N 2 − 1 ) + ≥ ( N 1 − 1 ) + + ( N 2 − 1 ) + . (N_1+N_2-1)_+\ge(N_1-1)_++(N_2-1)_+. ( N 1 + N 2 − 1 ) + ≥ ( N 1 − 1 ) + + ( N 2 − 1 ) + .
Taking expectations proves (47) .
Lemma 4.14. For e ( H ) ≥ 1 e(H)\ge1 e ( H ) ≥ 1 and q 1 , q 2 ≥ 0 q_1,q_2\ge0 q 1 , q 2 ≥ 0 with q = q 1 + q 2 ≤ 1 / ( 2 e ( H ) ) q=q_1+q_2\le1/(2e(H)) q = q 1 + q 2 ≤ 1/ ( 2 e ( H )) ,
∣ Φ H ( 1 − q ) − Φ H ( 1 − q 2 ) + e ( H ) q 1 ∣ ≤ 2 e ( H ) 2 q q 1 . (49) \left|\Phi_H(1-q)-\Phi_H(1-q_2)+e(H)q_1\right|\le2e(H)^2qq_1. \tag*{(49)} ∣ Φ H ( 1 − q ) − Φ H ( 1 − q 2 ) + e ( H ) q 1 ∣ ≤ 2 e ( H ) 2 q q 1 . (49)
Proof. If e ( H ) = 1 e(H)=1 e ( H ) = 1 , then Φ H ( p ) = p \Phi_H(p)=p Φ H ( p ) = p and the left-hand side is zero. For e ( H ) ≥ 2 e(H)\ge2 e ( H ) ≥ 2 , (4.4) gives Φ H ′ ( 1 ) = e ( H ) \Phi'_H(1)=e(H) Φ H ′ ( 1 ) = e ( H ) and shows that the coefficient of q j q^j q j in Φ H ( 1 − q ) \Phi_H(1-q) Φ H ( 1 − q ) has absolute value at most ( e ( H ) j ) \binom{e(H)}{j} ( j e ( H ) ) . Hence, for 0 ≤ x ≤ 1 / ( 2 e ( H ) ) 0\le x\le1/(2e(H)) 0 ≤ x ≤ 1/ ( 2 e ( H )) ,
∣ Φ H ′ ′ ( 1 − x ) ∣ ≤ ∑ j = 2 e ( H ) ( e ( H ) j ) j ( j − 1 ) x j − 2 = e ( H ) ( e ( H ) − 1 ) ( 1 + x ) e ( H ) − 2 ≤ 2 e ( H ) 2 . \begin{aligned}
\left|\Phi''_H(1-x)\right|\le\sum_{j=2}^{e(H)}\binom{e(H)}{j}j(j-1)x^{j-2} \\
&=e(H)(e(H)-1)(1+x)^{e(H)-2}\le2e(H)^2.
\end{aligned} ∣ Φ H ′′ ( 1 − x ) ∣ ≤ j = 2 ∑ e ( H ) ( j e ( H ) ) j ( j − 1 ) x j − 2 = e ( H ) ( e ( H ) − 1 ) ( 1 + x ) e ( H ) − 2 ≤ 2 e ( H ) 2 .
Integrating gives
∣ e ( H ) − Φ H ′ ( 1 − x ) ∣ = ∣ ∫ 0 x Φ H ′ ′ ( 1 − y ) d y ∣ ≤ 2 e ( H ) 2 x . \left|e(H)-\Phi'_H(1-x)\right|=\left|\int_0^x\Phi''_H(1-y)\,\mathrm{d}y\right|\le2e(H)^2x. ∣ e ( H ) − Φ H ′ ( 1 − x ) ∣ = ∫ 0 x Φ H ′′ ( 1 − y ) d y ≤ 2 e ( H ) 2 x .
Since q − q 2 = q 1 q-q_2=q_1 q − q 2 = q 1 , a second integration gives
∣ Φ H ( 1 − q ) − Φ H ( 1 − q 2 ) + e ( H ) q 1 ∣ = ∣ ∫ q 2 q ( e ( H ) − Φ H ′ ( 1 − x ) ) d x ∣ ≤ ∫ q 2 q 2 e ( H ) 2 x d x = e ( H ) 2 ( q 2 − q 2 2 ) = e ( H ) 2 q 1 ( q + q 2 ) ≤ 2 e ( H ) 2 q q 1 . \begin{aligned}
\left|\Phi_H(1-q)-\Phi_H(1-q_2)+e(H)q_1\right|
=\left|\int_{q_2}^{q}\left(e(H)-\Phi'_H(1-x)\right)\,\mathrm{d}x\right| \\
&\le\int_{q_2}^{q}2e(H)^2x\,\mathrm{d}x \\
&=e(H)^2(q^2-q_2^2)=e(H)^2q_1(q+q_2)\le2e(H)^2qq_1.
\end{aligned} ∣ Φ H ( 1 − q ) − Φ H ( 1 − q 2 ) + e ( H ) q 1 ∣ = ∫ q 2 q ( e ( H ) − Φ H ′ ( 1 − x ) ) d x ≤ ∫ q 2 q 2 e ( H ) 2 x d x = e ( H ) 2 ( q 2 − q 2 2 ) = e ( H ) 2 q 1 ( q + q 2 ) ≤ 2 e ( H ) 2 q q 1 .
Proposition 4.15. Suppose H H H has a vertex of degree at least two, and let 0 < δ ≤ 1 / v ( H ) 0<\delta\le1/v(H) 0 < δ ≤ 1/ v ( H ) . Assume that every graphon V V V with Δ V ≤ δ \Delta_V\le\delta Δ V ≤ δ satisfies
t ( H , 1 − V ) ≥ Φ H ( 1 − t ( K 2 , V ) ) . t(H,1-V)\ge\Phi_H(1-t(K_2,V)). t ( H , 1 − V ) ≥ Φ H ( 1 − t ( K 2 , V )) . Then t ( H , 1 − U ) ≥ Φ H ( 1 − q ) t(H,1-U)\ge\Phi_H(1-q) t ( H , 1 − U ) ≥ Φ H ( 1 − q ) whenever
q = t ( K 2 , U ) < min { δ 2 2 , δ 32 e ( H ) 2 } . (50) q=t(K_2,U)<\min\left\{\frac{\delta^2}{2},\frac{\delta}{32e(H)^2}\right\}. \tag*{(50)} q = t ( K 2 , U ) < min { 2 δ 2 , 32 e ( H ) 2 δ } . (50) If 16 e ( H ) 2 δ ≤ 1 16e(H)^2\delta\le1 16 e ( H ) 2 δ ≤ 1 , it suffices that q < δ 2 / 2 q<\delta^2/2 q < δ 2 /2 .
Proof. Let A = { x ∈ [ 0 , 1 ] : d U ( x ) > δ } A=\{x\in[0,1]:d_U(x)>\delta\} A = { x ∈ [ 0 , 1 ] : d U ( x ) > δ } and let s = ∣ A ∣ s=|A| s = ∣ A ∣ be its size. Decompose U U U as
U 1 ( x , y ) = U ( x , y ) 1 { x ∈ A or y ∈ A } , U 2 = U − U 1 , U_1(x,y)=U(x,y)1_{\{x\in A\text{ or }y\in A\}},\qquad U_2=U-U_1, U 1 ( x , y ) = U ( x , y ) 1 { x ∈ A or y ∈ A } , U 2 = U − U 1 , and write q i = t ( K 2 , U i ) q_i=t(K_2,U_i) q i = t ( K 2 , U i ) . Then q 1 + q 2 = q q_1+q_2=q q 1 + q 2 = q and
s ≤ q δ ≤ δ 2 ≤ 1 2 v ( H ) . s\le\frac{q}{\delta}\le\frac{\delta}{2}\le\frac{1}{2v(H)}. s ≤ δ q ≤ 2 δ ≤ 2 v ( H ) 1 . Also Δ U 2 ≤ δ \Delta_{U_2}\le\delta Δ U 2 ≤ δ , so t ( H , 1 − U 2 ) ≥ Φ H ( 1 − q 2 ) t(H,1-U_2)\ge\Phi_H(1-q_2) t ( H , 1 − U 2 ) ≥ Φ H ( 1 − q 2 ) by hypothesis. For x ∈ A x\in A x ∈ A , the average of U ( x , y ) U(x,y) U ( x , y ) over A c A^c A c satisfies
1 1 − s ∫ A c U ( x , y ) d y ≥ d U ( x ) − s 1 − s ≥ d U ( x ) − s ≥ d U ( x ) 2 . (51) \frac{1}{1-s}\int_{A^c}U(x,y)\,\mathrm{d}y\ge\frac{d_U(x)-s}{1-s}\ge d_U(x)-s\ge\frac{d_U(x)}{2}. \tag*{(51)} 1 − s 1 ∫ A c U ( x , y ) d y ≥ 1 − s d U ( x ) − s ≥ d U ( x ) − s ≥ 2 d U ( x ) . (51) Moreover,
q 1 = 2 ∫ A d U ( x ) d x − ∫ A × A U ( x , y ) d x d y ≤ 2 ∫ A d U ( x ) d x . (52) q_1=2\int_A d_U(x)\,\mathrm{d}x-\int_{A\times A}U(x,y)\,\mathrm{d}x\,\mathrm{d}y\le2\int_A d_U(x)\,\mathrm{d}x. \tag*{(52)} q 1 = 2 ∫ A d U ( x ) d x − ∫ A × A U ( x , y ) d x d y ≤ 2 ∫ A d U ( x ) d x . (52)
For a binomial random variable N N N with parameters k ∈ Z ≥ 0 k \in\mathbb{Z}_{\ge0} k ∈ Z ≥ 0 and h ∈ [ 0 , 1 ] h \in[0,1] h ∈ [ 0 , 1 ] , we have
E ( N − 1 ) + = ( 1 − h ) k − 1 + k h ≥ ( k − 1 ) + h 2 . (53) \mathbb{E}(N-1)_+ = (1-h)^k-1+kh \ge(k-1)_+h^2. \tag*{(53)} E ( N − 1 ) + = ( 1 − h ) k − 1 + k h ≥ ( k − 1 ) + h 2 . (53)
The expression is zero for k = 0 , 1 k=0,1 k = 0 , 1 ; for k ≥ 2 k\ge2 k ≥ 2 ,
( 1 − h ) k − 1 + k h = h ∑ j = 1 k − 1 ( 1 − ( 1 − h ) j ) ≥ h ∑ j = 1 k − 1 h = ( k − 1 ) h 2 . (1-h)^k-1+kh=h\sum_{j=1}^{k-1}\left(1-(1-h)^j\right)\ge h\sum_{j=1}^{k-1}h=(k-1)h^2. ( 1 − h ) k − 1 + k h = h j = 1 ∑ k − 1 ( 1 − ( 1 − h ) j ) ≥ h j = 1 ∑ k − 1 h = ( k − 1 ) h 2 .
Let N N N be the number of edges selected according to U 1 U_1 U 1 as in (48) . For each v ∈ V ( H ) v\in V(H) v ∈ V ( H ) , define the event
E v = { Z v ∈ A , Z w ∈ A c for every w ≠ v } . E_v=\{Z_v\in A,\ Z_w\in A^c\text{ for every }w\ne v\}. E v = { Z v ∈ A , Z w ∈ A c for every w = v } .
The events E v E_v E v are disjoint, and ( N − 1 ) + ≥ 0 (N-1)_+\ge0 ( N − 1 ) + ≥ 0 , so
D H ( U 1 ) = E ( N − 1 ) + ≥ ∑ v ∈ V ( H ) E [ ( N − 1 ) + 1 E v ] . D_H(U_1)=\mathbb{E}(N-1)_+\ge\sum_{v\in V(H)}\mathbb{E}\left[(N-1)_+\mathbf{1}_{E_v}\right]. D H ( U 1 ) = E ( N − 1 ) + ≥ v ∈ V ( H ) ∑ E [ ( N − 1 ) + 1 E v ] .
On E v E_v E v , only edges incident to v v v can be selected. Conditional on Z v = x ∈ A Z_v=x\in A Z v = x ∈ A and all other positions lying in A c A^c A c , N N N is binomial with parameters d H ( v ) d_H(v) d H ( v ) and ( 1 − s ) − 1 ∫ A c U ( x , y ) d y (1-s)^{-1}\int_{A^c}U(x,y)\,dy ( 1 − s ) − 1 ∫ A c U ( x , y ) d y . Since the other positions lie in A c A^c A c with probability ( 1 − s ) v ( H ) − 1 (1-s)^{v(H)-1} ( 1 − s ) v ( H ) − 1 , (4.37) and (4.35) give
D H ( U 1 ) ≥ ( 1 − s ) v ( H ) − 1 ∑ v ∈ V ( H ) ( d H ( v ) − 1 ) + ∫ A ( 1 1 − s ∫ A c U ( x , y ) d y ) 2 d x ≥ ( 1 − s ) v ( H ) − 1 4 ( ∑ v ∈ V ( H ) ( d H ( v ) − 1 ) + ) ∫ A d U ( x ) 2 d x ≥ 1 8 ∫ A d U ( x ) 2 d x ≥ δ 8 ∫ A d U ( x ) d x ≥ δ 16 q 1 . \begin{aligned}
D_H(U_1)\ge(1-s)^{v(H)-1}\sum_{v\in V(H)}(d_H(v)-1)_+\int_A\left(\frac{1}{1-s}\int_{A^c}U(x,y)\,dy\right)^2dx \\
&\ge\frac{(1-s)^{v(H)-1}}{4}\left(\sum_{v\in V(H)}(d_H(v)-1)_+\right)\int_A d_U(x)^2\,dx \\
&\ge\frac{1}{8}\int_A d_U(x)^2\,dx\ge\frac{\delta}{8}\int_A d_U(x)\,dx\ge\frac{\delta}{16}q_1.
\end{aligned} D H ( U 1 ) ≥ ( 1 − s ) v ( H ) − 1 v ∈ V ( H ) ∑ ( d H ( v ) − 1 ) + ∫ A ( 1 − s 1 ∫ A c U ( x , y ) d y ) 2 d x ≥ 4 ( 1 − s ) v ( H ) − 1 v ∈ V ( H ) ∑ ( d H ( v ) − 1 ) + ∫ A d U ( x ) 2 d x ≥ 8 1 ∫ A d U ( x ) 2 d x ≥ 8 δ ∫ A d U ( x ) d x ≥ 16 δ q 1 .
Here the degree assumption gives ∑ v ( d H ( v ) − 1 ) + ≥ 1 \sum_v(d_H(v)-1)_+\ge1 ∑ v ( d H ( v ) − 1 ) + ≥ 1 , and ( 1 − s ) v ( H ) − 1 ≥ 1 − ( v ( H ) − 1 ) s ≥ 1 / 2 (1-s)^{v(H)-1}\ge1-(v(H)-1)s\ge1/2 ( 1 − s ) v ( H ) − 1 ≥ 1 − ( v ( H ) − 1 ) s ≥ 1/2 . Since q ≤ δ / ( 32 e ( H ) 2 ) ≤ 1 / ( 2 e ( H ) ) q\le\delta/(32e(H)^2)\le1/(2e(H)) q ≤ δ / ( 32 e ( H ) 2 ) ≤ 1/ ( 2 e ( H )) , superadditivity and Lemma 4.14 give
t ( H , 1 − U ) ≥ t ( H , 1 − U 2 ) + D H ( U 1 ) − e ( H ) q 1 ≥ Φ H ( 1 − q 2 ) + D H ( U 1 ) − e ( H ) q 1 ≥ Φ H ( 1 − q ) + D H ( U 1 ) − 2 e ( H ) 2 q q 1 ≥ Φ H ( 1 − q ) + q 1 ( δ 16 − 2 e ( H ) 2 q ) ≥ Φ H ( 1 − q ) . \begin{aligned}
t(H,1-U)&\ge t(H,1-U_2)+D_H(U_1)-e(H)q_1\\
&\ge\Phi_H(1-q_2)+D_H(U_1)-e(H)q_1\\
&\ge\Phi_H(1-q)+D_H(U_1)-2e(H)^2qq_1\\
&\ge\Phi_H(1-q)+q_1\left(\frac{\delta}{16}-2e(H)^2q\right)\\
&\ge\Phi_H(1-q).
\end{aligned} t ( H , 1 − U ) ≥ t ( H , 1 − U 2 ) + D H ( U 1 ) − e ( H ) q 1 ≥ Φ H ( 1 − q 2 ) + D H ( U 1 ) − e ( H ) q 1 ≥ Φ H ( 1 − q ) + D H ( U 1 ) − 2 e ( H ) 2 q q 1 ≥ Φ H ( 1 − q ) + q 1 ( 16 δ − 2 e ( H ) 2 q ) ≥ Φ H ( 1 − q ) .
If 16 e ( H ) 2 δ ≤ 1 16e(H)^2\delta\le1 16 e ( H ) 2 δ ≤ 1 , then δ 2 / 2 ≤ δ / ( 32 e ( H ) 2 ) \delta^2/2\le\delta/(32e(H)^2) δ 2 /2 ≤ δ / ( 32 e ( H ) 2 ) , so q < δ 2 / 2 q<\delta^2/2 q < δ 2 /2 suffices.
The obstruction for even girth
Lemma 4.16. Suppose H H H has girth g g g . If A ⊆ E ( H ) A\subseteq E(H) A ⊆ E ( H ) and H A H_A H A contains a cycle, then r ( A ) ≥ g − 1 r(A)\ge g-1 r ( A ) ≥ g − 1 . Equality holds if and only if deleting the isolated vertices from H A H_A H A leaves a single g g g -cycle.
Proof. A component of H A H_A H A containing a cycle has at least g g g vertices. A spanning forest of H A H_A H A therefore has at least g − 1 g-1 g − 1 edges, so r ( A ) ≥ g − 1 r(A)\ge g-1 r ( A ) ≥ g − 1 . If r ( A ) = g − 1 r(A)=g-1 r ( A ) = g − 1 , this component has exactly g g g vertices and all other vertices are isolated. Its cycle uses all g g g vertices, and an additional edge would be a chord creating a shorter cycle. The converse is immediate.
Proposition 4.17. If H H H has girth g g g , then
Φ H ( 1 − q ) − ( 1 − q ) e ( H ) = ( − 1 ) g c g ( H ) q g − 1 + O H ( q g ) as q ↓ 0. (54) \Phi_H(1-q)-(1-q)^{e(H)}=(-1)^g c_g(H)q^{g-1}+O_H(q^g)\quad\text{as }q\downarrow0. \tag*{(54)} Φ H ( 1 − q ) − ( 1 − q ) e ( H ) = ( − 1 ) g c g ( H ) q g − 1 + O H ( q g ) as q ↓ 0. (54) If g g g is even, the constant graphon W ≡ 1 − 1 / k W\equiv1-1/k W ≡ 1 − 1/ k violates (4) for every sufficiently large integer k k k .
Proof. Subtracting the binomial expansion of ( 1 − q ) e ( H ) (1-q)^{e(H)} ( 1 − q ) e ( H ) from (18) gives
Φ H ( 1 − q ) − ( 1 − q ) e ( H ) = ∑ A ⊆ E ( H ) ( − 1 ) ∣ A ∣ ( q r ( A ) − q ∣ A ∣ ) . \Phi_H(1-q)-(1-q)^{e(H)}=\sum_{A\subseteq E(H)}(-1)^{|A|}\left(q^{r(A)}-q^{|A|}\right). Φ H ( 1 − q ) − ( 1 − q ) e ( H ) = A ⊆ E ( H ) ∑ ( − 1 ) ∣ A ∣ ( q r ( A ) − q ∣ A ∣ ) .
If H A H_A H A is a forest, the summand is zero. Each of the c g ( H ) c_g(H) c g ( H ) shortest cycles contributes ( − 1 ) g ( q g − 1 − q g ) (-1)^g(q^{g-1}-q^g) ( − 1 ) g ( q g − 1 − q g ) . By Lemma 4.16, every remaining edge set A A A containing a cycle satisfies r ( A ) ≥ g r(A)\ge g r ( A ) ≥ g , proving (54) .
For even g g g , the leading coefficient is positive, so Φ H ( 1 − q ) > ( 1 − q ) e ( H ) \Phi_H(1-q)>(1-q)^{e(H)} Φ H ( 1 − q ) > ( 1 − q ) e ( H ) for all sufficiently small q > 0 q>0 q > 0 . For the constant graphon W ≡ 1 − q W\equiv1-q W ≡ 1 − q ,
t ( H , W ) = ( 1 − q ) e ( H ) < Φ H ( 1 − q ) . t(H,W)=(1-q)^{e(H)}<\Phi_H(1-q). t ( H , W ) = ( 1 − q ) e ( H ) < Φ H ( 1 − q ) .
Taking q = 1 / k q=1/k q = 1/ k and using (3) shows that the constant graphon W ≡ 1 − 1 / k W\equiv1-1/k W ≡ 1 − 1/ k violates (4) for every sufficiently large integer k k k .
Proof of the characterisation
Proof of Theorem 1.6. (iii)⇒ \Rightarrow ⇒ (ii). Suppose the girth of H H H is odd, and set δ = ( 6 v ( H ) 6 ) − 1 \delta=(6v(H)^6)^{-1} δ = ( 6 v ( H ) 6 ) − 1 . By Proposition 4.12, every graphon V V V with Δ V ≤ δ \Delta_V\le\delta Δ V ≤ δ satisfies t ( H , 1 − V ) ≥ Φ H ( 1 − t ( K 2 , V ) ) t(H,1-V)\ge\Phi_H(1-t(K_2,V)) t ( H , 1 − V ) ≥ Φ H ( 1 − t ( K 2 , V )) . The graph H H H has a vertex of degree at least two, δ ≤ 1 / v ( H ) \delta\le1/v(H) δ ≤ 1/ v ( H ) , and
16 e ( H ) 2 δ ≤ 16 ( v ( H ) 2 2 ) 2 1 6 v ( H ) 6 = 2 3 v ( H ) 2 ≤ 1. 16e(H)^2\delta\le16\left(\frac{v(H)^2}{2}\right)^2\frac{1}{6v(H)^6}=\frac{2}{3v(H)^2}\le1. 16 e ( H ) 2 δ ≤ 16 ( 2 v ( H ) 2 ) 2 6 v ( H ) 6 1 = 3 v ( H ) 2 2 ≤ 1.
Thus Proposition 4.15 gives t ( H , 1 − U ) ≥ Φ H ( 1 − q ) t(H,1-U)\ge\Phi_H(1-q) t ( H , 1 − U ) ≥ Φ H ( 1 − q ) whenever
q < δ 2 2 = 1 72 v ( H ) 12 . q<\frac{\delta^2}{2}=\frac{1}{72v(H)^{12}}. q < 2 δ 2 = 72 v ( H ) 12 1 .
Taking U = 1 − W U=1-W U = 1 − W proves (ii) with the threshold (7) .
(ii)⇒ \Rightarrow ⇒ (i). For every sufficiently large integer k k k and every graphon W W W of edge density 1 − 1 / k 1-1/k 1 − 1/ k ,
t ( H , W ) ≥ Φ H ( 1 − 1 / k ) = t ( H , T k ) , t(H,W)\ge\Phi_H(1-1/k)=t(H,T_k), t ( H , W ) ≥ Φ H ( 1 − 1/ k ) = t ( H , T k ) ,
where the equality is (3) . With the threshold in (7) , it suffices that k > 72 v ( H ) 12 k>72v(H)^{12} k > 72 v ( H ) 12 .
(i)⇒ \Rightarrow ⇒ (iii). Since H H H is nonbipartite, it contains a cycle. If its girth were even, Proposition 4.17 would contradict (i). Hence its girth is odd.
Graphs on at most six vertices
The classification in Theorem 1.7 is obtained by enumerating the 117 graphs and proving the bound or constructing a counterexample for each. The accompanying Lean development contains the complete catalogue, with a formal proof for every entry. The accompanying notes give the graph-specific inequalities and certificate constructions.
For the positive cases, the general results of Sections 2 and 3 are supplemented by estimates for individual graphs. These estimates express homomorphism densities as integrals with one or more vertex positions fixed, then apply the weighted triangle inequality, moment bounds, and Cauchy–Schwarz. The remaining cases follow from sum-of-squares identities. For the negative cases, finite step graphons give strict counterexamples. The 23 violating graphs are shown in Figure 2 .
Density ranges for the violating graphs
Of the 23 graphs in Figure 2 , all except graph 129 have odd girth and hence eventually satisfy the Goodman-type lower bound by Theorem 1.6 . Graph 129 has even girth, so the bound fails for all p < 1 p < 1 p < 1 sufficiently close to 1. Thus there is no p 0 < 1 p_0 < 1 p 0 < 1 such that the bound holds at every density p ∈ ( p 0 , 1 ) p \in(p_0,1) p ∈ ( p 0 , 1 ) for this graph. Table 1 gives density ranges on which the bound holds, together with results on the optimality of T k T_k T k .
Table 1. Density ranges and Turán optimality for the 23 graphs that violate the Goodman-type lower bound.
For the 94 graphs satisfying (1.2), T k T_k T k is optimal for every integer k ≥ χ ( H ) k \ge\chi(H) k ≥ χ ( H ) . The first two rows of Table 1 give six further graphs with this property.
Write H 173 H_{173} H 173 for graph 173. At edge density 3 / 4 3/4 3/4 , we have
14056671 200000000 ≤ inf W a graphon t ( K 2 , W ) = 3 / 4 t ( H 173 , W ) ≤ 9 128 = t ( H 173 , T 4 ) . (55) \frac{14056671}{200000000} \le\inf_{\substack{W\ \text{a graphon}\\ t(K_2,W)=3/4}} t(H_{173},W) \le\frac{9}{128} = t(H_{173},T_4). \tag*{(55)} 200000000 14056671 ≤ W a graphon t ( K 2 , W ) = 3/4 inf t ( H 173 , W ) ≤ 128 9 = t ( H 173 , T 4 ) . (55)
The two bounds differ by 5829 / 200000000 5829/200000000 5829/200000000 . Whether T 4 T_4 T 4 attains the minimum remains open.
Constructions of counterexamples
In this subsection, we construct step graphons that violate the Goodman-type lower bound for each of the 23 graphs in Figure 2 .
For graphons U U U and V V V , their tensor product is the graphon on the product probability space [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 given by
( U ⊗ V ) ( ( x , x ′ ) , ( y , y ′ ) ) = U ( x , y ) V ( x ′ , y ′ ) . (U \otimes V)((x,x'),(y,y')) = U(x,y)V(x',y'). ( U ⊗ V ) (( x , x ′ ) , ( y , y ′ )) = U ( x , y ) V ( x ′ , y ′ ) .
Homomorphism densities are multiplicative under this operation:
t ( H , U ⊗ V ) = t ( H , U ) t ( H , V ) . t(H,U \otimes V) = t(H,U)t(H,V). t ( H , U ⊗ V ) = t ( H , U ) t ( H , V ) .
For the graphs 129, 149, 170, 173, 186, 189, 197, 198, 204, the graphon T 2 k − 1 ⊗ T 2 k T_{2k-1} \otimes T_{2k} T 2 k − 1 ⊗ T 2 k , whose edge density is
( 1 − 1 2 k − 1 ) ( 1 − 1 2 k ) = 1 − 1 k , \left(1-\frac{1}{2k-1}\right)\left(1-\frac{1}{2k}\right)=1-\frac{1}{k}, ( 1 − 2 k − 1 1 ) ( 1 − 2 k 1 ) = 1 − k 1 ,
satisfies t ( H , T 2 k − 1 ⊗ T 2 k ) < t ( H , T k ) t(H,T_{2k-1} \otimes T_{2k}) < t(H,T_k) t ( H , T 2 k − 1 ⊗ T 2 k ) < t ( H , T k ) for each k k k listed as suboptimal in Table 1 . At k = 3 k = 3 k = 3 , the same construction also gives a counterexample for graph 190.
For graphs 182 and 184, take W = T 4 ⊗ T 4 W = T_4 \otimes T_4 W = T 4 ⊗ T 4 . Then
t ( K 2 , W ) = 9 16 , t ( H , W ) = 81 65536 < 351 262144 = Φ H ( 9 16 ) . t(K_2,W) = \frac{9}{16}, \qquad t(H,W) = \frac{81}{65536} < \frac{351}{262144} = \Phi_H\left(\frac{9}{16}\right). t ( K 2 , W ) = 16 9 , t ( H , W ) = 65536 81 < 262144 351 = Φ H ( 16 9 ) .
For graph 129, the constant graphon W ≡ 1 − 1 / k W \equiv1 - 1/k W ≡ 1 − 1/ k gives
t ( H , T k ) − t ( H , W ) = ( k − 1 ) ( k 3 − 5 k 2 + 6 k − 1 ) k 7 > 0 ( k ≥ 4 ) . t(H,T_k) - t(H,W) = \frac{(k-1)(k^3 - 5k^2 + 6k - 1)}{k^7} > 0 \qquad(k \ge4). t ( H , T k ) − t ( H , W ) = k 7 ( k − 1 ) ( k 3 − 5 k 2 + 6 k − 1 ) > 0 ( k ≥ 4 ) .
Indeed, substituting k = u + 4 k = u + 4 k = u + 4 turns the cubic factor into u 3 + 7 u 2 + 14 u + 7 u^3 + 7u^2 + 14u + 7 u 3 + 7 u 2 + 14 u + 7 .
For graphs 166 and 172, partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into four equal parts A 1 A_1 A 1 , A 2 A_2 A 2 , A 3 A_3 A 3 , A 4 A_4 A 4 . Define W W W to be constant on each A i × A j A_i \times A_j A i × A j , with value given by the ( i , j ) (i,j) ( i , j ) -entry of the following matrix:
( 0 1 4 1 1 1 4 0 1 1 1 1 0 1 4 1 1 1 4 0 ) . \begin{pmatrix}
0 & \frac{1}{4} & 1 & 1 \\
\frac{1}{4} & 0 & 1 & 1 \\
1 & 1 & 0 & \frac{1}{4} \\
1 & 1 & \frac{1}{4} & 0
\end{pmatrix}. 0 4 1 1 1 4 1 0 1 1 1 1 0 4 1 1 1 4 1 0 .
Its edge density is 9 / 16 9/16 9/16 , and
t ( H , W ) = { 465 / 262144 , for graph 166, 3 / 2048 , for graph 172, < 477 262144 = Φ H ( 9 16 ) . t(H,W) =
\begin{cases}
465/262144, & \text{for graph 166,}\\
3/2048, & \text{for graph 172,}
\end{cases}
< \frac{477}{262144} = \Phi_H\left(\frac{9}{16}\right). t ( H , W ) = { 465/262144 , 3/2048 , for graph 166, for graph 172, < 262144 477 = Φ H ( 16 9 ) .
For graph 206, partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into three equal parts A 1 A_1 A 1 , A 2 A_2 A 2 , A 3 A_3 A 3 . Define W W W to be constant on each A i × A j A_i \times A_j A i × A j , with value given by the ( i , j ) (i,j) ( i , j ) -entry of
( 1 4 1 1 1 0 1 1 1 0 ) . \begin{pmatrix}
\frac{1}{4} & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{pmatrix}. 4 1 1 1 1 0 1 1 1 0 .
Then
t ( K 2 , W ) = 25 36 , t ( H , W ) = 77731841 48922361856 < 16975 10077696 = Φ H ( 25 36 ) . t(K_2,W)=\frac{25}{36},\qquad t(H,W)=\frac{77731841}{48922361856}<\frac{16975}{10077696}=\Phi_H\left(\frac{25}{36}\right). t ( K 2 , W ) = 36 25 , t ( H , W ) = 48922361856 77731841 < 10077696 16975 = Φ H ( 36 25 ) .
For graph 190 at k = 4 k=4 k = 4 , partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into four equal parts A 1 , A 2 , A 3 , A 4 A_1,A_2,A_3,A_4 A 1 , A 2 , A 3 , A 4 . For 0 ≤ ε ≤ 1 0\leq\varepsilon\leq1 0 ≤ ε ≤ 1 , define W ε W_\varepsilon W ε to be constant on each A i × A j A_i\times A_j A i × A j , with value given by the ( i , j ) (i,j) ( i , j ) -entry of the following matrix:
( ε 1 − ε / 3 1 − ε / 3 1 − ε / 3 1 − ε / 3 ε 1 − ε / 3 1 − ε / 3 1 − ε / 3 1 − ε / 3 ε 1 − ε / 3 1 − ε / 3 1 − ε / 3 1 − ε / 3 ε ) . \begin{pmatrix}
\varepsilon& 1-\varepsilon/3 & 1-\varepsilon/3 & 1-\varepsilon/3\\
1-\varepsilon/3 & \varepsilon& 1-\varepsilon/3 & 1-\varepsilon/3\\
1-\varepsilon/3 & 1-\varepsilon/3 & \varepsilon& 1-\varepsilon/3\\
1-\varepsilon/3 & 1-\varepsilon/3 & 1-\varepsilon/3 & \varepsilon
\end{pmatrix}. ε 1 − ε /3 1 − ε /3 1 − ε /3 1 − ε /3 ε 1 − ε /3 1 − ε /3 1 − ε /3 1 − ε /3 ε 1 − ε /3 1 − ε /3 1 − ε /3 1 − ε /3 ε .
The edge density remains 3 / 4 3/4 3/4 , while d d ε t ( H , W ε ) ∣ ε = 0 = − 1 / 256 \left.\frac{\mathrm{d}}{\mathrm{d}\varepsilon}t(H,W_\varepsilon)\right|_{\varepsilon=0}=-1/256 d ε d t ( H , W ε ) ε = 0 = − 1/256 , so sufficiently small positive ε \varepsilon ε decreases the H H H -density.
For graphs 48, 50, 140, 141, 143, 158 at k = 3 k=3 k = 3 , use the following four-part graphon. Partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into a set A 1 A_1 A 1 of size δ = 1 / 2000 \delta=1/2000 δ = 1/2000 and sets A 2 , A 3 , A 4 A_2,A_3,A_4 A 2 , A 3 , A 4 of size ( 1 − δ ) / 3 (1-\delta)/3 ( 1 − δ ) /3 each. Define W W W to be constant on each product of two parts, with values given by the following matrix:
( 0 1 23 50 23 50 1 ε 1 1 23 50 1 ε 1 23 50 1 1 ε ) . \begin{pmatrix}
0 & 1 & \frac{23}{50} & \frac{23}{50}\\
1 & \varepsilon& 1 & 1\\
\frac{23}{50} & 1 & \varepsilon& 1\\
\frac{23}{50} & 1 & 1 & \varepsilon
\end{pmatrix}. 0 1 50 23 50 23 1 ε 1 1 50 23 1 ε 1 50 23 1 1 ε .
The choice ε = 8046 / 99900025 \varepsilon=8046/99900025 ε = 8046/99900025 makes the edge density exactly 2 / 3 2/3 2/3 . For each of the six graphs, t ( H , W ) < t ( H , T 3 ) t(H,W)<t(H,T_3) t ( H , W ) < t ( H , T 3 ) ; the gaps t ( H , T 3 ) − t ( H , W ) t(H,T_3)-t(H,W) t ( H , T 3 ) − t ( H , W ) for graphs 48, 50, 140, 141, 143, 158 are approximately 4.10 × 10 − 7 4.10\times10^{-7} 4.10 × 1 0 − 7 , 2.24 × 10 − 8 2.24\times10^{-8} 2.24 × 1 0 − 8 , 3.30 × 10 − 7 3.30\times10^{-7} 3.30 × 1 0 − 7 , 1.16 × 10 − 7 1.16\times10^{-7} 1.16 × 1 0 − 7 , 8.00 × 10 − 8 8.00\times10^{-8} 8.00 × 1 0 − 8 , and 1.08 × 10 − 7 1.08\times10^{-7} 1.08 × 1 0 − 7 , respectively.
For graph 159, a three-part graphon gives a counterexample at k = 3 k=3 k = 3 . Partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into sets A 1 , A 2 , A 3 A_1,A_2,A_3 A 1 , A 2 , A 3 of sizes 13 / 40 13/40 13/40 , 7 / 20 7/20 7/20 , 13 / 40 13/40 13/40 , respectively. Define W W W to be constant on each A i × A j A_i\times A_j A i × A j , with value given by the ( i , j ) (i,j) ( i , j ) -entry of the following matrix:
( 0 1 49 50 1 557 14700 1 49 50 1 0 ) . \begin{pmatrix}
0 & 1 & \frac{49}{50}\\
1 & \frac{557}{14700} & 1\\
\frac{49}{50} & 1 & 0
\end{pmatrix}. 0 1 50 49 1 14700 557 1 50 49 1 0 .
Its edge density is exactly 2 / 3 2/3 2/3 , and t ( H , W ) < t ( H , T 3 ) = 4 / 243 t(H,W)<t(H,T_3)=4/243 t ( H , W ) < t ( H , T 3 ) = 4/243 , with t ( H , T 3 ) − t ( H , W ) ≈ 1.744 × 10 − 6 t(H,T_3)-t(H,W)\approx1.744\times10^{-6} t ( H , T 3 ) − t ( H , W ) ≈ 1.744 × 1 0 − 6 .
For graph 152, let 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 and partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into sets A 1 , A 2 , B , S 1 , S 2 A_1,A_2,B,S_1,S_2 A 1 , A 2 , B , S 1 , S 2 of sizes ( 1 2 − ε ) 624 625 \left(\frac{1}{2}-\varepsilon\right)\frac{624}{625} ( 2 1 − ε ) 625 624 , ( 1 2 − ε ) 1 625 \left(\frac{1}{2}-\varepsilon\right)\frac{1}{625} ( 2 1 − ε ) 625 1 , 1 2 \frac{1}{2} 2 1 , 1 10 \frac{1}{10} 10 1 , 9 ε 10 \frac{9\varepsilon}{10} 10 9 ε .
Define W ε W_\varepsilon W ε to be constant on each product of two parts, with values given by the following matrix, whose rows and columns are ordered as A 1 , A 2 , B , S 1 , S 2 A_1,A_2,B,S_1,S_2 A 1 , A 2 , B , S 1 , S 2 :
( 0 0 1 1 0 0 0 1 0 1 1 1 0 1 16 1 1 0 1 16 0 0 0 1 1 0 0 ) . \begin{pmatrix}
0 & 0 & 1 & 1 & 0\\
0 & 0 & 1 & 0 & 1\\
1 & 1 & 0 & \frac{1}{16} & 1\\
1 & 0 & \frac{1}{16} & 0 & 0\\
0 & 1 & 1 & 0 & 0
\end{pmatrix}. 0 0 1 1 0 0 0 1 0 1 1 1 0 16 1 1 1 0 16 1 0 0 0 1 1 0 0 .
Let p ε = t ( K 2 , W ε ) p_\varepsilon=t(K_2,W_\varepsilon) p ε = t ( K 2 , W ε ) . Summing over the partition classes gives
p ε = 1 2 + 753 100000 ε − 633 3125 ε 2 , p_\varepsilon=\frac{1}{2}+\frac{753}{100000}\varepsilon-\frac{633}{3125}\varepsilon^2, p ε = 2 1 + 100000 753 ε − 3125 633 ε 2 ,
t ( H , W ε ) = 2224881 80000000000 ε 2 ( 1 − 2 ε ) 2 . t(H,W_\varepsilon)=\frac{2224881}{80000000000}\varepsilon^2(1-2\varepsilon)^2. t ( H , W ε ) = 80000000000 2224881 ε 2 ( 1 − 2 ε ) 2 .
For this graph, the Goodman-type bound (1.2) would require
t ( H , W ε ) ≥ p ε ( 2 p ε − 1 ) 2 ( 3 p ε 2 − 3 p ε + 1 ) t(H,W_\varepsilon) \ge p_\varepsilon(2p_\varepsilon-1)^2(3p_\varepsilon^2-3p_\varepsilon+1) t ( H , W ε ) ≥ p ε ( 2 p ε − 1 ) 2 ( 3 p ε 2 − 3 p ε + 1 )
whenever p ε > 1 2 p_\varepsilon>\frac{1}{2} p ε > 2 1 .
The formula for p ε p_\varepsilon p ε shows that p ε > 1 / 2 p_\varepsilon>1/2 p ε > 1/2 for all sufficiently small positive ε \varepsilon ε . Moreover,
lim ε → 0 p ε ( 2 p ε − 1 ) 2 ( 3 p ε 2 − 3 p ε + 1 ) ε 2 = 1 2 ( 753 50000 ) 2 1 4 = 2268036 80000000000 > 2224881 80000000000 = lim ε → 0 t ( H , W ε ) ε 2 . \lim_{\varepsilon\to0}\frac{p_\varepsilon(2p_\varepsilon-1)^2(3p_\varepsilon^2-3p_\varepsilon+1)}{\varepsilon^2}
=\frac{1}{2}\left(\frac{753}{50000}\right)^2\frac{1}{4}
=\frac{2268036}{80000000000}
>\frac{2224881}{80000000000}
=\lim_{\varepsilon\to0}\frac{t(H,W_\varepsilon)}{\varepsilon^2}. ε → 0 lim ε 2 p ε ( 2 p ε − 1 ) 2 ( 3 p ε 2 − 3 p ε + 1 ) = 2 1 ( 50000 753 ) 2 4 1 = 80000000000 2268036 > 80000000000 2224881 = ε → 0 lim ε 2 t ( H , W ε ) .
Hence, for all sufficiently small positive ε \varepsilon ε ,
t ( H , W ε ) < p ε ( 2 p ε − 1 ) 2 ( 3 p ε 2 − 3 p ε + 1 ) , t(H,W_\varepsilon)<p_\varepsilon(2p_\varepsilon-1)^2(3p_\varepsilon^2-3p_\varepsilon+1), t ( H , W ε ) < p ε ( 2 p ε − 1 ) 2 ( 3 p ε 2 − 3 p ε + 1 ) ,
so W ε W_\varepsilon W ε is a counterexample to (1.2).
Concluding remarks
Theorems 1.1 and 1.3 establish the bound for two classes of chordal graphs. The following construction shows that attaching leaves to a clique can produce a chordal graph that violates the bound.
Proposition 6.1. Let L 20 L_{20} L 20 be obtained from a triangle by attaching twenty pendant leaves to each of its three vertices. Then L 20 L_{20} L 20 is a connected chordal graph with 63 vertices and 63 edges that does not satisfy the Goodman-type lower bound.
Proof. The polynomial Φ L 20 \Phi_{L_{20}} Φ L 20 is
Φ L 20 ( p ) = p 61 ( 2 p − 1 ) . \Phi_{L_{20}}(p)=p^{61}(2p-1). Φ L 20 ( p ) = p 61 ( 2 p − 1 ) .
Partition [ 0 , 1 ] [0,1] [ 0 , 1 ] into sets A A A , B B B of sizes 2 / 5 2/5 2/5 , 3 / 5 3/5 3/5 , and define a graphon W W W by
W ∣ A × A = 0 , W ∣ A × B = W ∣ B × A = 1 , W ∣ B × B = 1 9 . W|_{A\times A}=0,\qquad W|_{A\times B}=W|_{B\times A}=1,\qquad W|_{B\times B}=\frac{1}{9}. W ∣ A × A = 0 , W ∣ A × B = W ∣ B × A = 1 , W ∣ B × B = 9 1 .
Its degree function equals 3 / 5 3/5 3/5 on A A A and 7 / 15 7/15 7/15 on B B B , so its edge density is p = 13 / 25 > 1 / 2 p=13/25>1/2 p = 13/25 > 1/2 . A nonzero contribution to the triangle density has either one vertex in A A A or all three vertices in B B B . Integrating the leaves and summing these two contributions gives the exact inequality
t ( L 20 , W ) = 6 125 ( 49 375 ) 20 + 1 3375 ( 7 15 ) 60 < 1 25 ( 13 25 ) 61 = Φ L 20 ( 13 / 25 ) . t(L_{20},W)=\frac{6}{125}\left(\frac{49}{375}\right)^{20}+\frac{1}{3375}\left(\frac{7}{15}\right)^{60}<\frac{1}{25}\left(\frac{13}{25}\right)^{61}=\Phi_{L_{20}}(13/25). t ( L 20 , W ) = 125 6 ( 375 49 ) 20 + 3375 1 ( 15 7 ) 60 < 25 1 ( 25 13 ) 61 = Φ L 20 ( 13/25 ) .
Thus W W W violates the Goodman-type lower bound for L 20 L_{20} L 20 .
Problem 1 (Chordal classification). Characterise the connected nonbipartite chordal graphs that satisfy the Goodman-type lower bound. Can a necessary and sufficient condition be expressed in terms of their maximal cliques and the way those cliques intersect?
The graphon in the proof of Proposition 6.1 has edge density 13 / 25 13/25 13/25 , which is not a Turán density, so it does not rule out the optimality of T k T_k T k for L 20 L_{20} L 20 . We ask whether T k T_k T k is optimal for every graph in a larger class, which contains every chordal graph and every odd cycle.
Problem 2 (Graphs with no induced even cycle). Let H H H be a nonbipartite graph with no induced even cycle. Is T k T_k T k optimal for every integer k ≥ χ ( H ) k \ge\chi(H) k ≥ χ ( H ) ? Equivalently, does
t ( H , W ) ≥ P H ( k ) k v ( H ) t(H,W) \ge\frac{P_H(k)}{k^{v(H)}} t ( H , W ) ≥ k v ( H ) P H ( k ) hold for every integer k ≥ χ ( H ) k \ge\chi(H) k ≥ χ ( H ) and every graphon W W W with t ( K 2 , W ) = 1 − 1 / k t(K_2,W)=1-1/k t ( K 2 , W ) = 1 − 1/ k ?
A shortest cycle of such a graph is induced and hence odd, so Theorem 1.6 gives the optimality of T k T_k T k for all sufficiently large k k k .
The graphs of Theorem 1.7 also support this question. Each of the 23 graphs in Figure 2 contains an induced C 4 C_4 C 4 . Hence all 75 of the 117 graphs with no induced even cycle satisfy the Goodman-type lower bound.
We finally ask for the optimal exponent of v ( H ) v(H) v ( H ) in the density threshold of Theorem 1.6 . The following construction shows that every exponent below 4 is insufficient.
Proposition 6.2. For every sufficiently large odd integer n n n , there is an n n n -vertex graph H H H of girth 3 and chromatic number 3 such that the constant graphon W ≡ p W \equiv p W ≡ p , where
p = 1 − 128 ( n − 1 ) 4 , p=1-\frac{128}{(n-1)^4}, p = 1 − ( n − 1 ) 4 128 ,
Proof. Let r = ( n − 1 ) / 2 r=(n-1)/2 r = ( n − 1 ) /2 and let H H H be the graph obtained from K r , r K_{r,r} K r , r by adding one vertex adjacent to both ends of a chosen edge. Denote this graph by J r J_r J r . The new vertex completes a triangle and can receive a third colour in a 2-colouring of K r , r K_{r,r} K r , r . Thus J r J_r J r has girth 3 and chromatic number 3. Moreover, v ( J r ) = 2 r + 1 v(J_r)=2r+1 v ( J r ) = 2 r + 1 , e ( J r ) = r 2 + 2 e(J_r)=r^2+2 e ( J r ) = r 2 + 2 , and P J r ( x ) = ( x − 2 ) P K r , r ( x ) P_{J_r}(x)=(x-2)P_{K_{r,r}}(x) P J r ( x ) = ( x − 2 ) P K r , r ( x ) . Let α 1 , … , α 2 r \alpha_1,\ldots,\alpha_{2r} α 1 , … , α 2 r be the roots of P K r , r P_{K_{r,r}} P K r , r . Sokal’s bound [17 ] states that every root of the chromatic polynomial of a graph has modulus at most eight times its maximum degree. Since K r , r K_{r,r} K r , r has maximum degree r r r , we have ∣ α i ∣ ≤ 8 r |\alpha_i|\le8r ∣ α i ∣ ≤ 8 r for every i i i . Since P K r , r P_{K_{r,r}} P K r , r is monic of degree 2 r 2r 2 r ,
Φ K r , r ( 1 − q ) = q 2 r P K r , r ( 1 / q ) = ∏ i = 1 2 r ( 1 − α i q ) . \Phi_{K_{r,r}}(1-q)=q^{2r}P_{K_{r,r}}(1/q)=\prod_{i=1}^{2r}(1-\alpha_iq). Φ K r , r ( 1 − q ) = q 2 r P K r , r ( 1/ q ) = i = 1 ∏ 2 r ( 1 − α i q ) .
For 0 < q ≤ 1 / ( 16 r ) 0<q\le1/(16r) 0 < q ≤ 1/ ( 16 r ) , we have ∣ α i q ∣ ≤ 1 / 2 |\alpha_iq|\le1/2 ∣ α i q ∣ ≤ 1/2 , so the convergent series log ( 1 − z ) = − ∑ j ≥ 1 z j / j \log(1-z)=-\sum_{j\ge1}z^j/j log ( 1 − z ) = − ∑ j ≥ 1 z j / j gives
log Φ K r , r ( 1 − q ) ( 1 − q ) r 2 = ∑ i = 1 2 r log ( 1 − α i q ) − r 2 log ( 1 − q ) = ∑ j ≥ 1 r 2 − ∑ i = 1 2 r α i j j q j = ( r 2 − ∑ i = 1 2 r α i ) q + 1 2 ( r 2 − ∑ i = 1 2 r α i 2 ) q 2 \begin{aligned}
\log\frac{\Phi_{K_{r,r}}(1-q)}{(1-q)^{r^2}}
=\sum_{i=1}^{2r}\log(1-\alpha_iq)-r^2\log(1-q) \\
&=\sum_{j\ge1}\frac{r^2-\sum_{i=1}^{2r}\alpha_i^j}{j}q^j \\
&=\left(r^2-\sum_{i=1}^{2r}\alpha_i\right)q+\frac{1}{2}\left(r^2-\sum_{i=1}^{2r}\alpha_i^2\right)q^2
\end{aligned} log ( 1 − q ) r 2 Φ K r , r ( 1 − q ) = i = 1 ∑ 2 r log ( 1 − α i q ) − r 2 log ( 1 − q ) = j ≥ 1 ∑ j r 2 − ∑ i = 1 2 r α i j q j = ( r 2 − i = 1 ∑ 2 r α i ) q + 2 1 ( r 2 − i = 1 ∑ 2 r α i 2 ) q 2
+ 1 3 ( r 2 − ∑ i = 1 2 r α i 3 ) q 3 + O ( r 5 q 4 ) . \qquad+\frac{1}{3}\left(r^2-\sum_{i=1}^{2r}\alpha_i^3\right)q^3+O(r^5q^4). + 3 1 ( r 2 − i = 1 ∑ 2 r α i 3 ) q 3 + O ( r 5 q 4 ) .
Since K r , r K_{r,r} K r , r has r 2 r^2 r 2 edges and no triangles, (4.2) and Vieta’s formulas give
∑ i = 1 2 r α i = ∑ A ⊆ E ( K r , r ) ∣ A ∣ = 1 1 = r 2 , ∑ 1 ≤ i < j ≤ 2 r α i α j = ∑ A ⊆ E ( K r , r ) ∣ A ∣ = 2 1 = ( r 2 2 ) . (56) \sum_{i=1}^{2r}\alpha_i=\sum_{\substack{A\subseteq E(K_{r,r})\\|A|=1}}1=r^2,\qquad
\sum_{1\le i<j\le2r}\alpha_i\alpha_j=\sum_{\substack{A\subseteq E(K_{r,r})\\|A|=2}}1=\binom{r^2}{2}. \tag*{(56)} i = 1 ∑ 2 r α i = A ⊆ E ( K r , r ) ∣ A ∣ = 1 ∑ 1 = r 2 , 1 ≤ i < j ≤ 2 r ∑ α i α j = A ⊆ E ( K r , r ) ∣ A ∣ = 2 ∑ 1 = ( 2 r 2 ) . (56)
Hence
∑ i = 1 2 r α i 2 = ( ∑ i = 1 2 r α i ) 2 − 2 ∑ 1 ≤ i < j ≤ 2 r α i α j = r 4 − 2 ( r 2 2 ) = r 2 . \sum_{i=1}^{2r}\alpha_i^2=\left(\sum_{i=1}^{2r}\alpha_i\right)^2-2\sum_{1\le i<j\le2r}\alpha_i\alpha_j=r^4-2\binom{r^2}{2}=r^2. i = 1 ∑ 2 r α i 2 = ( i = 1 ∑ 2 r α i ) 2 − 2 1 ≤ i < j ≤ 2 r ∑ α i α j = r 4 − 2 ( 2 r 2 ) = r 2 .
Thus the terms with j = 1 j=1 j = 1 and j = 2 j=2 j = 2 are zero.
For the cubic term, the edge subsets contributing to the coefficient of q 3 q^3 q 3 in (18) are precisely the three-edge forests and the four-cycles, with signs − 1 -1 − 1 and + 1 +1 + 1 , respectively. Every three-edge subset of E ( K r , r ) E(K_{r,r}) E ( K r , r ) is a forest. Each four-cycle is obtained by choosing two vertices from each part, giving ( r 2 ) 2 \binom{r}{2}^2 ( 2 r ) 2 choices. Vieta’s formulas therefore give
∑ 1 ≤ i < j < k ≤ 2 r α i α j α k = ∑ A ⊆ E ( K r , r ) ∣ A ∣ = 3 1 − ( r 2 ) 2 = ( r 2 3 ) − ( r 2 ) 2 . \sum_{1\le i<j<k\le2r}\alpha_i\alpha_j\alpha_k
=\sum_{\substack{A\subseteq E(K_{r,r})\\ |A|=3}}1-\binom{r}{2}^2
=\binom{r^2}{3}-\binom{r}{2}^2. 1 ≤ i < j < k ≤ 2 r ∑ α i α j α k = A ⊆ E ( K r , r ) ∣ A ∣ = 3 ∑ 1 − ( 2 r ) 2 = ( 3 r 2 ) − ( 2 r ) 2 .
It follows that
∑ i = 1 2 r α i 3 = ( ∑ i α i ) 3 − 3 ( ∑ i α i ) ( ∑ i < j α i α j ) + 3 ∑ i < j < k α i α j α k = r 6 − 3 r 2 ( r 2 2 ) + 3 ( ( r 2 3 ) − ( r 2 ) 2 ) = r 2 − 3 ( r 2 ) 2 . \begin{aligned}
\sum_{i=1}^{2r}\alpha_i^3
=\left(\sum_i\alpha_i\right)^3-3\left(\sum_i\alpha_i\right)\left(\sum_{i<j}\alpha_i\alpha_j\right)+3\sum_{i<j<k}\alpha_i\alpha_j\alpha_k \\
&=r^6-3r^2\binom{r^2}{2}+3\left(\binom{r^2}{3}-\binom{r}{2}^2\right) \\
&=r^2-3\binom{r}{2}^2.
\end{aligned} i = 1 ∑ 2 r α i 3 = ( i ∑ α i ) 3 − 3 ( i ∑ α i ) ( i < j ∑ α i α j ) + 3 i < j < k ∑ α i α j α k = r 6 − 3 r 2 ( 2 r 2 ) + 3 ( ( 3 r 2 ) − ( 2 r ) 2 ) = r 2 − 3 ( 2 r ) 2 .
Thus the coefficient of q 3 q^3 q 3 in the logarithmic expansion is
r 2 − ∑ i = 1 2 r α i 3 3 = ( r 2 ) 2 . \frac{r^2-\sum_{i=1}^{2r}\alpha_i^3}{3}=\binom{r}{2}^2. 3 r 2 − ∑ i = 1 2 r α i 3 = ( 2 r ) 2 .
For the remaining terms, ∣ ∑ i α i j ∣ ≤ 2 r ( 8 r ) j \left|\sum_i\alpha_i^j\right|\le2r(8r)^j ∑ i α i j ≤ 2 r ( 8 r ) j gives
∣ ∑ j ≥ 4 r 2 − ∑ i = 1 2 r α i j j q j ∣ ≤ r 2 q 4 4 ( 1 − q ) + r ( 8 r q ) 4 2 ( 1 − 8 r q ) ≤ 1 2 r 2 q 4 + r ( 8 r q ) 4 = O ( r 5 q 4 ) , \begin{aligned}
\left|\sum_{j\ge4}\frac{r^2-\sum_{i=1}^{2r}\alpha_i^j}{j}q^j\right|
\le\frac{r^2q^4}{4(1-q)}+\frac{r(8rq)^4}{2(1-8rq)} \\
&\le\frac{1}{2}r^2q^4+r(8rq)^4=O(r^5q^4),
\end{aligned} j ≥ 4 ∑ j r 2 − ∑ i = 1 2 r α i j q j ≤ 4 ( 1 − q ) r 2 q 4 + 2 ( 1 − 8 r q ) r ( 8 r q ) 4 ≤ 2 1 r 2 q 4 + r ( 8 r q ) 4 = O ( r 5 q 4 ) ,
where the last inequality follows from q ≤ 1 / 2 q\le1/2 q ≤ 1/2 and 8 r q ≤ 1 / 2 8rq\le1/2 8 r q ≤ 1/2 . Consequently,
log Φ J r ( 1 − q ) ( 1 − q ) r 2 + 2 = log 1 − 2 q ( 1 − q ) 2 + log Φ K r , r ( 1 − q ) ( 1 − q ) r 2 = − q 2 + ( ( r 2 ) 2 − 2 ) q 3 + O ( r 5 q 4 ) . \begin{aligned}
\log\frac{\Phi_{J_r}(1-q)}{(1-q)^{r^2+2}}
=\log\frac{1-2q}{(1-q)^2}+\log\frac{\Phi_{K_{r,r}}(1-q)}{(1-q)^{r^2}} \\
&=-q^2+\left(\binom{r}{2}^2-2\right)q^3+O(r^5q^4).
\end{aligned} log ( 1 − q ) r 2 + 2 Φ J r ( 1 − q ) = log ( 1 − q ) 2 1 − 2 q + log ( 1 − q ) r 2 Φ K r , r ( 1 − q ) = − q 2 + ( ( 2 r ) 2 − 2 ) q 3 + O ( r 5 q 4 ) .
Taking q = 8 / r 4 q=8/r^4 q = 8/ r 4 gives
log Φ J r ( p ) p r 2 + 2 = 64 r 8 + O ( r − 9 ) > 0 \log\frac{\Phi_{J_r}(p)}{p^{r^2+2}}=\frac{64}{r^8}+O(r^{-9})>0 log p r 2 + 2 Φ J r ( p ) = r 8 64 + O ( r − 9 ) > 0
for all sufficiently large r r r . Thus t ( J r , W ) = p r 2 + 2 < Φ J r ( p ) t(J_r,W)=p^{r^2+2}<\Phi_{J_r}(p) t ( J r , W ) = p r 2 + 2 < Φ J r ( p ) .
Together, Theorem 1.6 and Proposition 6.2 show that the optimal uniform exponent lies between 4 and 12.
Problem 3 (Optimal exponent in the density threshold). Determine the infimum of the exponents γ \gamma γ for which there is a constant C > 0 C > 0 C > 0 such that
t ( H , W ) ≥ Φ H ( p ) whenever p = t ( K 2 , W ) > 1 − 1 C n γ , t(H,W) \ge\Phi_H(p) \qquad\text{whenever} \qquad p=t(K_2,W)>1-\frac{1}{Cn^\gamma}, t ( H , W ) ≥ Φ H ( p ) whenever p = t ( K 2 , W ) > 1 − C n γ 1 ,
for every integer n ≥ 3 n \ge3 n ≥ 3 , every graph H H H of odd girth with at most n n n vertices, and every graphon W W W . In particular, does such a bound hold with γ = 4 \gamma= 4 γ = 4 ?
Formal verification. The main results in § 1 , the density ranges and Turán-optimality statements in Table 1 , the counterexamples in § 5.2 , Proposition 6.1 , and the upper bound in (55) have been formally verified in Lean 4 using Mathlib. The development contains a proof for each of the 117 graphs, including the rational sum-of-squares certificates used in the positive cases and exact counterexamples for the negative cases. It is available at https://github.com/mekty2012/GoodmanTypeBound ; the module Goodman/Paper.lean lists the correspondence between the paper’s statements and their Lean declarations.
The formal proof deviates from the proof in this paper for ease of formalisation. First, in the proof of Lemma 4.4 , it proves the required absolute-error bound directly by leaf integration and L 2 L^2 L 2 estimates, instead of using Sidorenko’s tree inequalities. Second, in the proof of Theorem 4.7 , it replaces the weighted Parseval identity (34) by Bessel’s inequality and controls an additional nonnegative residual term in the spectral decomposition.
AI usage disclosure. The initial proofs of Theorem 1.1 and Corollary 1.5 were generated with GPT-5.5 through ChatGPT Pro. The author proved the general clique-tree criterion in Lemma 1.2 and the result for trivially perfect graphs in Theorem 1.3 by extending these proof ideas. The proof of Theorem 1.6 was obtained using GPT-6 Pro, and the 117 cases in Theorem 1.7 were resolved using GPT-5.6 Codex. The Lean formalisation was carried out using Claude Opus 5 and 5.5. Several attempts with ChatGPT 6 Pro produced neither proofs nor counterexamples for the open problems. GPT-6.1 Sol also assisted with drafting proofs and manuscript text. The author checked and revised this material.
Acknowledgements I would like to thank Hongseok Yang for helpful discussions. I was supported by the National Research Foundation of Korea (NRF) grant funded by the Korean Government (MSIT) (No. RS-2023-00279680).