Paper deep dive

Exponential random graph models with soft clique constraints

Yasmin Tousinejad, Vera Koponen

Year: 2026Venue: arXiv preprintArea: math.COType: PreprintEmbeddings: 166

Intelligence

Status: not_run | Model: - | Prompt: - | Confidence: 0%

Entities (0)

No extracted entities yet.

Relation Signals (0)

No relation signals yet.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Let $r\geq3$ be fixed, and let $\mathbf{G}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\ldots,n\}$. We consider an exponential random graph model which gives higher probability to $G \in \mathbf{G}_n$ than to $H \in \mathbf{G}_n$ if $G$ has fewer $r$-cliques than $H$. But all graphs in $\mathbf{G}_n$ have positive probability. The degree to which graphs with fewer $r$-cliques are given higher probability is determined by a positive weight $w$. We prove that, asymptotically almost surely as $n \to \infty$, a random graph from $\mathbf{G}_n$ has a vertex partition into $r-1$ parts of roughly equal size, the density of edges between the parts is close to $1/2$, and for every $\varepsilon > 0$ the density of edges within any part is less than $\varepsilon$. The asymptotic structural properties are independent of the weight $w$ as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

163,647 characters extracted from source content.

Expand or collapse full text

Exponential random graph models with soft clique constraints Yasmin Tousinejad and Vera Koponen Address: Department of Mathematics, Uppsala University, Sweden. Email address: yasmin.tousinejad@math.u.se Address: Department of Mathematics, Uppsala University, Sweden. Email address: vera.koponen@math.u.se Date: 31 August, 2026 Abstract. Let r≥3r≥ 3 be fixed, and let nG_n be the set of all simple graphs with vertex set [n]=1,…,n[n]=\1,…,n\. We consider an exponential random graph model which gives higher probability to G∈nG _n than to H∈nH _n if G has fewer r-cliques than H. But all graphs in nG_n have positive probability. The degree to which graphs with fewer r-cliques are given higher probability is determined by a positive weight w. We prove that, asymptotically almost surely as n→∞n→∞, a random graph from nG_n has a vertex partition into r−1r-1 parts of roughly equal size, the density of edges between the parts is close to 1/21/2, and for every ε>0 >0 the density of edges within any part is less than ε . The asymptotic structural properties are independent of the weight w as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight. 1. Introduction Studies of large graphs, or other structures, subject to certain hard constraints have a long history in the field of random structures. The classical result of Erdős, Kleitman and Rothschild [12] states that the proportion of bipartite graphs among all triangle-free graphs with vertices 1,…,n1,…,n tends to 11 as n→∞n→∞. More generally, Kolaitis, Prömel and Rothschild [19] proved that, for every fixed r≥3r≥ 3, the proportion of (r−1)(r-1)-partite graphs among all KrK_r-free graphs with vertices 1,…,n1,…,n tends to 11 as n→∞n→∞. We can say that asymptotically almost surely (a.a.s.) a KrK_r-free graph is (r−1)(r-1)-partite. Later studies have considered the a.a.s. structure of H-free graphs for other “forbidden” subgraphs H (e.g. [2, 3, 15]), and yet other investigations have considered forbidding certain induced subgraphs (e.g. [4, 17, 24, 25]). Some studies have considered the a.a.s. structure under constraints other than forbidding a finite number of subgraph or induced subgraph configurations (e.g. [6, 5, 20, 31]), and some have considered structures other than graphs (e.g. [18, 29]). In all mentioned examples, the probability distribution on structures with vertex set [n]:=1,…,n[n]:=\1,…,n\ that satisfy the given constraints is the uniform one. One can reformulate the problem by considering all graphs (or some other kind of structure) with vertex set [n][n], assigning probability 0 to graphs that do not satisfy the constraints and equal probability to the other graphs. An alternative is to not assign probability 0 to graphs that violate the constraints, but to instead consider a probability distribution on graphs with vertex set [n][n] with the following property: A graph with more violations of the constraints is less likely than a graph with fewer violations of the constraints, but graphs with violations can still have positive probability. Since the constraints may be violated in this setting, it is more appropriate to call them soft constraints. This idea is present in so-called exponential random graph models (ERGMs) [27, 9]. The same idea also underlies probability distributions defined by so-called Markov logic networks (MLNs) [26], which are formal specification models in the field of Statistical Relational Artificial Intelligence (SRAI) [8, 11, 13]. MLNs can be defined for finite relational structures, not just graphs, but when restricted to graphs, they are special cases of ERGMs. Not much is known about structural properties of large random structures defined by fixed-weight MLNs. The investigations most directly related to this topic that we are aware of are [21, 30]. Our main result concerns an ERGM, or equivalently an MLN, on random graphs which “penalizes” (for any fixed r≥3r≥ 3) r-cliques, that is, copies of the complete graph on r vertices, denoted KrK_r. In other words, a graph with more r-cliques will be less likely than a graph with fewer r-cliques, but all graphs have positive probability. The strength of the penalization is expressed by a positive weight w. The precise definition of the distribution is given in Definition 2.2. Informally speaking, our main result, Theorem 2.7, shows that, for every fixed positive weight w and every ε>0 >0, with probability tending to 1 as the number n of vertices tends to infinity, the following holds for a random graph: (1) There is a partition of the vertex set into r−1r-1 parts, each of size close to nr−1 nr-1. (2) The density of edges between any two different parts is close to 12 12. (3) For every ε>0 >0, if n is large enough then the density of edges within any part is less than ε . Note that the asymptotic almost sure structure of a random graph does not depend on the weight w (as long as w>0w>0). We also prove (Corollary 6.6) that if r≥4r≥ 4 then the probability that a random graph is (r−2)(r-2)-partite tends to 0 exponentially fast as the number of vertices tends to infinity. A further consequence of our results is a stochastic block model limit for fixed induced subgraphs (Corollary 6.2). Informally speaking, for every fixed m, as n tends to infinity, the subgraph induced by [m][m] converges in distribution to a stochastic block model with r−1r-1 classes such that each of the m vertices is assigned independently and uniformly to one of these classes. Given these assignments, there are no edges within a class, and each possible edge between different classes is included independently with probability 12 12. The limiting distribution depends on r, but not on w. We can refine the probability model considered so that we consider some integers 3≤r1<…<rk3≤ r_1<…<r_k and for each rir_i we penalize an rir_i-clique with weight wi>0w_i>0. (The larger wiw_i is, the more strongly rir_i-cliques are penalized.) We show (Theorem 6.7) that, for all choices of weights w1,…,wk>0w_1,…,w_k>0, the asymptotic behaviour of random graphs under this model is determined by r1r_1. More precisely, with probability tending to 1 as the number n of vertices tends to infinity, a random graph will satisfy conditions (1) – (3) above if we let r:=r1r:=r_1. Our main results are proved by using graphons [7, 22, 16], which are analytic objects used to represent limits of sequences of dense graphs. The article is organized as follows. Just below we introduce the general notation and terminology that will be used. In Section 2 we define the probability model and state the main results (in Theorem 2.7). Section 3 defines the concept of graphon, as well as related concepts, and proves some basic results that will be used later. In Section 4 we work with the concepts of entropy of graphons, homomorphism density of KrK_r in graphons, and the cut distance of a graphon from a “balanced (r−1)(r-1)-partite graphon”, and show how they are related. In Section 5 we prove Theorem 2.7. Section 6 derives some consequences of Theorem 2.7 which were briefly described above. General notation and terminology By ℕN we denote the set of positive integers. For n∈ℕn , [n]:=1,…,n[n]:=\1,…,n\. For n∈ℕn , let nG_n be the set of all undirected graphs without loops (i.e. simple graphs) with vertex set [n][n]. For every finite graph G, let E⁡(G)E(G) denote its edge set and let χ⁡(G)χ(G) denote its chromatic number. If n∈ℕn , G∈nG _n, and A⊆[n]A [n], set eG(A)≔|u,v∈E(G):u,v∈A|.e_G(A) |\\u,v\∈ E(G):\ u,v∈ A\ |. If in addition B⊆[n]B [n] is disjoint from A, define eG(A,B)≔|u,v∈E(G):|u,v∩A|=1,|u,v∩B|=1|.e_G(A,B) |\\u,v\∈ E(G):\ |\u,v\∩ A|=1,\ |\u,v\∩ B|=1\ |. For n∈ℕn and graphs G,H∈nG,H _n, define the n2n^2-normalized edge-edit distance between G and H by dedit(G,H)≔1n2|E⁡(G)△E(H)|.d_edit(G,H) 1n^2\,|E(G) E(H)|. Here △ denotes symmetric difference. Thus dedit(G,H)d_edit(G,H) is the number of edge insertions and deletions needed to turn G into H, normalized by n2n^2. For n∈ℕn and p∈[0,1]p∈[0,1], the notation n∼G⁡(n,p) H_n G(n,p) means that n H_n is a random element of nG_n sampled by including an unordered pair i,j\i,j\ as an edge with probability p, independently of whether other pairs have been included or not. In particular, n∼G⁡(n,12) H_n G(n, 12) means that every graph in nG_n has probability 2−(n2)2^- n2, so n H_n is uniformly distributed on nG_n. For every integer s≥2s≥ 2, KsK_s denotes a complete graph with s vertices. For every finite graph G, let Ks(G)K_s(G) denote the number of unordered copies of KsK_s in G, in other words, the number of subgraphs of G that are isomorphic to KsK_s. 2. The probability model and the main results Throughout this article r≥3r≥ 3 is a fixed integer and w>0w>0 is a fixed real number interpreted as the “weight” that will be associated to every r-tuple of vertices of a graph that does not form an r-clique. 2.1. The probability distribution Definition 2.1. For every n∈ℕn and G∈nG _n, let (2.1) Nr(G):=nr−r!Kr(G),N_r(G):=n^r-r!\,K_r(G), so Nr(G)N_r(G) is the number of ordered r-tuples (v1,…,vr)∈[n]r(v_1,…,v_r)∈[n]^r (with repetitions allowed) that do not consist of r distinct vertices that form an r-clique in G. Definition 2.2. For each n∈ℕn and G∈nG _n, we define its unnormalized mass by μn,r(G)≔exp⁡(wNr(G)). _n,r(G) (w\,N_r(G) ). We then define the partition function (or normalizing constant) by Zn,r≔∑J∈nμn,r(J).Z_n,r _J _n _n,r(J). Finally, we define the probability measure of the model by ℙn,r(A)≔1Zn,r∑G∈Aμn,r(G) for all A⊆n.P_n,r(A) 1Z_n,r _G∈ A _n,r(G) for all \ A _n. For a single graph G∈nG _n, we also set ℙn,r(G)≔ℙn,r(G)=μn,r(G)Zn,r.P_n,r(G) _n,r(\G\)= _n,r(G)Z_n,r. Since w is fixed in the model, we suppress the dependence on w in the notation μn,r _n,r, Zn,rZ_n,r, and ℙn,rP_n,r. Note that if G,H∈nG,H _n and Kr(G)<Kr(H)K_r(G)<K_r(H), then ℙn,r(G)>ℙn,r(H)P_n,r(G)>P_n,r(H). The distribution ℙn,rP_n,r is exactly the probability distribution on nG_n obtained from a Markov logic network [26] with one soft constraint of the form ⋁1≤i<j≤r¬E⁡(xi,xj) with weight w, _1≤ i<j≤ r E(x_i,x_j) with weight w, where ¬E⁡(xi,xj) E(x_i,x_j) expresses that there is no edge between xix_i and xjx_j. Remark 2.3. (On counting only tuples without repetitions) In Definition 2.2 we count all ordered r-tuples (also those with repetitions) (x1,…,xr)∈[n]r.(x_1,…,x_r)∈[n]^r. Another natural convention is to count only those ordered tuples whose entries are pairwise distinct. Under that convention, the total number of allowed ordered tuples is n(n−1)⋯(n−r+1),n(n-1)·s(n-r+1), and the falsifying tuples are still exactly the r!r! orderings of the vertices of each copy of KrK_r. So the number of satisfied groundings becomes Nrdist(G)=n(n−1)⋯(n−r+1)−r!Kr(G).N_r^dist(G)=n(n-1)·s(n-r+1)-r!\,K_r(G). If we use the same weight w, then the corresponding unnormalized mass is μn,rdist(G)≔exp(wNrdist(G))=exp(w[n(n−1)⋯(n−r+1)−r!Kr(G)]). _n,r^dist(G) (w\,N_r^dist(G) )= (w [n(n-1)·s(n-r+1)-r!\,K_r(G) ] ). Compare this with our present convention, μn,r(G)=exp⁡(w⁡[nr−r!Kr(G)]). _n,r(G)= (w[n^r-r!\,K_r(G)] ). Subtracting the exponents gives μn,r(G)=exp(w[nr−n(n−1)⋯(n−r+1)])μn,rdist(G). _n,r(G)= (w [n^r-n(n-1)·s(n-r+1) ] )\, _n,r^dist(G). The factor exp(w[nr−n(n−1)⋯(n−r+1)]) (w [n^r-n(n-1)·s(n-r+1) ] ) is deterministic in the sense that it depends only on n, r, and w, and not on the graph G. Therefore this factor changes the partition function, but it disappears when we normalize to obtain probabilities. Indeed, if Zn,rdist≔∑J∈nμn,rdist(J),Z_n,r^dist _J _n _n,r^dist(J), then Zn,r=exp(w[nr−n(n−1)⋯(n−r+1)])Zn,rdist,Z_n,r= (w [n^r-n(n-1)·s(n-r+1) ] )\,Z_n,r^dist, and hence ℙn,r(G)=μn,r(G)Zn,r=μn,rdist(G)Zn,rdist.P_n,r(G)= _n,r(G)Z_n,r= _n,r^dist(G)Z_n,r^dist. So, for the same clause weight w, the two counting conventions define exactly the same probability measure on nG_n. Thus the choice between these two conventions does not affect which graphs are more or less likely. 2.2. The equivalent exponential random graph model The distribution ℙn,rP_n,r can be defined in the setting of exponential random graph models [27]. Definition 2.4. Fix n,k∈ℕn,k . An Exponential Random Graph Model (ERGM) on nG_n is a probability distribution of the form ℙn,ϑ(G):=exp⁡(∑i=1kϑiTi(G))ZnERGM(ϑ)for all G∈n,P_n, (G):= ( _i=1^k _i\,T_i(G) )Z_n^ERGM( ) all \ G _n, where T1,…,TkT_1,…,T_k are real-valued functions on ⋃n∈ℕn _n G_n, ϑ=(ϑ1,…,ϑk)∈ℝk =( _1,…, _k) ^k is a parameter vector, and ZnERGM(ϑ):=∑J∈nexp⁡(∑i=1kϑiTi(J))Z_n^ERGM( ):= _J _n ( _i=1^k _i\,T_i(J) ) is the normalizing constant. All else being equal, a positive value of ϑi _i rewards larger values of Ti(G)T_i(G) in the exponent, while a negative value penalizes them. Note that if k=1k=1, ϑ1=w _1=w, and T1(G)=Nr(G)T_1(G)=N_r(G), then ℙn,r(G)=ℙn,ϑ(G) for all G∈n.P_n,r(G)=P_n, (G) for all \ G _n. Hence ℙn,rP_n,r is an ERGM. 2.3. The reduced partition function It will be convenient to work with the quantities defined below. Definition 2.5. (a) For all n∈ℕn , let (2.2) Z~n,r≔Z~n,r(w)≔∑J∈nexp⁡(−r!wKr(J)) and Z_n,r Z_n,r(w) _J _n (-r!\,w\,K_r(J) )\ and Fn,r≔Fn,r(w)≔1n2ln⁡Z~n,r. F_n,r F_n,r(w) 1n^2 Z_n,r. We call Z~n,r Z_n,r the reduced partition function and Fn,r(w)F_n,r(w) the reduced free energy. (b) For a graph G∈nG _n, we call exp⁡(−r!wKr(G)) (-r!\,w\,K_r(G) ) the reduced mass of G. Thus Z~n,r Z_n,r is the sum of the reduced masses of all graphs in nG_n. The partition function Zn,rZ_n,r sums the unnormalized masses of all graphs in nG_n. As the next lemma shows, its logarithm contains the graph-independent term wnrwn^r. This term changes the normalizing constant but not the probability measure, so we will often remove it and work with the reduced partition function and reduced free energy. Lemma 2.6. For every n∈ℕn and every G∈nG _n, μn,r(G)=exp⁡(wnr)exp⁡(−r!wKr(G)). _n,r(G)= (w\,n^r ) (-r!\,w\,K_r(G) ). Moreover, Zn,r=exp⁡(wnr)Z~n,r,Z_n,r= (w\,n^r )\, Z_n,r, and (2.3) ℙn,r(G)=exp⁡(−r!wKr(G))∑J∈nexp⁡(−r!wKr(J))=exp⁡(−r!wKr(G))Z~n,r.P_n,r(G)= (-r!\,w\,K_r(G) ) _J _n (-r!\,w\,K_r(J) )= (-r!\,w\,K_r(G) ) Z_n,r. Proof. Insert (2.1) into the definition of μn,r(G) _n,r(G): μn,r(G)=exp⁡(w⁡[nr−r!Kr(G)]). _n,r(G)= (w\,[n^r-r!\,K_r(G)] ). Now factor out the deterministic term ewnre^wn^r. The formulas for Zn,rZ_n,r and ℙn,rP_n,r follow immediately. ∎ 2.4. Main results Recall that we have fixed an integer r≥3r≥ 3 and a real w>0w>0. The notation n∼ℙn,r G_n _n,r means that n G_n is a random graph from nG_n under the distribution ℙn,rP_n,r. (So if J∈nJ _n then ℙ⁡(n=J)=ℙn,r(J)P( G_n=J)=P_n,r(J).) Recall also notation introduced in Section 1. Some of the notions appearing in the main result below are defined only later: A graphon is defined in Definition 3.1. For a graph G∈nG _n, its empirical graphon WGW_G is defined in Definition 3.2. The cut distance δ□ _ between two graphons is defined in Definition 3.6, and the cut distance from a graphon to a family is defined in Definition 3.7. The family Bq⋆B_q is defined in Definition 4.1; informally, it consists of the balanced q-block graphons that are equal to 00 on the diagonal blocks and equal to 12 12 on the off-diagonal blocks. Theorem 2.7. Fix r≥3r≥ 3, set q=r−1q=r-1. Let n∼ℙn,r G_n _n,r. Then the following hold. (i) The reduced free energy satisfies limn→∞Fn,r(w)=ln⁡22(1−1q). _n→∞F_n,r(w)= 22 (1- 1q ). (i) For every ε>0 >0, there are constants c=c⁡(ε,r)>0c=c( ,r)>0 and N=N⁡(ε,r,w)N=N( ,r,w) such that, for every n≥Nn≥ N, ℙ⁡(δ□(Wn,Bq⋆)≥ε)≤e−cn2.P ( _ (W_ G_n,B_q )≥ )≤ e^-cn^2. (i) For every ε>0 >0, there are constants c=c⁡(ε,r)>0c=c( ,r)>0 and n0=n0(ε,r,w)n_0=n_0( ,r,w) such that, for every n≥n0n≥ n_0, with probability at least 1−e−cn21-e^-cn^2, the graph n G_n has a partition [n]=V1⊔⋯⊔Vq[n]=V_1 ·s V_q with the following properties: (a) Each part is almost balanced: ||Vi|−n/q|≤εnfor every i∈[q]. ||V_i|-n/q |≤ n every i∈[q]. (b) Each between-part edge density is close to 12 12: |en(Vi,Vj)|Vi||Vj|−12|≤εfor all distinct i,j∈[q]. | e_ G_n(V_i,V_j)|V_i||V_j|- 12 |≤ all distinct i,j∈[q]. (c) The total number of edges inside the parts satisfies ∑i=1qen(Vi)≤εn210q. _i=1^qe_ G_n(V_i)≤ n^210q. (d) The total density of edges inside the parts is at most ε : ∑i=1qen(Vi)∑i=1q(|Vi|2)≤ε. _i=1^qe_ G_n(V_i) _i=1^q |V_i|2≤ . In particular, if n′ G_n is obtained from n G_n by deleting all edges whose endpoints lie in the same part, then n′ G_n is q-partite and dedit(n,n′)≤ε10q≤ε2.d_edit( G_n, G_n )≤ 10q≤ 2. 2.5. Related work In the introduction we mentioned several studies of graphs, or other relational structures, subject to “hard” constraints. We also mentioned [21, 30] about structures subject to “soft” constraints defined by Markov logic networks. As we use graphons to prove our main results we like to mention [1] which considers Markov logic networks and a multi-relational analogue of a graphon in the context when one considers several different edge relations. However, the results in [1], which generalize the basic theory of graphons, are not of help in the present context as far as we can see. In [9] Chatterjee and Diaconis consider ERGM distributions on nG_n of the form ℙnT(G)=exp⁡(n2T(G))∑J∈nexp⁡(n2T(J))P_n^T(G)= (n^2T(G) ) _J _n (n^2T(J) ) where T is a function from ⋃n∈ℕn _n G_n into the reals. If we rewrite the distribution ℙn,rP_n,r so that, for an appropriate choice of T and all n, ℙn,r=ℙnTP_n,r=P_n^T then, for all n and all G∈nG _n, we must have T⁡(G):=wNr(G)n2.T(G):= wN_r(G)n^2. Recall that Nr(G)N_r(G) is the number of r-tuples of vertices of G that do not form an r-clique. So if G∈nG _n does not have an r-clique (e.g. if G is (r−1)(r-1)-partite), then Nr(G)=nrN_r(G)=n^r where r≥3r≥ 3. It follows that maxG∈n⁡T⁡(G) _G _nT(G) is unbounded as n→∞n→∞. But the results of [9] assume that maxG∈n⁡T⁡(G) _G _nT(G) is bounded as n→∞n→∞. Therefore their results do not apply to the present context. 3. Graphon preliminaries 3.1. Basic definitions Definition 3.1 (Graphon). A graphon is a measurable function W:[0,1]2→[0,1]W:[0,1]^2→[0,1] such that W⁡(x,y)=W⁡(y,x)W(x,y)=W(y,x) for almost every (x,y)∈[0,1]2(x,y)∈[0,1]^2. Let W denote the family of these measurable functions. Let λ denote Lebesgue measure on [0,1][0,1]. For each integer m≥1m≥ 1, let λmλ^m denote the product Lebesgue measure on [0,1]m[0,1]^m. Graphons are the standard limit objects for dense graphs. They also define random graph models. Let W be a graphon and let n∈ℕn . Choose X1,…,XnX_1,…,X_n independently and uniformly from [0,1][0,1]. Conditional on X1,…,XnX_1,…,X_n, put each edge i,j\i,j\ with i<ji<j into the graph independently with probability W⁡(Xi,Xj).W(X_i,X_j). Definition 3.2 (Empirical graphon). Let n∈ℕn , and let G be a graph with vertex set [n][n] and adjacency matrix (aij)1≤i,j≤n(a_ij)_1≤ i,j≤ n, where aij=ajiandaii=0.a_ij=a_ji a_i=0. Split [0,1][0,1] into n intervals of equal length by setting Ii=[i−1n,in)for 1≤i<n,In=[n−1n,1].I_i= [ i-1n, in ) 1≤ i<n, I_n= [ n-1n,1 ]. The empirical graphon of G is the graphon WG:[0,1]2→[0,1]W_G:[0,1]^2→[0,1] defined as follows. If x∈Iix∈ I_i and y∈Ijy∈ I_j, then WG(x,y)≔aij.W_G(x,y) a_ij. Thus WGW_G records the adjacency matrix of G on the n2n^2 rectangles Ii×IjI_i× I_j. It is measurable, symmetric, and takes only the values 00 and 11. Also, WG=0W_G=0 on each rectangle Ii×IiI_i× I_i, because aii=0a_i=0. Definition 3.3 (Homomorphism density). Let H be a finite simple graph with vertex set V⁡(H)=1,…,kV(H)=\1,…,k\. For a graphon W, the homomorphism density of H in W is t(H,W)≔∫[0,1]k∏i,j∈E⁡(H)W(xi,xj)dx1⋯dxk.t(H,W) _[0,1]^k _\i,j\∈ E(H)W(x_i,x_j)\,dx_1·s dx_k. Remark 3.4. For H=KrH=K_r this becomes t(Kr,W)=∫[0,1]r∏1≤a<b≤rW(xa,xb)dx1⋯dxr.t(K_r,W)= _[0,1]^r _1≤ a<b≤ rW(x_a,x_b)\,dx_1·s dx_r. The integrand is nonnegative. So if t⁡(Kr,W)=0t(K_r,W)=0, then the product inside the integral must vanish almost everywhere. From now on, a graphon W is called a graphon of zero KrK_r-density if t⁡(Kr,W)=0,t(K_r,W)=0, that is, if its KrK_r-homomorphism density is zero. Definition 3.5 (Cut norm). For an integrable function U:[0,1]2→ℝU:[0,1]^2 , the cut norm is ‖U‖□≔supS,T⊆[0,1]S,T measurable|∫S×TU⁡(x,y)xy|.\|U\|_ _ subarraycS,T [0,1]\\ S,T measurable subarray | _S× TU(x,y)\,dx\,dy |. Definition 3.6 (Cut distance). A measurable map ϕ:[0,1]→[0,1]φ:[0,1]→[0,1] is measure-preserving if λ⁡(ϕ−1(A))=λ⁡(A)for every Lebesgue-measurable A⊆[0,1].λ(φ^-1(A))=λ(A) every Lebesgue-measurable A [0,1]. A measure-preserving bijection is a bijection ϕ:[0,1]→[0,1]φ:[0,1]→[0,1] such that both ϕφ and ϕ−1φ^-1 are Lebesgue-measurable and ϕφ is measure-preserving. If W is a graphon and ϕφ is a measure-preserving map, define Wϕ(x,y)≔W⁡(ϕ⁡(x),ϕ⁡(y)).W^φ(x,y) W(φ(x),φ(y)). Thus WϕW^φ is obtained from W by applying ϕφ to both variables. When ϕφ is a measure-preserving bijection, we call WϕW^φ a relabeling of W. For graphons W1W_1 and W2W_2, their cut distance is δ□(W1,W2)≔infϕ‖W1−W2ϕ‖□, _ (W_1,W_2) _φ\|W_1-W_2^φ\|_ , where the infimum is taken over all measure-preserving bijections ϕ:[0,1]→[0,1]φ:[0,1]→[0,1]. Relabeling by a measure-preserving bijection does not change the cut norm. Indeed, let F:[0,1]2→ℝF:[0,1]^2 be a measurable function with ∫[0,1]2|F⁡(x,y)|xy<∞, _[0,1]^2|F(x,y)|\,dx\,dy<∞, and let ϕφ be a measure-preserving bijection. Define Fϕ(x,y)≔F⁡(ϕ⁡(x),ϕ⁡(y)).F^φ(x,y) F(φ(x),φ(y)). Then ‖Fϕ‖□=‖F‖□.\|F^φ\|_ =\|F\|_ . This follows by changing variables in the integral over S×TS× T. Since ϕφ is measure-preserving and bijective, the sets ϕ⁡(S)φ(S) and ϕ⁡(T)φ(T) run through the same measurable subsets of [0,1][0,1] as S and T. Thus the supremum in the cut norm is unchanged. Definition 3.7. Let W be a graphon, and let ℱF be a nonempty family of graphons. The cut distance from W to ℱF is δ□(W,ℱ)≔infV∈ℱδ□(W,V). _ (W,F) _V _ (W,V). The cut distance δ□ _ is a pseudometric on W. Indeed, let U,V,W∈U,V,W . To see symmetry, let ϕφ be a measure-preserving bijection. By invariance of the cut norm under relabeling, ‖U−Vϕ‖□=‖Uϕ−1−V‖□=‖V−Uϕ−1‖□.\|U-V^φ\|_ =\|U^φ^-1-V\|_ =\|V-U^φ^-1\|_ . Taking the infimum over ϕφ gives δ□(U,V)=δ□(V,U) _ (U,V)= _ (V,U). For the triangle inequality, if ϕφ and ψ are measure-preserving bijections, then ‖U−Wψ∘ϕ‖□ \|U-W^ψ φ\|_ ≤‖U−Vϕ‖□+‖Vϕ−(Wψ)ϕ‖□ ≤\|U-V^φ\|_ +\|V^φ-(W^ψ)^φ\|_ =‖U−Vϕ‖□+‖V−Wψ‖□. =\|U-V^φ\|_ +\|V-W^ψ\|_ . Taking the infimum over ϕφ and ψ proves the triangle inequality. Nonnegativity and δ□(U,U)=0 _ (U,U)=0 are immediate. Notation 3.8 (Reduced graphon space). Define W∼V⟺δ□(W,V)=0,W V _ (W,V)=0, and let ~≔/∼,π:→~ W / , π:W→ W be the quotient space and quotient map. We use W~≔π⁡(W) W π(W) and, for n∈ℕn and G∈nG _n, W~G≔π⁡(WG) W_G π(W_G). For reduced graphons define d□(U~,V~)≔δ□(U,V),d_ ( U, V) _ (U,V), where U and V are arbitrary representatives. This definition does not depend on the chosen representatives. Indeed, if U′∼U U and V′∼V V, then δ□(U′,V′)≤δ□(U′,U)+δ□(U,V)+δ□(V,V′)=δ□(U,V). _ (U ,V )≤ _ (U ,U)+ _ (U,V)+ _ (V,V )= _ (U,V). The same argument with (U,V)(U,V) and (U′,V′)(U ,V ) interchanged gives δ□(U,V)≤δ□(U′,V′). _ (U,V)≤ _ (U ,V ). Hence δ□(U′,V′)=δ□(U,V). _ (U ,V )= _ (U,V). Thus d□d_ is well defined on ~ W. It is a metric because nonnegativity, symmetry, and the triangle inequality are inherited from δ□ _ . Also, d□(U~,V~)=0d_ ( U, V)=0 holds exactly when U∼VU V, which means U~=V~ U= V. The metric space (~,d□)( W,d_ ) is compact; see [22, Thm. 9.23]. For ℱ⊆F , we use π⁡(ℱ)≔π⁡(W):W∈ℱ⊆~π(F) \π(W):W \ W for its quotient image. Remark 3.9 (Zero cut distance). For graphons U and V, the condition δ□(U,V)=0 _ (U,V)=0 means that U and V represent the same graph limit. Equivalently, there exist measure-preserving maps ϕ,ψ:[0,1]→[0,1]φ,ψ:[0,1]→[0,1] such that Uϕ=Vψalmost everywhere;U^φ=V^ψ everywhere; see [22, Cor. 10.34 and Cor. 10.35(a)]. The maps in this characterization need not be bijections. Consequently, the condition δ□(U,V)=0 _ (U,V)=0 is weaker than almost-everywhere equality after a single measure-preserving relabeling. By Notation 3.8, graphons at zero cut distance represent the same point of ~ W. This quotient space is the reduced graphon space used in [10, Sec. 1.3]. Notation 3.10. For an integrable function U:[0,1]2→ℝU:[0,1]^2 , the L1L^1-norm is defined as ‖U‖1≔∫[0,1]2|U⁡(x,y)|xy.\|U\|_1 _[0,1]^2|U(x,y)|\,dx\,dy. Notation 3.11 (Indicator functions). For any set or event A, A1_A denotes its indicator. Thus A(z)=11_A(z)=1 when z∈Az∈ A and A(z)=01_A(z)=0 otherwise. Lemma 3.12. We will use the following two forms of the Cauchy-Schwarz inequality. (i) If S⊆[0,1]2S [0,1]^2 is measurable and f:S→ℝf:S is measurable with ∫Sf2<∞, _Sf^2<∞, then (∫S|f|)2≤λ2(S)∫Sf2. ( _S|f| )^2≤λ^2(S) _Sf^2. (i) If m≥1m≥ 1 is an integer and x1,…,xm∈ℝx_1,…,x_m , then (∑a=1mxa)2≤m∑a=1mxa2. ( _a=1^mx_a )^2≤ m _a=1^mx_a^2. Equivalently, ∑a=1mxa2≥1m(∑a=1mxa)2. _a=1^mx_a^2≥ 1m ( _a=1^mx_a )^2. Consequently, if q∈ℕq , n∈ℤ≥0n _≥ 0, m1,…,mq∈ℤ≥0m_1,…,m_q _≥ 0, and ∑a=1qma=n, _a=1^qm_a=n, then ∑a=1q(ma2)=12(∑a=1qma2−n)≥12(n2q−n). _a=1^q m_a2= 12 ( _a=1^qm_a^2-n )≥ 12 ( n^2q-n ). Proof. For (i), apply [28, Thm. 11.35] to the functions |f||f| and 11 on S. We get ∫S|f|≤(∫Sf2)1/2(∫S1)1/2. _S|f|≤ ( _Sf^2 )^1/2 ( _S1 )^1/2. Since ∫S1=λ2(S), _S1=λ^2(S), it follows that (∫S|f|)2≤λ2(S)∫Sf2. ( _S|f| )^2≤λ^2(S) _Sf^2. For (i), apply [28, Thm. 1.35] to the two lists x1,…,xmand1,…,1.x_1,…,x_m 1,…,1. This gives (∑a=1mxa)2≤(∑a=1mxa2)(∑a=1m1)=m∑a=1mxa2. ( _a=1^mx_a )^2≤ ( _a=1^mx_a^2 ) ( _a=1^m1 )=m _a=1^mx_a^2. Dividing by m, we obtain ∑a=1mxa2≥1m(∑a=1mxa)2. _a=1^mx_a^2≥ 1m ( _a=1^mx_a )^2. Now apply (i) with m=qm=q and xa=max_a=m_a. Since ∑a=1qma=n, _a=1^qm_a=n, we have ∑a=1qma2≥n2q. _a=1^qm_a^2≥ n^2q. Therefore ∑a=1q(ma2)=12∑a=1qma(ma−1)=12(∑a=1qma2−n)≥12(n2q−n). _a=1^q m_a2= 12 _a=1^qm_a(m_a-1)= 12 ( _a=1^qm_a^2-n )≥ 12 ( n^2q-n ). ∎ Lemma 3.13. Let F:[0,1]2→ℝF:[0,1]^2 be bounded and measurable, and let f,g:[0,1]→[0,1]f,g:[0,1]→[0,1] be measurable. Then |∫[0,1]2F⁡(x,y)f(x)g(y)xy|≤‖F‖□. | _[0,1]^2F(x,y)\,f(x)\,g(y)\,dx\,dy |≤\|F\|_ . Proof. By [16, Eq. (4.2) and Rem. 4.1], ∥F∥□=supϕ,ψ:[0,1]→[0,1]ϕ,ψ measurable|∫[0,1]2F(x,y)ϕ(x)ψ(y)dxdy|.\|F\|_ = _ subarraycφ,ψ:[0,1]→[0,1]\\ φ,ψ measurable subarray | _[0,1]^2F(x,y)φ(x)ψ(y)\,dx\,dy |. Taking ϕ=fφ=f and ψ=gψ=g gives |∫[0,1]2F⁡(x,y)f(x)g(y)xy|≤‖F‖□. | _[0,1]^2F(x,y)f(x)g(y)\,dx\,dy |≤\|F\|_ . ∎ Lemma 3.14 (Clique density is Lipschitz in cut distance). Let r≥2r≥ 2. For all graphons U and V, |t⁡(Kr,U)−t⁡(Kr,V)|≤(r2)‖U−V‖□.|t(K_r,U)-t(K_r,V)|≤ r2\,\|U-V\|_ . Consequently, |t⁡(Kr,U)−t⁡(Kr,V)|≤(r2)δ□(U,V).|t(K_r,U)-t(K_r,V)|≤ r2\, _ (U,V). In particular, the map W↦t⁡(Kr,W)W t(K_r,W) is continuous with respect to cut distance. Proof. By [16, Rem. 2.1], every Lebesgue-measurable graphon on [0,1]2[0,1]^2 is equal almost everywhere to a Borel-measurable one. Such a replacement changes neither homomorphism densities nor cut norms. We may therefore replace U and V by Borel-measurable representatives and continue to denote them by U and V. In particular, whenever all but one of the variables are fixed below, the resulting one-variable function is measurable. Let m≔(r2),D≔U−V.m r2, D U-V. Choose once and for all an ordering of the (r2) r2 edges of KrK_r. Equivalently, choose an ordering of the pairs (i1,j1),…,(im,jm),1≤iℓ<jℓ≤r,(i_1,j_1),…,(i_m,j_m), 1≤ i_ <j_ ≤ r, so that every pair appears exactly once. Vertex s carries the single variable xs∈[0,1]x_s∈[0,1]. The symbols iℓi_ and jℓj_ record which two vertices form the ℓ -th edge in the chosen list. For example, when r=4r=4, one possible ordering is (i1,j1) (i_1,j_1) =(1,2), =(1,2), (i2,j2) (i_2,j_2) =(1,3), =(1,3), (i3,j3) (i_3,j_3) =(1,4), =(1,4), (i4,j4) (i_4,j_4) =(2,3), =(2,3), (i5,j5) (i_5,j_5) =(2,4), =(2,4), (i6,j6) (i_6,j_6) =(3,4). =(3,4). By Remark 3.4, t(Kr,W)=∫[0,1]r∏ℓ=1mW(xiℓ,xjℓ)dx1⋯dxr.t(K_r,W)= _[0,1]^r _ =1^mW(x_i_ ,x_j_ )\,dx_1·s dx_r. This means that we choose numbers x1,…,xr∈[0,1],x_1,…,x_r∈[0,1], one number for each vertex of the clique. For every edge i,j\i,j\ of the clique, we include the factor W⁡(xi,xj)W(x_i,x_j). Then we multiply all these factors together. Finally, we average over all choices of (x1,…,xr)∈[0,1]r(x_1,…,x_r)∈[0,1]^r. Since the set [0,1]r[0,1]^r has total measure 11, the integral here is literally an average. Applying this formula to U and to V, we obtain t(Kr,U)−t(Kr,V)=∫[0,1]r(∏ℓ=1mU(xiℓ,xjℓ)−∏ℓ=1mV(xiℓ,xjℓ))dx1⋯dxr.t(K_r,U)-t(K_r,V)= _[0,1]^r ( _ =1^mU(x_i_ ,x_j_ )- _ =1^mV(x_i_ ,x_j_ ) )\,dx_1·s dx_r. To compare the two products, it is helpful to change the edge factors one at a time. For a fixed point (x1,…,xr)∈[0,1]r(x_1,…,x_r)∈[0,1]^r, use Uℓ≔U⁡(xiℓ,xjℓ),Vℓ≔V⁡(xiℓ,xjℓ).U_ U(x_i_ ,x_j_ ), V_ V(x_i_ ,x_j_ ). Now define P0≔∏ℓ=1mVℓ,P_0 _ =1^mV_ , and for s=1,…,ms=1,…,m define Ps≔(∏ℓ=1sUℓ)(∏ℓ=s+1mVℓ).P_s ( _ =1^sU_ ) ( _ =s+1^mV_ ). Thus P0P_0 is the product built entirely from V, while PmP_m is the product built entirely from U. Therefore ∏ℓ=1mUℓ−∏ℓ=1mVℓ=Pm−P0=∑s=1m(Ps−Ps−1). _ =1^mU_ - _ =1^mV_ =P_m-P_0= _s=1^m(P_s-P_s-1). For each s, only the s-th factor changes when one passes from Ps−1P_s-1 to PsP_s, so Ps−Ps−1=(∏ℓ<sUℓ)(Us−Vs)(∏ℓ>sVℓ).P_s-P_s-1= ( _ <sU_ )(U_s-V_s) ( _ >sV_ ). Substituting back the definitions of UℓU_ and VℓV_ , we get ∏ℓ=1mU⁡(xiℓ,xjℓ)−∏ℓ=1mV⁡(xiℓ,xjℓ) _ =1^mU(x_i_ ,x_j_ )- _ =1^mV(x_i_ ,x_j_ ) =∑s=1m(∏ℓ<sU⁡(xiℓ,xjℓ))D(xis,xjs)(∏ℓ>sV⁡(xiℓ,xjℓ)). = _s=1^m ( _ <sU(x_i_ ,x_j_ ) )D(x_i_s,x_j_s) ( _ >sV(x_i_ ,x_j_ ) ). If s=1s=1 or s=ms=m, one of the products is empty; by convention, an empty product is equal to 11. Substituting this into the integral and using the triangle inequality, we obtain |t⁡(Kr,U)−t⁡(Kr,V)|≤∑s=1mIs,|t(K_r,U)-t(K_r,V)|≤ _s=1^mI_s, where (3.1) Is I_s ≔|∫[0,1]r(∏ℓ<sU(xiℓ,xjℓ))D(xis,xjs)(∏ℓ>sV(xiℓ,xjℓ))dx1⋯dxr|. | _[0,1]^r ( _ <sU(x_i_ ,x_j_ ) )D(x_i_s,x_j_s) ( _ >sV(x_i_ ,x_j_ ) )\,dx_1·s dx_r |. We now estimate one such term. Fix s∈1,…,ms∈\1,…,m\ and use (is,js)=(a,b).(i_s,j_s)=(a,b). Let x^=(xt)t∈[r]∖a,b,dx^≔∏t∈[r]∖a,bdxt, x=(x_t)_t∈[r] \a,b\, d x _t∈[r] \a,b\dx_t, where the coordinates are taken in increasing order. Thus x x denotes all variables except xax_a and xbx_b. When r=2r=2, [0,1]0[0,1]^0 is interpreted as a one-point probability space, so integration with respect to dx^d x means evaluation at that point. Because every graphon takes values in [0,1][0,1], the integrand in (3.1) is measurable and bounded in absolute value by 11. Thus it is integrable on [0,1]r[0,1]^r. We can therefore write the integral by first averaging over the two variables xax_a and xbx_b, and then averaging over the remaining r−2r-2 variables, which we collect in x x. The distinguished edge a,b\a,b\ contributes the factor D⁡(xa,xb).D(x_a,x_b). Every other edge of KrK_r falls into exactly one of the following three types. An edge of the form a,c\a,c\ with c∉a,bc∉\a,b\ contributes a factor that depends on xax_a but not on xbx_b. An edge of the form b,c\b,c\ with c∉a,bc∉\a,b\ contributes a factor that depends on xbx_b but not on xax_a. An edge of the form c,d\c,d\ with c,d∉a,bc,d∉\a,b\ contributes a factor that depends on neither xax_a nor xbx_b; once x x is fixed, it is constant. Because KrK_r is a simple graph, there is only one edge joining a and b. So the factor D⁡(xa,xb)D(x_a,x_b) is the only factor that depends on both variables at the same time. Figure 1 illustrates this factorization in the case K4K_4. Figure 1. In the integral defining t⁡(K4,W)t(K_4,W), vertex i carries the variable xix_i, and the edge i,j\i,j\ contributes the factor W⁡(xi,xj)W(x_i,x_j). If the distinguished edge is 3,4\3,4\, then that edge contributes the factor (U−V)(x3,x4)(U-V)(x_3,x_4). Once x1x_1 and x2x_2 are fixed, the remaining factors split into a function of x3x_3, a function of x4x_4, and a constant. Therefore, for each fixed choice of x x, the whole integrand in (3.1) can be written in the form C⁡(x^)D(xa,xb)Ax^(xa)Bx^(xb),C( x)\,D(x_a,x_b)\,A_ x(x_a)\,B_ x(x_b), where Ax^,Bx^:[0,1]→[0,1]A_ x,B_ x:[0,1]→[0,1] are measurable and C⁡(x^)∈[0,1]C( x)∈[0,1]. More concretely, Ax^A_ x is the product of all remaining factors coming from edges that touch a but not b, Bx^B_ x is the product of all remaining factors coming from edges that touch b but not a, and C⁡(x^)C( x) is the product of all remaining factors coming from edges that touch neither a nor b. Empty products are interpreted as 11. These functions take values in [0,1][0,1] because every graphon factor does. Using this factorization and averaging first in xax_a and xbx_b, we get (3.2) Is I_s =|∫[0,1]r−2∫[0,1]2C⁡(x^)D(xa,xb)Ax^(xa)Bx^(xb)dxadxbdx^| = | _[0,1]^r-2 _[0,1]^2C( x)\,D(x_a,x_b)\,A_ x(x_a)\,B_ x(x_b)\,dx_a\,dx_b\,d x | ≤∫[0,1]r−2|∫[0,1]2D⁡(xa,xb)(C⁡(x^)Ax^(xa))Bx^(xb)dxadxb|dx^. ≤ _[0,1]^r-2 | _[0,1]^2D(x_a,x_b)\, (C( x)A_ x(x_a) )\,B_ x(x_b)\,dx_a\,dx_b |\,d x. For each fixed x x, define fx^(xa)≔C⁡(x^)Ax^(xa),gx^(xb)≔Bx^(xb).f_ x(x_a) C( x)A_ x(x_a), g_ x(x_b) B_ x(x_b). Then fx^,gx^:[0,1]→[0,1]f_ x,g_ x:[0,1]→[0,1] are measurable, so Lemma 3.13 applies and gives |∫[0,1]2D⁡(xa,xb)fx^(xa)gx^(xb)dxadxb|≤‖D‖□. | _[0,1]^2D(x_a,x_b)\,f_ x(x_a)\,g_ x(x_b)\,dx_a\,dx_b |≤\|D\|_ . Substituting this bound into (3.2) yields Is≤∫[0,1]r−2‖D‖□x^=‖D‖□,I_s≤ _[0,1]^r-2\|D\|_ \,d x=\|D\|_ , because the set [0,1]r−2[0,1]^r-2 has total measure 11. This bound is the same for every s∈[m]s∈[m]. Hence |t⁡(Kr,U)−t⁡(Kr,V)|≤∑s=1mIs≤∑s=1m‖D‖□=m‖D‖□=(r2)‖U−V‖□.|t(K_r,U)-t(K_r,V)|≤ _s=1^mI_s≤ _s=1^m\|D\|_ =m\,\|D\|_ = r2\,\|U-V\|_ . This proves the first inequality. We now pass from cut norm to cut distance. Let ϕφ be any measure-preserving bijection of [0,1][0,1]. By Definition 3.6, Vϕ(x,y)=V⁡(ϕ⁡(x),ϕ⁡(y)).V^φ(x,y)=V(φ(x),φ(y)). Define Φ:[0,1]r→[0,1]r,Φ⁡(x1,…,xr)≔(ϕ⁡(x1),…,ϕ⁡(xr)). :[0,1]^r→[0,1]^r, (x_1,…,x_r) (φ(x_1),…,φ(x_r)). Since ϕφ preserves Lebesgue measure on [0,1][0,1], the map Φ preserves the product measure on [0,1]r[0,1]^r. Therefore t⁡(Kr,Vϕ)=t⁡(Kr,V).t(K_r,V^φ)=t(K_r,V). Applying the inequality already proved to U and VϕV^φ, we obtain |t⁡(Kr,U)−t⁡(Kr,V)|=|t⁡(Kr,U)−t⁡(Kr,Vϕ)|≤(r2)‖U−Vϕ‖□.|t(K_r,U)-t(K_r,V)|=|t(K_r,U)-t(K_r,V^φ)|≤ r2\,\|U-V^φ\|_ . Now take the infimum over all measure-preserving bijections ϕφ. By the definition of δ□ _ , |t⁡(Kr,U)−t⁡(Kr,V)|≤(r2)δ□(U,V).|t(K_r,U)-t(K_r,V)|≤ r2\, _ (U,V). Thus W↦t⁡(Kr,W)W t(K_r,W) is Lipschitz with respect to cut distance, and in particular it is continuous. ∎ 3.2. Entropy Entropy tells us, on the logarithmic scale, how many ways there are to choose edges and non-edges so that the edge density has a fixed value. The relevant one-variable function is the binary entropy h⁡(p)≔−pln⁡p−(1−p)ln⁡(1−p),p∈[0,1],h(p) -p p-(1-p) (1-p), p∈[0,1], with the convention 0ln⁡0≔00 0 0. If pNpN is an integer, then the number of 00–11 strings of length N with exactly pNpN ones is (NpN) NpN, and for large N the logarithm of this number has leading term Nh(p)Nh(p). Thus h⁡(p)h(p) measures the entropy contribution per possible edge when the edge density is p. In particular, h⁡(0)=h⁡(1)=0,0≤h⁡(p)≤ln⁡2,h⁡(12)=ln⁡2.h(0)=h(1)=0, 0≤ h(p)≤ 2, h ( 12 )= 2. So the entropy is zero when the presence or absence of an edge is completely determined, and it is largest at p=12p= 12, where the two possibilities are most evenly balanced. Definition 3.15 (Graphon entropy). For a graphon W, define (3.3) Ent⁡(W)≔12∫[0,1]2h⁡(W⁡(x,y))xy. (W) 12 _[0,1]^2h (W(x,y) )\,dx\,dy. The factor 12 12 is needed because the square [0,1]2[0,1]^2 counts both (x,y)(x,y) and (y,x)(y,x), while an edge is an unordered pair. Lemma 3.16. For every p∈[0,1]p∈[0,1], (3.4) h⁡(p)≤ln⁡2−2(p−12)2.h(p)≤ 2-2 (p- 12 )^2. Proof. Set ψ⁡(p)≔ln⁡2−h⁡(p)−2(p−12)2.ψ(p) 2-h(p)-2 (p- 12 )^2. For p∈(0,1)p∈(0,1), h′(p)=ln⁡1−p,h (p)= 1-pp, so ψ′(p)=ln⁡p1−p−4(p−12).ψ (p)= p1-p-4 (p- 12 ). Also, ψ′(p)=1p⁡(1−p)−4≥0,ψ (p)= 1p(1-p)-4≥ 0, because p⁡(1−p)≤1/4p(1-p)≤ 1/4. Thus ψ is convex on (0,1)(0,1) and extends continuously to [0,1][0,1]. Since ψ⁡(12)=0,ψ′(12)=0,ψ ( 12 )=0, ψ ( 12 )=0, the point p=1/2p=1/2 is a global minimizer. Hence ψ⁡(p)≥0ψ(p)≥ 0 for every p∈[0,1]p∈[0,1], which gives (3.4). ∎ Lemma 3.17. If U,V∈U,V satisfy δ□(U,V)=0 _ (U,V)=0, then Ent⁡(U)=Ent⁡(V). (U)= (V). Consequently, Ent⁡(W~)≔Ent⁡(W),W~=π⁡(W), ( W) (W), W=π(W), is a well-defined function on ~ W. Proof. By Remark 3.9, there are measure-preserving maps ϕ,ψ:[0,1]→[0,1]φ,ψ:[0,1]→[0,1] such that Uϕ=VψU^φ=V^ψ almost everywhere. The product maps ϕ×ϕφ×φ and ψ×ψ×ψ preserve λ2λ^2, hence Ent⁡(U)=Ent⁡(Uϕ)=Ent⁡(Vψ)=Ent⁡(V). (U)= (U^φ)= (V^ψ)= (V). ∎ Graphon entropy controls the number of finite graphs with prescribed large-scale structure. More precisely, for a cut-closed family ℱF, the n2n^2-scale upper bound is governed by supW∈ℱEnt⁡(W) _W (W), rather than by the entropy of an arbitrarily chosen member of ℱF. In Section 5, Lemma 5.9 uses such an entropy supremum to bound the number of graphs whose empirical graphons lie in a given family. We combine this result with Lemma 4.12 in the proof of Theorem 2.7(i) to show that the probability of staying a fixed cut distance away from Bq⋆B_q decreases exponentially in n2n^2. Lemma 4.5 shows that, among graphons with zero KrK_r-density, entropy is maximized exactly by the graphons at zero cut distance from Bq⋆B_q . Lemma 3.18. For every n∈ℕn , every graph G with vertex set [n][n], and every integer r≥2r≥ 2, t⁡(Kr,WG)=r!Kr(G)nr.t(K_r,W_G)= r!\,K_r(G)n^r. Proof. Let (aij)1≤i,j≤n(a_ij)_1≤ i,j≤ n be the adjacency matrix of G, and let I1,…,InI_1,…,I_n be the intervals from Definition 3.2. Splitting [0,1]r[0,1]^r into the boxes Iv1×⋯×Ivr,v1,…,vr∈[n],I_v_1×·s× I_v_r, v_1,…,v_r∈[n], gives (3.5) t⁡(Kr,WG)=1nr∑v1,…,vr∈[n]∏1≤s<t≤ravs,vt.t(K_r,W_G)= 1n^r _v_1,…,v_r∈[n] _1≤ s<t≤ ra_v_s,v_t. Since every entry of the adjacency matrix is either 00 or 11, the summand corresponding to (v1,…,vr)(v_1,…,v_r) is equal to 11 exactly when the vertices v1,…,vrv_1,…,v_r are pairwise distinct and form a copy of KrK_r in G. Indeed, if vs=vtv_s=v_t for some s<ts<t, then the product contains the factor avs,vt=avs,vs=0,a_v_s,v_t=a_v_s,v_s=0, because G has no loops. Thus the sum in (3.5) counts the ordered r-tuples obtained by ordering the vertices of copies of KrK_r in G. Every unordered copy has exactly r!r! such orderings, and therefore (3.6) ∑v1,…,vr∈[n]∏1≤s<t≤ravs,vt=r!Kr(G). _v_1,…,v_r∈[n] _1≤ s<t≤ ra_v_s,v_t=r!\,K_r(G). Combining (3.5) and (3.6) gives t⁡(Kr,WG)=r!Kr(G)nr,t(K_r,W_G)= r!\,K_r(G)n^r, as required. ∎ Remark 3.19. For n≥rn≥ r, Lemma 3.18 gives t⁡(Kr,WG)=n(n−1)⋯(n−r+1)nrKr(G)(nr).t(K_r,W_G)= n(n-1)·s(n-r+1)n^r\, K_r(G) nr. Thus the graphon homomorphism-density normalization differs from the usual clique density based on unordered copies by the factor n(n−1)⋯(n−r+1)nr. n(n-1)·s(n-r+1)n^r. For fixed r, limn→∞n(n−1)⋯(n−r+1)nr=1. _n→∞ n(n-1)·s(n-r+1)n^r=1. 4. Entropy maximizers and stability In this section we define a family of “balanced q-partite graphons” (recall q:=r−1q:=r-1) and prove results which relate the distance of a graphon W to a balanced q-partite graphon to the homomorphism density of KrK_r in W and the entropy of W. In particular, we show that the balanced q-partite graphons are the graphons that maximize entropy among the graphons with KrK_r-homomorphism density 0. This will be used in the proof of Theorem 2.7 in Section 5. 4.1. The family Bq⋆B_q and the balanced Turán graphons Definition 4.1. Let q≥2q≥ 2. The family Bq⋆B_q consists of all graphons W:[0,1]2→[0,1]W:[0,1]^2→[0,1] for which there exists a measurable partition [0,1]=A1⊔⋯⊔Aq,λ⁡(Ai)=1qfor every i∈[q],[0,1]=A_1 ·s A_q, λ(A_i)= 1q every i∈[q], such that W⁡(x,y)=0for almost every (x,y)∈Ai×Aifor every i,W(x,y)=0 almost every\ (x,y)∈ A_i× A_i every i, and W⁡(x,y)=12for almost every (x,y)∈Ai×Ajfor all distinct i,j∈[q].W(x,y)= 12 almost every\ (x,y)∈ A_i× A_j all distinct i,j∈[q]. Equivalently, the values of W on the q2q^2 block products are given by the following block-value matrix: [012⋯12120⋯12⋱1212⋯0] bmatrix0& 12&·s& 12\\ 12&0&·s& 12\\ & & & \\ 12& 12&·s&0 bmatrix with blocks of equal size. So Bq⋆B_q is the graphon analogue of the family of balanced complete q-partite graphs, except that the off-diagonal blocks have value 12 12 instead of 11. Notation 4.2 (Balanced complete q-partite graphons). Define q⋆≔⋃1≤i,j≤qi≠jAi×Aj:A1,…,Aq⊆[0,1] are measurable,[0,1]=A1⊔⋯⊔Aq,λ⁡(Ai)=1q for every i∈[q].U_q \1_ _ subarrayc1≤ i,j≤ q\\ i≠ j subarrayA_i× A_j:\; array[]lA_1,…,A_q [0,1] are measurable,\\ [0,1]=A_1 ·s A_q,\\ λ(A_i)= 1q for every i∈[q] array \. These are the balanced complete q-partite 0,1\0,1\-valued graphons. By construction, Bq⋆=W∈:W=12Ualmost everywhere for some U∈q⋆.B_q = \W :\;W= 12\,U\ almost everywhere for some U _q \. Notation 4.3 (Canonical representative of Bq⋆B_q ). We fix one balanced partition of [0,1][0,1] by setting Aa≔[a−1q,aq)for a=1,…,q−1,Aq≔[q−1q,1].A_a [ a-1q, aq ) a=1,…,q-1, A_q [ q-1q,1 ]. Thus [0,1]=A1⊔⋯⊔Aq,λ⁡(Aa)=1qfor every a∈[q].[0,1]=A_1 ·s A_q, λ(A_a)= 1q every a∈[q]. Define the canonical element Wq⋆∈Bq⋆W_q ∈ B_q by Wq⋆(x,y)≔0,if x,y∈Aa for some a∈[q],12,if x∈Aa,y∈Ab for some distinct a,b∈[q].W_q (x,y) cases0,&if x,y∈ A_a for some a∈[q],\\[2.84526pt] 12,&if x∈ A_a,\ y∈ A_b for some distinct a,b∈[q]. cases Equivalently, Wq⋆=12 1⋃1≤a,b≤qa≠bAa×Ab.W_q = 12\,1_ _ subarrayc1≤ a,b≤ q\\ a≠ b subarrayA_a× A_b. Every graphon in Bq⋆B_q is equal almost everywhere to a relabeling of Wq⋆W_q . Indeed, suppose that V∈Bq⋆V∈ B_q corresponds to a balanced partition [0,1]=B1⊔⋯⊔Bq[0,1]=B_1 ·s B_q. For each i∈[q]i∈[q], both BiB_i and AiA_i are measurable subsets of [0,1][0,1] with Lebesgue measure 1/q1/q. Equip these sets with their normalized restricted Lebesgue measures. By [16, Cor. A.11], there is a measure-preserving bijection ϕi:Bi→Ai. _i:B_i→ A_i. Since the same normalization factor q is used on both sets, ϕi _i also preserves the original Lebesgue measure. Pasting ϕ1,…,ϕq _1,…, _q gives a measure-preserving bijection ϕ:[0,1]→[0,1]φ:[0,1]→[0,1] such that ϕ⁡(Bi)=Aiup to null sets for every i∈[q].φ(B_i)=A_i to null sets for every i∈[q]. Therefore V=(Wq⋆)ϕalmost everywhere.V=(W_q )^φ everywhere. In particular, δ□(V,Wq⋆)=0for every V∈Bq⋆. _ (V,W_q )=0 every V∈ B_q . Define W~q⋆≔π⁡(Wq⋆),B~q⋆≔π⁡(Bq⋆). W_q π(W_q ), B_q π(B_q ). Then B~q⋆=W~q⋆. B_q =\ W_q \. Consequently, for every graphon W, δ□(W,Bq⋆)=δ□(W,Wq⋆). _ (W,B_q )= _ (W,W_q ). Lemma 4.4. Fix r≥3r≥ 3 and set q=r−1q=r-1. Let U be a 0,1\0,1\-valued graphon and assume t⁡(Kr,U)=0.t(K_r,U)=0. Then ∫[0,1]2U⁡(x,y)xy≤1−1q. _[0,1]^2U(x,y)\,dx\,dy≤ 1- 1q. Moreover, equality holds if and only if δ□(U,q⋆)=0. _ (U,U_q )=0. Proof. This is the KrK_r-free case of the graphon Turán theorem; see [22, Cor. 16.11]. In the present notation, its equality case is exactly the condition δ□(U,q⋆)=0. _ (U,U_q )=0. ∎ Lemma 4.5 (Entropy maximizers among graphons of zero KrK_r-density). Fix r≥3r≥ 3 and set q=r−1q=r-1. Then supEnt⁡(W):t⁡(Kr,W)=0=ln⁡22(1−1q). \ (W):\ t(K_r,W)=0\= 22 (1- 1q ). A graphon W with t⁡(Kr,W)=0t(K_r,W)=0 attains this supremum if and only if δ□(W,Bq⋆)=0. _ (W,B_q )=0. Equivalently, the reduced maximizer set is the singleton B~q⋆=W~q⋆ B_q =\ W_q \. Remark 4.6. Lemma 4.5 can also be deduced from [9, Thm. 8.2]. In that theorem, take H=KrH=K_r and p=1/2p=1/2. Since χ⁡(Kr)=rχ(K_r)=r, the graphon g appearing there is the balanced (r−1)(r-1)-partite 0,1\0,1\-valued graphon. Hence pg=12gpg= 12g is a representative of the reduced class W~q⋆ W_q ; equivalently, π⁡(pg)=W~q⋆.π(pg)= W_q . The off-diagonal support of g has measure 1−1/q1-1/q. Therefore Ent⁡(12g)=ln⁡22(1−1q), ( 12g )= 22 (1- 1q ), which also gives the value of the constrained maximum. For p=1/2p=1/2, the Erdős-Rényi rate function I12I_ 12, defined in (5.9) below, satisfies I12(W)=ln⁡22−Ent⁡(W).I_ 12(W)= 22- (W). Thus minimizing I12I_ 12 under the constraint t⁡(Kr,W)=0t(K_r,W)=0 is the same as maximizing Ent⁡(W) (W) under the same constraint. We nevertheless give a direct proof below, using the graphon Turán theorem, because it is short and makes the equality cases explicit. Proof of Lemma 4.5. Let W be a graphon satisfying t⁡(Kr,W)=0.t(K_r,W)=0. Set S≔(x,y)∈[0,1]2:W⁡(x,y)>0,U≔S.S \(x,y)∈[0,1]^2:W(x,y)>0\, U 1_S. Since W is measurable and symmetric almost everywhere, the function U is also measurable and symmetric almost everywhere. Also, U only takes the values 00 and 11. Hence U is a graphon. We first show that U has zero KrK_r-density. By Remark 3.4, the integrand defining t⁡(Kr,W)t(K_r,W) is nonnegative. Since t⁡(Kr,W)=0t(K_r,W)=0, we have ∏1≤a<b≤rW⁡(xa,xb)=0 _1≤ a<b≤ rW(x_a,x_b)=0 for almost every (x1,…,xr)∈[0,1]r(x_1,…,x_r)∈[0,1]^r. If ∏1≤a<b≤rU⁡(xa,xb)=1, _1≤ a<b≤ rU(x_a,x_b)=1, then every factor U⁡(xa,xb)U(x_a,x_b) is equal to 11. By the definition of U, this means that every corresponding factor W⁡(xa,xb)W(x_a,x_b) is strictly positive. Thus ∏1≤a<b≤rW⁡(xa,xb)>0. _1≤ a<b≤ rW(x_a,x_b)>0. This can happen only on a null set. Therefore t⁡(Kr,U)=0.t(K_r,U)=0. We now bound the entropy of W. Since W=0W=0 on ScS^c and h⁡(0)=0h(0)=0, Definition 3.15 gives Ent⁡(W)=12∫Sh⁡(W⁡(x,y))xy. (W)= 12 _Sh(W(x,y))\,dx\,dy. By Lemma 3.16, we have h⁡(p)≤ln⁡2h(p)≤ 2 for every p∈[0,1]p∈[0,1]. Hence (4.1) Ent⁡(W)≤ln⁡22λ2(S)=ln⁡22∫[0,1]2U⁡(x,y)xy. (W)≤ 22λ^2(S)= 22 _[0,1]^2U(x,y)\,dx\,dy. Since U is a 0,1\0,1\-valued graphon and t⁡(Kr,U)=0t(K_r,U)=0, Lemma 4.4 gives (4.2) ∫[0,1]2U⁡(x,y)xy≤1−1q. _[0,1]^2U(x,y)\,dx\,dy≤ 1- 1q. Combining (4.1) and (4.2), we get Ent⁡(W)≤ln⁡22(1−1q). (W)≤ 22 (1- 1q ). Therefore supEnt⁡(W):t⁡(Kr,W)=0≤ln⁡22(1−1q). \ (W):t(K_r,W)=0\≤ 22 (1- 1q ). Next we show that this upper bound is attained. Consider the canonical graphon Wq⋆W_q from Notation 4.3. The graphon Wq⋆W_q has value 00 on the diagonal blocks and value 1/21/2 on the off-diagonal blocks. Since q=r−1q=r-1, any choice of r points in [0,1][0,1] contains two points in the same canonical block. For that pair, the corresponding factor in the KrK_r-integrand is 00. Hence (4.3) t⁡(Kr,Wq⋆)=0.t(K_r,W_q )=0. The diagonal blocks have total measure 1/q1/q, and the off-diagonal blocks have total measure 1−1/q1-1/q. Using Definition 3.15, together with h⁡(0)=0andh⁡(12)=ln⁡2,h(0)=0 h ( 12 )= 2, we obtain (4.4) Ent⁡(Wq⋆)=12(1−1q)h(12)=ln⁡22(1−1q). (W_q )= 12 (1- 1q )h ( 12 )= 22 (1- 1q ). Thus supEnt⁡(W):t⁡(Kr,W)=0=ln⁡22(1−1q). \ (W):t(K_r,W)=0\= 22 (1- 1q ). It remains to identify the graphons that attain this value. Suppose first that W is an entropy maximizer under the constraint t⁡(Kr,W)=0.t(K_r,W)=0. Use the same notation as above, S=(x,y)∈[0,1]2:W⁡(x,y)>0,U=S.S=\(x,y)∈[0,1]^2:W(x,y)>0\, U=1_S. Since W attains the value in (4.4), both inequalities (4.1) and (4.2) must be equalities. Equality in (4.2), by the equality case in Lemma 4.4, gives δ□(U,q⋆)=0. _ (U,U_q )=0. Equality in (4.1) gives h⁡(W⁡(x,y))=ln⁡2for almost every (x,y)∈S.h(W(x,y))= 2 almost every (x,y)∈ S. By Lemma 3.16, equality h⁡(p)=ln⁡2h(p)= 2 is possible only when p=1/2p=1/2. Hence W⁡(x,y)=12for almost every (x,y)∈S.W(x,y)= 12 almost every (x,y)∈ S. Also, by the definition of S, we have W=0W=0 almost everywhere on ScS^c. Therefore W=12Ualmost everywhere.W= 12\,U everywhere. By Notation 4.2, the family Bq⋆B_q consists exactly of the graphons 12V 12V with V∈q⋆V _q , up to almost-everywhere equality. Since δ□(U,q⋆)=0, _ (U,U_q )=0, we get δ□(12U,Bq⋆)=0. _ ( 12U,B_q )=0. Indeed, for every η>0η>0, choose Vη∈q⋆V_η _q such that δ□(U,Vη)<2η. _ (U,V_η)<2η. Then 12Vη∈Bq⋆ 12V_η∈ B_q , and by homogeneity of the cut norm, δ□(12U,12Vη)≤12δ□(U,Vη)<η. _ ( 12U, 12V_η )≤ 12\, _ (U,V_η)<η. Since W=12UW= 12U almost everywhere, it follows that δ□(W,Bq⋆)=0. _ (W,B_q )=0. Conversely, suppose that δ□(W,Bq⋆)=0. _ (W,B_q )=0. By Notation 4.3, this is equivalent to δ□(W,Wq⋆)=0. _ (W,W_q )=0. Using Lemma 3.14 and (4.3), we get t⁡(Kr,W)=t⁡(Kr,Wq⋆)=0.t(K_r,W)=t(K_r,W_q )=0. Using Lemma 3.17 and (4.4), we get Ent⁡(W)=Ent⁡(Wq⋆)=ln⁡22(1−1q). (W)= (W_q )= 22 (1- 1q ). Thus W satisfies the constraint t⁡(Kr,W)=0t(K_r,W)=0 and attains the maximum entropy. We have shown that the entropy maximizers are exactly the graphons W satisfying δ□(W,Bq⋆)=0. _ (W,B_q )=0. Finally, Notation 4.3 gives B~q⋆=W~q⋆, B_q =\ W_q \, so the reduced maximizer set is the singleton W~q⋆\ W_q \. ∎ Remark 4.7. By Lemma 3.18, the reduced mass of G∈nG _n is exp⁡(−r!wKr(G))=exp⁡(−n2Lnt(Kr,WG)),Ln≔wnr−2. (-r!\,w\,K_r(G) )= (-n^2L_n\,t(K_r,W_G) ), L_n wn^r-2. The corresponding graphon functional is therefore Tn(W)=−Lnt(Kr,W).T_n(W)=-L_n\,t(K_r,W). For fixed L>0L>0, let ℱ~L⋆≔π⁡(argmaxW∈⁡Ent⁡(W)−Lt(Kr,W)). F_L π ( *arg\,max_W \ (W)-L\,t(K_r,W) \ ). For the ERGM with zero edge coefficient and clique coefficient −L-L, [9, Thm. 3.2] gives exponential concentration around ℱ~L⋆ F_L . The concentration rate is not given uniformly in L. Moreover, [9, Thm. 7.1] gives limL→∞supW~∈ℱ~L⋆d□(W~,W~q⋆)=0. _L→∞ _ W∈ F_L d_ ( W, W_q )=0. These results describe an iterated limit in which one first lets n→∞n→∞ with L fixed and then lets L→∞L→∞. In the fixed-weight MLN considered here, Ln=wnr−2,limn→∞Ln=+∞.L_n=wn^r-2, _n→∞L_n=+∞. Thus n and LnL_n grow together. Since the concentration rate for fixed L is not uniform in L, the fixed-coefficient theorem does not directly give a bound of the form e−cn2e^-cn^2 with c>0c>0 independent of n along this sequence. 4.2. Entropy gap away from the maximizers The next two lemmas show that once we stay a fixed cut distance away from the reduced maximizer class represented by Bq⋆B_q , the entropy drops. Lemma 4.8. Fix r≥3r≥ 3 and set q=r−1q=r-1. For every ε>0 >0 there exists γr(ε)>0 _r( )>0 such that the following holds. If U is a 0,1\0,1\-valued graphon and satisfies t⁡(Kr,U)=0,δ□(U,q⋆)≥ε,t(K_r,U)=0, _ (U,U_q )≥ , then ∫[0,1]2U≤(1−1q)−γr(ε). _[0,1]^2U≤ (1- 1q )- _r( ). Proof. Fix ε>0 >0 and define mε≔sup∫[0,1]2U:U is a 0,1-valued graphon,t⁡(Kr,U)=0,δ□(U,q⋆)≥ε.m_ \ _[0,1]^2U: array[]lU is a $\0,1\$-valued graphon,\\ t(K_r,U)=0,\\ _ (U,U_q )≥ array \. If the set inside the supremum is empty, take γr(ε)=12(1−1q). _r( )= 12 (1- 1q ). The conclusion then holds automatically. Hence assume that the set is nonempty. By Lemma 4.4, mε≤1−1q.m_ ≤ 1- 1q. We claim that the inequality is strict. Assume instead that mε=1−1q.m_ =1- 1q. By the definition of the supremum, there exists a sequence (Un)(U_n) of 0,1\0,1\-valued graphons such that t⁡(Kr,Un)=0,δ□(Un,q⋆)≥ε,limn→∞∫[0,1]2Un=1−1q.t(K_r,U_n)=0, _ (U_n,U_q )≥ , _n→∞ _[0,1]^2U_n=1- 1q. Let U~n∈~ U_n∈ W be the equivalence class of UnU_n. By Notation 3.8, the metric space (~,d□)( W,d_ ) is compact; see [22, Thm. 9.23]. Hence, after passing to a subsequence, we may assume that limn→∞d□(U~n,U~)=0 _n→∞d_ ( U_n, U)=0 for some U~∈~ U∈ W. Choose any representative U∈U~U∈ U. Since the metric on ~ W is induced by δ□ _ , this means exactly that limn→∞δ□(Un,U)=0. _n→∞ _ (U_n,U)=0. By Lemma 3.14, the map t⁡(Kr,⋅)t(K_r,·) is continuous with respect to cut distance. Therefore limn→∞t⁡(Kr,Un)=t⁡(Kr,U)=0. _n→∞t(K_r,U_n)=t(K_r,U)=0. Also, the limit still stays at least ε away from q⋆U_q . Indeed, δ□(U,q⋆)≥δ□(Un,q⋆)−δ□(Un,U), _ (U,U_q )≥ _ (U_n,U_q )- _ (U_n,U), and letting n→∞n→∞ gives (4.5) δ□(U,q⋆)≥ε. _ (U,U_q )≥ . We also need the edge density to pass to the limit. For graphons W and V, and for any measure-preserving bijection ϕφ, ∫[0,1]2V=∫[0,1]2Vϕ _[0,1]^2V= _[0,1]^2V^φ by a change of variables. Therefore |∫[0,1]2(W−V)|=|∫[0,1]2(W−Vϕ)|. | _[0,1]^2(W-V) |= | _[0,1]^2(W-V^φ) |. By Definition 3.5, we may choose S=T=[0,1]S=T=[0,1] in the supremum defining the cut norm, so |∫[0,1]2(W−Vϕ)|≤‖W−Vϕ‖□. | _[0,1]^2(W-V^φ) |≤\|W-V^φ\|_ . Taking the infimum over all measure-preserving bijections ϕφ gives |∫[0,1]2(W−V)|≤δ□(W,V). | _[0,1]^2(W-V) |≤ _ (W,V). Apply this to (W,V)=(Un,U)(W,V)=(U_n,U) and let n→∞n→∞: (4.6) ∫[0,1]2U=limn→∞∫[0,1]2Un=1−1q. _[0,1]^2U= _n→∞ _[0,1]^2U_n=1- 1q. Now define the positivity set of U by S≔(x,y)∈[0,1]2:U⁡(x,y)>0,V≔S.S \(x,y)∈[0,1]^2:\ U(x,y)>0\, V 1_S. The function V is measurable, 0,1\0,1\-valued, and symmetric almost everywhere; hence it is a graphon. Moreover, 0≤U≤V≤1.0≤ U≤ V≤ 1. We show first that V is a graphon of zero KrK_r-density. If ∏1≤a<b≤rV⁡(xa,xb)=1, _1≤ a<b≤ rV(x_a,x_b)=1, then each factor U⁡(xa,xb)U(x_a,x_b) is strictly positive, so ∏1≤a<b≤rU⁡(xa,xb)>0. _1≤ a<b≤ rU(x_a,x_b)>0. But the integrand defining t⁡(Kr,U)t(K_r,U) is nonnegative and has integral 00. So this can happen only on a set of measure 00. Hence t⁡(Kr,V)=0.t(K_r,V)=0. Because U≤VU≤ V, equation (4.6) gives ∫[0,1]2V≥∫[0,1]2U=1−1q. _[0,1]^2V≥ _[0,1]^2U=1- 1q. On the other hand, V is a 0,1\0,1\-valued graphon of zero KrK_r-density, so Lemma 4.4 gives ∫[0,1]2V≤1−1q. _[0,1]^2V≤ 1- 1q. Thus ∫[0,1]2V=1−1q. _[0,1]^2V=1- 1q. By the equality case in Lemma 4.4, this implies δ□(V,q⋆)=0. _ (V,U_q )=0. Finally, V−U≥0V-U≥ 0 pointwise and ∫[0,1]2(V−U)=∫[0,1]2V−∫[0,1]2U=0. _[0,1]^2(V-U)= _[0,1]^2V- _[0,1]^2U=0. A nonnegative integrable function with integral 00 is zero almost everywhere. So U=Valmost everywhere.U=V everywhere. Therefore δ□(U,q⋆)=0, _ (U,U_q )=0, contradicting the earlier bound δ□(U,q⋆)≥ε _ (U,U_q )≥ in (4.5). This contradiction shows that mε<1−1q.m_ <1- 1q. Now define γr(ε)≔(1−1q)−mε>0. _r( ) (1- 1q )-m_ >0. This is exactly the desired gap. ∎ Lemma 4.9 (Entropy gap away from Bq⋆B_q ). Fix r≥3r≥ 3 and set q=r−1q=r-1. For every ε>0 >0 there exists cr,ε>0c_r, >0 such that every graphon W satisfying t⁡(Kr,W)=0,δ□(W,Bq⋆)≥εt(K_r,W)=0, _ (W,B_q )≥ also satisfies Ent⁡(W)≤ln⁡22(1−1q)−cr,ε. (W)≤ 22 (1- 1q )-c_r, . Proof. Fix ε>0 >0 and let W be a graphon with t⁡(Kr,W)=0,δ□(W,Bq⋆)≥ε.t(K_r,W)=0, _ (W,B_q )≥ . As before, set S≔(x,y)∈[0,1]2:W⁡(x,y)>0,U≔S.S \(x,y)∈[0,1]^2:\ W(x,y)>0\, U 1_S. The function U is measurable, 0,1\0,1\-valued, and symmetric almost everywhere; hence it is a graphon. Since t⁡(Kr,W)=0t(K_r,W)=0, Remark 3.4 implies that ∏1≤a<b≤rW⁡(xa,xb)=0 _1≤ a<b≤ rW(x_a,x_b)=0 for almost every (x1,…,xr)∈[0,1]r(x_1,…,x_r)∈[0,1]^r. If ∏1≤a<b≤rU⁡(xa,xb)=1, _1≤ a<b≤ rU(x_a,x_b)=1, then every factor W⁡(xa,xb)W(x_a,x_b) is strictly positive, and therefore ∏1≤a<b≤rW⁡(xa,xb)>0. _1≤ a<b≤ rW(x_a,x_b)>0. This can happen only on a null set. Hence t⁡(Kr,U)=0.t(K_r,U)=0. Moreover, W=0W=0 on ScS^c, while h⁡(u)≤ln⁡2h(u)≤ 2 for every u∈[0,1]u∈[0,1]. Therefore Ent⁡(W)=12∫Sh⁡(W⁡(x,y))xy≤ln⁡22λ2(S)=ln⁡22∫[0,1]2U. (W)= 12 _Sh(W(x,y))\,dx\,dy≤ 22λ^2(S)= 22 _[0,1]^2U. We now split into two cases. Case 1: δ□(U,q⋆)≥ε/2 _ (U,U_q )≥ /2. Then Lemma 4.8 gives ∫[0,1]2U≤(1−1q)−γr(ε/2). _[0,1]^2U≤ (1- 1q )- _r( /2). Hence Ent⁡(W)≤ln⁡22(1−1q)−ln⁡22γr(ε/2). (W)≤ 22 (1- 1q )- 22\, _r( /2). Thus, in Case 1, the claimed bound holds with entropy loss ln⁡22γr(ε/2) 22 _r( /2). Case 2: δ□(U,q⋆)<ε/2 _ (U,U_q )< /2. Choose U⋆∈q⋆U _q such that δ□(U,U⋆)<ε2. _ (U,U )< 2. Set V⋆≔12U⋆.V 12\,U . By Notation 4.2, the family Bq⋆B_q consists exactly of graphons that are equal almost everywhere to 12U 12U for some U∈q⋆U _q . Since U⋆∈q⋆U _q and V⋆=12U⋆V = 12U , it follows that V⋆∈Bq⋆V ∈ B_q . Since δ□(W,Bq⋆)≥ε _ (W,B_q )≥ , we have δ□(W,V⋆)≥ε. _ (W,V )≥ . Also, by homogeneity of the cut distance, δ□(12U,V⋆)=δ□(12U,12U⋆)=12δ□(U,U⋆)<ε4. _ ( 12U,V )= _ ( 12U, 12U )= 12\, _ (U,U )< 4. So the triangle inequality gives δ□(W,12U)≥δ□(W,V⋆)−δ□(12U,V⋆)>3ε4. _ (W, 12U )≥ _ (W,V )- _ ( 12U,V )> 3 4. Since δ□(W,12U)≤‖W−12U‖□≤‖W−12U‖1, _ (W, 12U )≤ \|W- 12U \|_ ≤ \|W- 12U \|_1, it follows that ‖W−12U‖1>3ε4. \|W- 12U \|_1> 3 4. Because U=SU=1_S and W=0W=0 on ScS^c, this means ∫S|W−12|>3ε4. _S |W- 12 |> 3 4. Since U is 0,1\0,1\-valued and is a graphon of zero KrK_r-density, Lemma 4.4 gives λ2(S)=∫[0,1]2U≤1−1q.λ^2(S)= _[0,1]^2U≤ 1- 1q. By Lemma 3.12(i), (∫S|W−12|)2≤λ2(S)∫S(W−12)2. ( _S |W- 12 | )^2≤λ^2(S) _S (W- 12 )^2. Therefore ∫S(W−12)2≥(3ε4)21−1q. _S (W- 12 )^2≥ ( 3 4 )^21- 1q. For every (x,y)∈S(x,y)∈ S, we also have W⁡(x,y)∈[0,1]W(x,y)∈[0,1]. Hence Lemma 3.16 gives h⁡(W⁡(x,y))≤ln⁡2−2(W⁡(x,y)−12)2for every (x,y)∈S.h(W(x,y))≤ 2-2 (W(x,y)- 12 )^2 every (x,y)∈ S. Using this inequality in the entropy identity above, we obtain Ent⁡(W) (W) ≤12∫S(ln⁡2−2(W⁡(x,y)−12)2)xy ≤ 12 _S ( 2-2 (W(x,y)- 12 )^2 )\,dx\,dy =ln⁡22λ2(S)−∫S(W⁡(x,y)−12)2xy = 22\,λ^2(S)- _S (W(x,y)- 12 )^2\,dx\,dy ≤ln⁡22(1−1q)−916ε2(1−1q). ≤ 22 (1- 1q )- 916 ^2(1- 1q). Here the last inequality uses the two estimates already proved above: λ2(S)≤1−1qand∫S(W⁡(x,y)−12)2xy≥916ε2(1−1q).λ^2(S)≤ 1- 1q _S (W(x,y)- 12 )^2\,dx\,dy≥ 916 ^2(1- 1q). Combine the two cases and define cr,ε≔min⁡ln⁡22γr(ε/2),916ε2(1−1q)>0.c_r, \ 22\, _r( /2), 916 ^2(1- 1q) \>0. Then Ent⁡(W)≤ln⁡22(1−1q)−cr,ε. (W)≤ 22 (1- 1q )-c_r, . ∎ The graphon removal lemma in [14, Lem. 2.3] is stated with the strict assumption t⁡(Kr,W)<δt(K_r,W)<δ. We will use the following non-strict version, obtained by applying that lemma with a smaller threshold. Lemma 4.10 (Graphon KrK_r removal). Fix r≥3r≥ 3. For every η>0η>0 there exists δ=δKr(η)>0δ= _K_r(η)>0 such that whenever a graphon W satisfies t⁡(Kr,W)≤δ,t(K_r,W)≤δ, there exists a graphon W′W with t⁡(Kr,W′)=0,‖W−W′‖1≤η.t(K_r,W )=0, \|W-W \|_1≤η. Proof. Apply [14, Lem. 2.3] with F=KrF=K_r and error η. This gives a number δ0>0 _0>0 such that, whenever t⁡(Kr,W)<δ0,t(K_r,W)< _0, there is a graphon W′W satisfying t⁡(Kr,W′)=0and‖W−W′‖1≤η.t(K_r,W )=0 \|W-W \|_1≤η. Now define δKr(η)≔δ02. _K_r(η) _02. If t⁡(Kr,W)≤δKr(η)t(K_r,W)≤ _K_r(η), then t⁡(Kr,W)≤δ02<δ0.t(K_r,W)≤ _02< _0. Thus W satisfies the strict hypothesis of [14, Lem. 2.3], applied with F=KrF=K_r and error η. Hence there exists a graphon W′W such that t⁡(Kr,W′)=0and‖W−W′‖1≤η.t(K_r,W )=0 \|W-W \|_1≤η. This is the required graphon. ∎ Lemma 4.11 (Entropy is continuous in L1L^1). For graphons U and V, and for every α>0α>0, (4.7) |Ent⁡(U)−Ent⁡(V)|≤12ω(α)+ln⁡22‖U−V‖1α,| (U)- (V)|≤ 12\,ω(α)+ 22\, \|U-V\|_1α, where ω(α)≔sup|h(x)−h(y)|:x,y∈[0,1],|x−y|≤α.ω(α) \|h(x)-h(y)|:\ x,y∈[0,1],\ |x-y|≤α\. In particular, Ent is uniformly continuous on W with respect to ∥⋅∥1\|·\|_1. For every τ>0τ>0 there exists η>0η>0 such that, for all graphons U and V, ‖U−V‖1≤η⟹|Ent⁡(U)−Ent⁡(V)|≤τ.\|U-V\|_1≤η | (U)- (V)|≤τ. Proof. Fix α>0α>0 and define the two sets A≔(x,y)∈[0,1]2:|U⁡(x,y)−V⁡(x,y)|≤α,A \(x,y)∈[0,1]^2:\ |U(x,y)-V(x,y)|≤α\, B≔(x,y)∈[0,1]2:|U⁡(x,y)−V⁡(x,y)|>α.B \(x,y)∈[0,1]^2:\ |U(x,y)-V(x,y)|>α\. Then |Ent⁡(U)−Ent⁡(V)| | (U)- (V)| =12|∫[0,1]2(h⁡(U)−h⁡(V))| = 12 | _[0,1]^2(h(U)-h(V)) | ≤12∫A|h⁡(U)−h⁡(V)|+12∫B|h⁡(U)−h⁡(V)|. ≤ 12 _A|h(U)-h(V)|+ 12 _B|h(U)-h(V)|. On the set A we have |h⁡(U)−h⁡(V)|≤ω⁡(α),|h(U)-h(V)|≤ω(α), so ∫A|h⁡(U)−h⁡(V)|≤ω⁡(α). _A|h(U)-h(V)|≤ω(α). On the set B we use only the bound 0≤h≤ln⁡20≤ h≤ 2, and since B⊆[0,1]2B [0,1]^2, we get ∫B|h⁡(U)−h⁡(V)|≤(ln⁡2)λ2(B). _B|h(U)-h(V)|≤( 2)\,λ^2(B). Also, since |U−V|>α|U-V|>α on B, ‖U−V‖1≥αλ2(B),soλ2(B)≤‖U−V‖1α.\|U-V\|_1≥α\,λ^2(B), λ^2(B)≤ \|U-V\|_1α. Putting these estimates together yields (4.7). Finally, h is uniformly continuous on the compact interval [0,1][0,1], and therefore limα→0ω⁡(α)=0. _α→ 0ω(α)=0. Fix τ>0τ>0. Choose α>0α>0 such that 12ω(α)≤τ2, 12\,ω(α)≤ τ2, and then choose η>0η>0 such that ln⁡22ηα≤τ2. 22\, ηα≤ τ2. If ‖U−V‖1≤η\|U-V\|_1≤η, then (4.7) gives |Ent⁡(U)−Ent⁡(V)|≤τ.| (U)- (V)|≤τ. This proves the uniform continuity statement. ∎ Lemma 4.12. Fix r≥3r≥ 3 and set q=r−1q=r-1. For every ε>0 >0 there exist δr,ε>0 _r, >0 and cr,ε′>0c _r, >0 such that every graphon W satisfying t⁡(Kr,W)≤δr,εandδ□(W,Bq⋆)≥ε,t(K_r,W)≤ _r, _ (W,B_q )≥ , also satisfies Ent⁡(W)≤ln⁡22(1−1q)−cr,ε′. (W)≤ 22 (1- 1q )-c _r, . Proof. Fix ε>0 >0. Apply Lemma 4.9 with ε/2 /2. This gives a constant cr,ε/2>0c_r, /2>0 such that every V that is a graphon of zero KrK_r-density and satisfies δ□(V,Bq⋆)≥ε2 _ (V,B_q )≥ 2 satisfies Ent⁡(V)≤ln⁡22(1−1q)−cr,ε/2. (V)≤ 22 (1- 1q )-c_r, /2. Choose η>0η>0 so small that η≤ε2η≤ 2 and supU,V∈‖U−V‖1≤η|Ent⁡(U)−Ent⁡(V)|≤12cr,ε/2. _ subarraycU,V \\ \|U-V\|_1≤η subarray| (U)- (V)|≤ 12\,c_r, /2. This is possible by Lemma 4.11. Now apply Lemma 4.10 with this η. We obtain δr,ε>0 _r, >0 such that every graphon W with t⁡(Kr,W)≤δr,εt(K_r,W)≤ _r, admits a graphon W′W of zero KrK_r-density satisfying ‖W−W′‖1≤η.\|W-W \|_1≤η. Suppose that t⁡(Kr,W)≤δr,εandδ□(W,Bq⋆)≥ε.t(K_r,W)≤ _r, _ (W,B_q )≥ . Choose a corresponding graphon W′W such that ‖W−W′‖1≤η\|W-W \|_1≤η. Since δ□(W,W′)≤‖W−W′‖□≤‖W−W′‖1≤η, _ (W,W )≤\|W-W \|_ ≤\|W-W \|_1≤η, the triangle inequality gives δ□(W′,Bq⋆)≥δ□(W,Bq⋆)−δ□(W,W′)≥ε−η≥ε2. _ (W ,B_q )≥ _ (W,B_q )- _ (W,W )≥ -η≥ 2. So Lemma 4.9 implies Ent⁡(W′)≤ln⁡22(1−1q)−cr,ε/2. (W )≤ 22 (1- 1q )-c_r, /2. Also, |Ent⁡(W)−Ent⁡(W′)|≤12cr,ε/2| (W)- (W )|≤ 12\,c_r, /2 by our choice of η. Therefore Ent⁡(W)≤Ent⁡(W′)+12cr,ε/2≤ln⁡22(1−1q)−12cr,ε/2. (W)≤ (W )+ 12\,c_r, /2≤ 22 (1- 1q )- 12\,c_r, /2. Thus the lemma holds with cr,ε′≔12cr,ε/2>0.c _r, 12\,c_r, /2>0. ∎ 5. Proof of Theorem 2.7 Recall that we have fixed r≥3r≥ 3 and w>0w>0 and we continue to let q:=r−1q:=r-1. We first prove some technical results in sections 5.1 – 5.3. Then we prove parts (i), (i), and (i) of Theorem 2.7, in this order, in sections 5.4 – 5.7. Notation 5.1 (Balanced q-partite entropy level). We write (5.1) sq≔ln⁡22(1−1q).s_q 22 (1- 1q ). Corollary 2.6 shows that the graph-independent factor ewnre^wn^r disappears after normalization. Thus the probability measure ℙn,rP_n,r is determined by the reduced masses exp⁡(−r!wKr(G)),G∈n. (-r!\,w\,K_r(G) ), G _n. By Lemma 3.18, t⁡(Kr,WG)=r!Kr(G)nr.t(K_r,W_G)= r!\,K_r(G)n^r. Consequently, (5.2) exp⁡(−r!wKr(G))=exp⁡(−wt(Kr,WG)nr). (-r!\,w\,K_r(G) )= (-w\,t(K_r,W_G)n^r ). This identity connects the finite-graph penalty with the graphon arguments in this section. 5.1. A general vanishing lemma The next lemma records the counting estimate that the graphon KrK_r-homomorphism density t⁡(Kr,Wn)=r!Kr(n)/nrt(K_r,W_ G_n)=r!\,K_r( G_n)/n^r goes to zero in probability for every fixed r≥3r≥ 3 and every fixed w>0w>0, where n∼ℙn,r G_n _n,r. Lemma 5.2. Fix r≥3r≥ 3 and w>0w>0. For every ε>0 >0 and every n∈ℕn , define n,ε(r)≔G∈n:Kr(G)≥εnr.A_n, ^(r) \\,G _n:\ K_r(G)≥ n^r\,\. Then ℙn,r(n,ε(r))≤|n|e−r!wεnr=exp⁡((n2)ln⁡2−r!wεnr).P_n,r (A_n, ^(r) )≤|G_n|\,e^-r!\,w\, n^r= ( n2 2-r!\,w\, n^r ). In particular, for every ε>0 >0, limn→∞ℙn,r(n,ε(r))=0. _n→∞P_n,r (A_n, ^(r) )=0. Equivalently, if n∼ℙn,r G_n _n,r, then for every δ>0δ>0, limn→∞ℙ⁡(t⁡(Kr,Wn)≥δ)=0, _n→∞P (t(K_r,W_ G_n)≥δ )=0, because this event is n∈n,δ/r!(r)\ G_n _n,δ/r!^(r)\. Thus t⁡(Kr,Wn)t(K_r,W_ G_n) converges to 00 in probability. Proof. By (2.3), ℙn,r(G)=e−r!wKr(G)Z~n,r.P_n,r(G)= e^-r!\,w\,K_r(G) Z_n,r. The denominator is at least 11, because a graph with no edges has no copy of KrK_r and contributes 11. So for every event ⊆nA _n, ℙn,r()=∑G∈ℙn,r(G)≤∑G∈e−r!wKr(G).P_n,r(A)= _G P_n,r(G)≤ _G e^-r!\,w\,K_r(G). Apply this with =n,ε(r)A=A_n, ^(r). On this event we have Kr(G)≥εnrK_r(G)≥ n^r, hence ℙn,r(n,ε(r))≤|n,ε(r)|e−r!wεnr≤|n|e−r!wεnr.P_n,r (A_n, ^(r) )≤|A_n, ^(r)|\,e^-r!\,w\, n^r≤|G_n|\,e^-r!\,w\, n^r. Since |n|=2(n2)|G_n|=2 n2, we have |n|e−r!wεnr=exp⁡((n2)ln⁡2−r!wεnr).|G_n|\,e^-r!\,w\, n^r= ( n2 2-r!\,w\, n^r ). Because r≥3r≥ 3, the term −r!wεnr-r!\,w\, n^r is of strictly higher order than (n2)ln⁡2=O⁡(n2) n2 2=O(n^2), so the exponent has limit −∞-∞. ∎ 5.2. Graphs with a fixed positive clique density A fixed positive lower bound on t⁡(Kr,WG)t(K_r,W_G) gives a negative term of order nrn^r in the exponent. The total number of labeled graphs is only exp⁡(O⁡(n2)) (O(n^2)). Since r≥3r≥ 3, the penalty is stronger than this counting term. Lemma 5.3 (Fixed positive clique density is negligible). Fix 0<δ≤10<δ≤ 1. For every M>0M>0, there exists N=N⁡(M,δ,r,w)N=N(M,δ,r,w) such that, for every n≥Nn≥ N, (5.3) ∑G∈nt⁡(Kr,WG)≥δexp⁡(−r!wKr(G))≤exp⁡(−Mn2). _ subarraycG _n\\ t(K_r,W_G)≥δ subarray (-r!\,w\,K_r(G) )≤ (-Mn^2). Proof. If t⁡(Kr,WG)≥δt(K_r,W_G)≥δ, then (5.2) gives exp⁡(−r!wKr(G))≤exp⁡(−wδnr). (-r!\,w\,K_r(G) )≤ (-wδ n^r). Since |n|=2(n2)|G_n|=2 n2, the total contribution of graphs satisfying t⁡(Kr,WG)≥δt(K_r,W_G)≥δ is bounded by (5.4) ∑G∈nt⁡(Kr,WG)≥δexp⁡(−r!wKr(G))≤exp⁡(En), _ subarraycG _n\\ t(K_r,W_G)≥δ subarray (-r!\,w\,K_r(G) )≤ (E_n), where (5.5) En≔(n2)ln⁡2−wδnr.E_n n2 2-wδ n^r. We now compare EnE_n with the n2n^2 scale. By (5.5), Enn2=(n2)n2ln⁡2−wδnr−2. E_nn^2= n2n^2 2-wδ n^r-2. Since (n2)n2=n⁡(n−1)2n2=12−12n, n2n^2= n(n-1)2n^2= 12- 12n, we get (5.6) Enn2=ln⁡22−ln⁡22n−wδnr−2. E_nn^2= 22- 22n-wδ n^r-2. Because r≥3r≥ 3 and wδ>0wδ>0, limn→∞(ln⁡22−ln⁡22n−wδnr−2)=−∞. _n→∞ ( 22- 22n-wδ n^r-2 )=-∞. Therefore, by (5.6), there is N=N⁡(M,δ,r,w)N=N(M,δ,r,w) such that, for every n≥Nn≥ N, Enn2≤−M. E_nn^2≤-M. Equivalently, En≤−Mn2.E_n≤-Mn^2. Combining this with (5.4), we obtain, for every n≥Nn≥ N, ∑G∈nt⁡(Kr,WG)≥δexp⁡(−r!wKr(G))≤exp⁡(En)≤exp⁡(−Mn2). _ subarraycG _n\\ t(K_r,W_G)≥δ subarray (-r!\,w\,K_r(G) )≤ (E_n)≤ (-Mn^2). This proves the lemma. ∎ Thus graphs with t⁡(Kr,WG)≥δt(K_r,W_G)≥δ have negligible total reduced mass on the n2n^2 scale, for every fixed δ>0δ>0. The main contribution must come from graphs with small empirical KrK_r-density. Lemma 4.5 identifies the largest entropy at zero KrK_r-density, and Lemma 4.12 gives a strict entropy loss away from Bq⋆B_q when the KrK_r-density is sufficiently small. 5.3. Counting cut-closed families We next convert entropy bounds for graphons into counting bounds for labeled graphs. Definition 5.4 (Cut-closed family of graphons). A family ℱ⊆F is called cut-closed if, whenever Wm∈ℱW_m for every m and limm→∞δ□(Wm,W)=0, _m→∞ _ (W_m,W)=0, then W∈ℱW . Lemma 5.5. Let ℱ⊆F be cut-closed, and let ℱ~ F be its image in ~ W. Then the following statements hold. (1) If W∈ℱW , V∈V , and δ□(W,V)=0 _ (W,V)=0, then V∈ℱV . (2) For every n∈ℕn and every G∈nG _n, WG∈ℱ⟺W~G∈ℱ~.W_G W_G∈ F. (3) The set ℱ~ F is closed in the metric d□d_ . Proof. For the first statement, take the constant sequence Wm=W_m=W. Then limm→∞δ□(Wm,V)=0, _m→∞ _ (W_m,V)=0, so cut-closedness gives V∈ℱV . The forward implication in the second statement follows from the definition of ℱ~ F. Conversely, suppose that W~G∈ℱ~ W_G∈ F. Then some V∈ℱV satisfies δ□(WG,V)=0 _ (W_G,V)=0. The first statement gives WG∈ℱW_G . For the third statement, let W~m∈ℱ~ W_m∈ F and suppose that limm→∞d□(W~m,W~)=0. _m→∞d_ ( W_m, W)=0. Choose a representative W of W~ W. For each m, choose a representative Vm∈ℱV_m of W~m W_m. By the definition of d□d_ , δ□(Vm,W)=d□(W~m,W~). _ (V_m,W)=d_ ( W_m, W). Hence limm→∞δ□(Vm,W)=0. _m→∞ _ (V_m,W)=0. Cut-closedness gives W∈ℱW , and therefore W~∈ℱ~ W∈ F. ∎ Notation 5.6 (Uniform measure on labeled graphs). For each n∈ℕn , let ℙnunifP_n^unif be the uniform probability measure on nG_n. Since nG_n contains 2(n2)2 n2 graphs, we have (5.7) ℙnunif(A)=2−(n2)|A|,A⊆n.P_n^unif(A)=2^- n2|A|, A _n. We consider nG_n as a probability space equipped with ℙnunifP_n^unif, and let n R_n be the canonical random graph on this space; thus n(G)=Gfor every G∈n. R_n(G)=G every G _n. Equivalently, each possible edge is present independently with probability 12 12. Hence n∼G⁡(n,12). R_n G (n, 12 ). For every ~⊆~ A W, the event W~n∈~ W_ R_n∈ A consists exactly of the graphs whose empirical graphon class belongs to ~ A. Hence (5.8) ℙnunif(W~n∈~)=ℙnunif(G∈n:W~G∈~).P_n^unif ( W_ R_n∈ A )=P_n^unif (\G _n: W_G∈ A\ ). Theorem 5.7. For a graphon W∈W , define (5.9) I12(W)≔12∫[0,1]2[Wln⁡(2W)+(1−W)ln⁡(2(1−W))]xy,I_ 12(W) 12 _[0,1]^2 [W (2W)+(1-W) (2(1-W) ) ]\,dx\,dy, where 0ln⁡0=00 0=0. The functional I12I_ 12 is constant on zero-cut-distance classes. Thus, if W~=π⁡(W) W=π(W), then I12(W~)≔I12(W)I_ 12( W) I_ 12(W) is well-defined. Moreover, (5.10) I12(W~)=ln⁡22−Ent⁡(W~).I_ 12( W)= 22- ( W). If ℱ~⊆~ F W is closed, then (5.11) lim supn→∞1n2lnℙnunif(G∈n:W~G∈ℱ~)≤−infW~∈ℱ~I12(W~). _n→∞ 1n^2 _n^unif ( \G _n: W_G∈ F \ )≤- _ W∈ FI_ 12( W). Here inf∅=+∞ =+∞, sup∅=−∞ =-∞, and ln⁡0=−∞ 0=-∞. Proof. Recall that the binary entropy function is defined by h⁡(u)=−uln⁡u−(1−u)ln⁡(1−u),u∈[0,1],h(u)=-u u-(1-u) (1-u), u∈[0,1], with the convention 0ln⁡0=00 0=0. For 0<u<10<u<1, we have uln⁡(2u)+(1−u)ln⁡(2(1−u)) u (2u)+(1-u) (2(1-u) ) =u⁡(ln⁡2+ln⁡u)+(1−u)(ln⁡2+ln⁡(1−u)) =u ( 2+ u )+(1-u) ( 2+ (1-u) ) =(u+(1−u))ln⁡2+uln⁡u+(1−u)ln⁡(1−u) = (u+(1-u) ) 2+u u+(1-u) (1-u) =ln⁡2−h⁡(u). = 2-h(u). The same identity holds for u=0u=0 and u=1u=1 under the convention 0ln⁡0=00 0=0. Hence it holds for every u∈[0,1]u∈[0,1]. Integrating this identity gives I12(W)=ln⁡22−Ent⁡(W).I_ 12(W)= 22- (W). By Lemma 3.17, entropy is unchanged under zero cut distance. Hence I12I_ 12 is also unchanged under zero cut distance, so I12(W~)I_ 12( W) is well-defined and (5.10) follows. Under the measure ℙnunifP_n^unif from Notation 5.6, the random graph n R_n has distribution G⁡(n,12)G(n, 12). We may therefore apply [10, Thm. 2.3] with p=12p= 12. The graphon associated with a finite graph in [10, Eq. (4)] agrees almost everywhere with the empirical graphon from Definition 3.2. By Remark 3.9, the reduced graphon space used here is the same reduced cut-metric space as the one used in [10]. Finally, for p=12p= 12, the rate function in [10, Eq. (7)] is exactly (5.9). The closed-set upper bound in [10, Thm. 2.3], together with (5.8), therefore gives (5.11). ∎ Lemma 5.8. Let ℱ~⊆~ F W be closed. For every n∈ℕn , (5.12) ℙnunif(G∈n:W~G∈ℱ~) _n^unif ( \G _n: W_G∈ F \ ) =2−(n2)|G∈n:W~G∈ℱ~|. =2^- n2 | \G _n: W_G∈ F \ |. Consequently, (5.13) lim supn→∞1n2ln⁡|G∈n:W~G∈ℱ~|≤supW~∈ℱ~Ent⁡(W~). _n→∞ 1n^2 | \G _n: W_G∈ F \ |≤ _ W∈ F ( W). If ℱ~≠∅ F≠ , then for every γ>0γ>0 there is N=N⁡(ℱ~,γ)N=N( F,γ) such that, for every n≥Nn≥ N, (5.14) |G∈n:W~G∈ℱ~|≤exp⁡([supW~∈ℱ~Ent⁡(W~)+γ]n2). | \G _n: W_G∈ F \ |≤ ( [ _ W∈ F ( W)+γ ]n^2 ). Proof. Equation (5.12) follows immediately from the definition (5.7). Set Nn(ℱ~)≔|G∈n:W~G∈ℱ~|.N_n( F) | \G _n: W_G∈ F \ |. Using (5.12), with ln⁡0=−∞ 0=-∞ when Nn(ℱ~)=0N_n( F)=0, we obtain 1n2lnNn(ℱ~)=(n2)n2ln2+1n2lnℙnunif(G∈n:W~G∈ℱ~). 1n^2 N_n( F)= n2n^2 2+ 1n^2 _n^unif ( \G _n: W_G∈ F \ ). Taking the upper limit and applying (5.11) gives lim supn→∞1n2ln⁡Nn(ℱ~)≤ln⁡22−infW~∈ℱ~I12(W~). _n→∞ 1n^2 N_n( F)≤ 22- _ W∈ FI_ 12( W). By (5.10), the right-hand side equals supW~∈ℱ~Ent⁡(W~). _ W∈ F ( W). This proves (5.13). Finally, suppose that ℱ~≠∅ F≠ and fix γ>0γ>0. By (5.13), for all sufficiently large n, 1n2ln⁡Nn(ℱ~)≤supW~∈ℱ~Ent⁡(W~)+γ. 1n^2 N_n( F)≤ _ W∈ F ( W)+γ. Exponentiating proves (5.14). ∎ Lemma 5.9. Let ℱ⊆F be a nonempty cut-closed family. For every γ>0γ>0, there exists N=N⁡(ℱ,γ)N=N(F,γ) such that, for every n≥Nn≥ N, (5.15) |G∈n:WG∈ℱ|≤exp⁡([supW∈ℱEnt⁡(W)+γ]n2). | \G _n:\ W_G \ |≤ ( [ _W (W)+γ ]n^2 ). Equivalently, there is a nonnegative sequence αn(ℱ) _n(F) satisfying limn→∞αn(ℱ)=0 _n→∞ _n(F)=0 such that (5.16) |G∈n:WG∈ℱ|≤exp⁡([supW∈ℱEnt⁡(W)+αn(ℱ)]n2) | \G _n:\ W_G \ |≤ ( [ _W (W)+ _n(F) ]n^2 ) for every sufficiently large n. Proof. Let ℱ~ F be the image of ℱF in ~ W. Lemma 5.5 shows that ℱ~ F is closed and that WG∈ℱ⟺W~G∈ℱ~.W_G W_G∈ F. Therefore |G∈n:WG∈ℱ|=|G∈n:W~G∈ℱ~|. | \G _n:\ W_G \ |= | \G _n:\ W_G∈ F \ |. Entropy is constant on every zero-cut-distance class by Lemma 3.17, so supW~∈ℱ~Ent⁡(W~)=supW∈ℱEnt⁡(W). _ W∈ F ( W)= _W (W). Now apply (5.14) to ℱ~ F. This proves (5.15). For the second form, set Sℱ≔supW∈ℱEnt⁡(W)S_F _W (W) and Nn(ℱ)≔|G∈n:WG∈ℱ|.N_n(F) | \G _n:\ W_G \ |. If Nn(ℱ)=0N_n(F)=0, set bn=0b_n=0. If Nn(ℱ)>0N_n(F)>0, set bn≔max⁡0,1n2ln⁡Nn(ℱ)−Sℱ.b_n \0, 1n^2 N_n(F)-S_F \. We now show that limn→∞bn=0 _n→∞b_n=0. Fix γ>0γ>0. By (5.15), for all sufficiently large n, Nn(ℱ)≤exp⁡((Sℱ+γ)n2).N_n(F)≤ ((S_F+γ)n^2 ). If Nn(ℱ)=0N_n(F)=0, then bn=0b_n=0. If Nn(ℱ)>0N_n(F)>0, the last inequality gives 1n2ln⁡Nn(ℱ)−Sℱ≤γ, 1n^2 N_n(F)-S_F≤γ, and therefore 0≤bn≤γ.0≤ b_n≤γ. Since γ>0γ>0 was arbitrary, it follows that limn→∞bn=0. _n→∞b_n=0. Set αn(ℱ)≔bn+1n. _n(F) b_n+ 1n. Then limn→∞αn(ℱ)=0. _n→∞ _n(F)=0. If Nn(ℱ)>0N_n(F)>0, the definition of bnb_n gives 1n2ln⁡Nn(ℱ)≤Sℱ+bn≤Sℱ+αn(ℱ). 1n^2 N_n(F)≤ S_F+b_n≤ S_F+ _n(F). Exponentiating gives (5.16). If Nn(ℱ)=0N_n(F)=0, then (5.16) is trivial. Thus (5.16) holds for every sufficiently large n. ∎ Lemma 5.10. Fix r≥3r≥ 3 and set q=r−1q=r-1. The following subsets of W are cut-closed. (1) For every δ∈[0,1]δ∈[0,1], ℱδ(r)≔W∈:t⁡(Kr,W)≤δ.F_δ^(r) \W :\;t(K_r,W)≤δ\. (2) For every ε>0 >0, ε,q≔W∈:δ□(W,Bq⋆)≥ε.D_ ,q \W :\; _ (W,B_q )≥ \. (3) For every δ∈[0,1]δ∈[0,1] and ε>0 >0, ℱδ,ε(r,q)≔ℱδ(r)∩ε,q.F_δ, ^(r,q) _δ^(r) _ ,q. Proof. (1) Fix δ∈[0,1]δ∈[0,1]. We show that ℱδ(r)=W∈:t⁡(Kr,W)≤δF_δ^(r)=\W :\;t(K_r,W)≤δ\ is cut-closed. Let (Wm)m≥1(W_m)_m≥ 1 be a sequence of graphons in ℱδ(r)F_δ^(r), and suppose that limm→∞δ□(Wm,W)=0 _m→∞ _ (W_m,W)=0 for some graphon W∈W . Since each WmW_m belongs to ℱδ(r)F_δ^(r), we have t⁡(Kr,Wm)≤δfor every m.t(K_r,W_m)≤δ every m. By Lemma 3.14, the map W↦t⁡(Kr,W)W t(K_r,W) is continuous in cut distance. Hence limm→∞t⁡(Kr,Wm)=t⁡(Kr,W). _m→∞t(K_r,W_m)=t(K_r,W). Taking the limit in t⁡(Kr,Wm)≤δt(K_r,W_m)≤δ gives t⁡(Kr,W)≤δ.t(K_r,W)≤δ. Therefore W∈ℱδ(r).W _δ^(r). So ℱδ(r)F_δ^(r) is cut-closed. (2) Fix ε>0 >0. We prove that ε,q=W∈:δ□(W,Bq⋆)≥εD_ ,q=\W :\; _ (W,B_q )≥ \ is cut-closed. If ℋH is a nonempty family of graphons, then the function W↦δ□(W,ℋ)W _ (W,H) is continuous in cut distance. Indeed, let U,V∈U,V . For every H∈ℋH , the triangle inequality gives δ□(U,H)≤δ□(U,V)+δ□(V,H). _ (U,H)≤ _ (U,V)+ _ (V,H). Taking the infimum over all H∈ℋH gives δ□(U,ℋ)≤δ□(U,V)+δ□(V,ℋ). _ (U,H)≤ _ (U,V)+ _ (V,H). So δ□(U,ℋ)−δ□(V,ℋ)≤δ□(U,V). _ (U,H)- _ (V,H)≤ _ (U,V). Now if we switch the roles of U and V, we get δ□(V,ℋ)−δ□(U,ℋ)≤δ□(U,V). _ (V,H)- _ (U,H)≤ _ (U,V). Therefore |δ□(U,ℋ)−δ□(V,ℋ)|≤δ□(U,V). | _ (U,H)- _ (V,H) |≤ _ (U,V). Thus W↦δ□(W,ℋ)W _ (W,H) is continuous. Now apply this with ℋ=Bq⋆.H=B_q . This family is nonempty, because Wq⋆∈Bq⋆W_q ∈ B_q by Notation 4.3. Hence W↦δ□(W,Bq⋆)W _ (W,B_q ) is continuous in cut distance. Now let (Wm)m≥1(W_m)_m≥ 1 be a sequence of graphons in ε,qD_ ,q, and suppose that limm→∞δ□(Wm,W)=0 _m→∞ _ (W_m,W)=0 for some graphon W∈W . Since each WmW_m belongs to ε,qD_ ,q, we have δ□(Wm,Bq⋆)≥εfor every m. _ (W_m,B_q )≥ every m. By the continuity established above, we have limm→∞δ□(Wm,Bq⋆)=δ□(W,Bq⋆). _m→∞ _ (W_m,B_q )= _ (W,B_q ). Taking the limit in δ□(Wm,Bq⋆)≥ε _ (W_m,B_q )≥ gives δ□(W,Bq⋆)≥ε. _ (W,B_q )≥ . Therefore W∈ε,q.W _ ,q. So ε,qD_ ,q is cut-closed. (3) Fix δ∈[0,1]δ∈[0,1] and ε>0 >0. We show that ℱδ,ε(r,q)=ℱδ(r)∩ε,qF_δ, ^(r,q)=F_δ^(r) _ ,q is cut-closed. Let (Wm)m≥1(W_m)_m≥ 1 be a sequence of graphons in ℱδ,ε(r,q)F_δ, ^(r,q), and suppose that limm→∞δ□(Wm,W)=0 _m→∞ _ (W_m,W)=0 for some graphon W∈W . Since Wm∈ℱδ,ε(r,q)=ℱδ(r)∩ε,q,W_m _δ, ^(r,q)=F_δ^(r) _ ,q, we have Wm∈ℱδ(r)andWm∈ε,qW_m _δ^(r) W_m _ ,q for every m. By item (1), ℱδ(r)F_δ^(r) is cut-closed. Hence W∈ℱδ(r).W _δ^(r). By item (2), ε,qD_ ,q is cut-closed. Hence W∈ε,q.W _ ,q. Therefore W∈ℱδ(r)∩ε,q=ℱδ,ε(r,q).W _δ^(r) _ ,q=F_δ, ^(r,q). So ℱδ,ε(r,q)F_δ, ^(r,q) is cut-closed. ∎ 5.4. The reduced free-energy limit Lemma 5.11 (Balanced multipartite lower bound). Let n∈ℕn , and use n=qm+a,m,a∈ℤ≥0,0≤a<q.n=qm+a, m,a _≥ 0, 0≤ a<q. Then, with sqs_q as in Notation 5.1, (5.17) Z~n,r≥exp⁡(sqn2−ln⁡22a(1−aq))≥exp⁡(sqn2−qln⁡28). Z_n,r≥ (s_qn^2- 22a (1- aq ) )≥ (s_qn^2- q 28 ). Proof. Write [n][n] as the disjoint union of q possibly empty sets [n]=V1⊔⋯⊔Vq[n]=V_1 ·s V_q whose sizes differ by at most one. Thus a sets have size m+1m+1, and the remaining q−aq-a sets have size m. Put ni≔|Vi|,i=1,…,q.n_i |V_i|, i=1,…,q. Let M be the number of unordered pairs of vertices lying in different parts. Then M=∑1≤i<j≤qninj.M= _1≤ i<j≤ qn_in_j. Since (∑i=1qni)2=∑i=1qni2+2∑1≤i<j≤qninj, ( _i=1^qn_i )^2= _i=1^qn_i^2+2 _1≤ i<j≤ qn_in_j, we have (5.18) M=12(n2−∑i=1qni2).M= 12 (n^2- _i=1^qn_i^2 ). We now compute the sum of the squared part sizes. By the choice of the partition, ∑i=1qni2 _i=1^qn_i^2 =(q−a)m2+a(m+1)2 =(q-a)m^2+a(m+1)^2 =qm2+2am+a. =qm^2+2am+a. On the other hand, since n=qm+an=qm+a, n2q=qm2+2am+a2q. n^2q=qm^2+2am+ a^2q. Therefore (5.19) ∑i=1qni2=n2q+a⁡(1−aq). _i=1^qn_i^2= n^2q+a (1- aq ). Substituting (5.19) into (5.18) gives (5.20) M=12(1−1q)n2−12a(1−aq).M= 12 (1- 1q )n^2- 12a (1- aq ). Now choose an arbitrary subset of these M possible between-part edges, and put no edges inside the parts. This gives exactly 2M2^M labeled graphs on [n][n]. Every graph constructed in this way is q-partite. Hence every clique in such a graph uses at most one vertex from each part, so every clique has size at most q. Since q=r−1q=r-1, none of these graphs contains a copy of KrK_r. Therefore each of these graphs has reduced mass exp⁡(−r!wKr(G))=1. (-r!\,w\,K_r(G))=1. Thus all these graphs contribute 11 each to Z~n,r Z_n,r, and so Z~n,r≥2M. Z_n,r≥ 2^M. Multiplying (5.20) by ln⁡2 2 and then using (5.1), we obtain (ln⁡2)M ( 2)M =ln⁡22(1−1q)n2−ln⁡22a(1−aq) = 22 (1- 1q )n^2- 22a (1- aq ) =sqn2−ln⁡22a(1−aq). =s_qn^2- 22a (1- aq ). Consequently, 2M=exp⁡(sqn2−ln⁡22a(1−aq)).2^M= (s_qn^2- 22a (1- aq ) ). Together with Z~n,r≥2M Z_n,r≥ 2^M, this proves the first inequality in (5.17). Finally, the function x⁡(1−xq)x (1- xq ) is maximized on [0,q][0,q] at x=q/2x=q/2, where its value is q/4q/4. Since 0≤a<q0≤ a<q, we have 0≤a⁡(1−aq)≤q4.0≤ a (1- aq )≤ q4. Hence −ln⁡22a(1−aq)≥−qln⁡28.- 22a (1- aq )≥- q 28. This gives the second inequality in (5.17). ∎ We now prove Theorem 2.7(i). We first fix an auxiliary clique coefficient L, then let n→∞n→∞, and only afterward let L→∞L→∞. Proof of Theorem 2.7(i). We prove the upper and lower bounds separately. Upper bound. Fix L>0L>0 and define Z~n,r(L)≔∑G∈nexp⁡(−Ln2t(Kr,WG)). Z_n,r^(L) _G _n (-Ln^2t(K_r,W_G) ). This is an auxiliary partition function in which the clique penalty L remains fixed as n grows. For every graphon W, 0≤t⁡(Kr,W)≤1.0≤ t(K_r,W)≤ 1. Moreover, t⁡(Kr,W)t(K_r,W) is continuous in cut distance by Lemma 3.14. Hence the functional W⟼−Lt(Kr,W)W -L\,t(K_r,W) is bounded and continuous. We may therefore apply [9, Thm. 3.1], which gives (5.21) limn→∞1n2ln⁡Z~n,r(L)=supW∈Ent⁡(W)−Lt(Kr,W). _n→∞ 1n^2 Z_n,r^(L)= _W \ (W)-L\,t(K_r,W) \. We next determine what happens to the right-hand side when L becomes large. In the notation of [9, Thm. 7.1], take H=Kr,β1=0,β2=−L.H=K_r, _1=0, _2=-L. The rate functional I used there satisfies I⁡(W)=12∫[0,1]2[Wln⁡W+(1−W)ln⁡(1−W)]xy=−Ent⁡(W),I(W)= 12 _[0,1]^2 [W W+(1-W) (1-W) ]\,dx\,dy=- (W), with the usual convention at 00 and 11. Thus, at β2=−L _2=-L, their variational value is exactly supW∈Ent⁡(W)−Lt(Kr,W). _W \ (W)-L\,t(K_r,W) \. Moreover, χ⁡(Kr)=randp=e2β11+e2β1=12.χ(K_r)=r p= e^2 _11+e^2 _1= 12. Theorem 7.1 of that paper therefore gives the limiting value r−22(r−1)ln⁡2=ln⁡22(1−1q)=sq, r-22(r-1) 2= 22 (1- 1q )=s_q, where we used q=r−1q=r-1. It follows that (5.22) limL→∞supW∈Ent⁡(W)−Lt(Kr,W)=sq. _L→∞ _W \ (W)-L\,t(K_r,W) \=s_q. We now compare the auxiliary model with the model in the theorem. Write Ln≔wnr−2.L_n wn^r-2. By (5.2), the reduced mass of a graph G is exp⁡(−r!wKr(G))=exp⁡(−n2Lnt(Kr,WG)). (-r!\,w\,K_r(G) )= (-n^2L_n\,t(K_r,W_G) ). Since r≥3r≥ 3 and w>0w>0, we have limn→∞Ln=+∞. _n→∞L_n=+∞. Thus, for every fixed L>0L>0, we have Ln≥L_n≥ L for all sufficiently large n. Since t⁡(Kr,WG)≥0t(K_r,W_G)≥ 0, this gives exp⁡(−n2Lnt(Kr,WG))≤exp⁡(−n2Lt(Kr,WG)). (-n^2L_n\,t(K_r,W_G) )≤ (-n^2L\,t(K_r,W_G) ). Summing this inequality over all G∈nG _n yields Z~n,r≤Z~n,r(L) Z_n,r≤ Z_n,r^(L) for all sufficiently large n. Taking logarithms, dividing by n2n^2, and using (5.21), we obtain lim supn→∞Fn,r(w) _n→∞F_n,r(w) ≤limn→∞1n2ln⁡Z~n,r(L) ≤ _n→∞ 1n^2 Z_n,r^(L) =supW∈Ent⁡(W)−Lt(Kr,W). = _W \ (W)-L\,t(K_r,W) \. This holds for every fixed L>0L>0. We may therefore let L→∞L→∞. Equation (5.22) then gives lim supn→∞Fn,r(w)≤sq. _n→∞F_n,r(w)≤ s_q. Lower bound. A graph whose edges lie only between the parts of a q-partite partition contains no copy of KrK_r, because q=r−1q=r-1. Such a graph therefore has reduced mass 11. Lemma 5.11 counts these graphs and gives Fn,r(w)≥sq−qln⁡28n2.F_n,r(w)≥ s_q- q 28n^2. Taking the lower limit gives lim infn→∞Fn,r(w)≥sq. _n→∞F_n,r(w)≥ s_q. The upper and lower bounds now agree. Therefore limn→∞Fn,r(w)=sq=ln⁡22(1−1q). _n→∞F_n,r(w)=s_q= 22 (1- 1q ). ∎ 5.5. Exponential concentration in cut distance We now prove Theorem 2.7(i). Fix ε>0 >0. The event we need to estimate is δ□(Wn,Bq⋆)≥ε. _ (W_ G_n,B_q )≥ . After choosing a small number δ>0δ>0, we separate this event according to the empirical clique density t⁡(Kr,Wn)t(K_r,W_ G_n). The part with t⁡(Kr,Wn)≥δt(K_r,W_ G_n)≥δ has very small total reduced mass by Lemma 5.3. The remaining part has t⁡(Kr,Wn)<δandδ□(Wn,Bq⋆)≥ε.t(K_r,W_ G_n)<δ _ (W_ G_n,B_q )≥ . For this part, Lemma 4.12 gives an entropy loss, and the counting bound in Lemma 5.9 turns that entropy loss into an exponential probability bound. As explained in Remark 4.7, [9, Thm. 3.2] gives concentration for each fixed clique coefficient L, but it does not provide concentration constants uniform in L. Since the present model follows the diagonal sequence Ln=wnr−2L_n=wn^r-2, for which limn→∞Ln=+∞ _n→∞L_n=+∞, the proof below establishes the required uniform diagonal estimate directly. Proof of Theorem 2.7(i). Fix ε>0 >0, and let n∼ℙn,r G_n _n,r. Choose δ0=δr,ε>0andc′=cr,ε′>0 _0= _r, >0 c =c _r, >0 from Lemma 4.12, and set δ≔min⁡δ0,1.δ \ _0,1\. The conclusion of Lemma 4.12 still holds under the stronger condition t⁡(Kr,W)≤δt(K_r,W)≤δ. Define n,ε≔G∈n:δ□(WG,Bq⋆)≥ε.A_n, \G _n:\ _ (W_G,B_q )≥ \. By (2.3), ℙ⁡(n∈n,ε)=Rn,εZ~n,r,P( G_n _n, )= R_n, Z_n,r, where Rn,ε≔∑G∈n,εexp⁡(−r!wKr(G)).R_n, _G _n, (-r!\,w\,K_r(G) ). Using (5.2), set Rn,ε=Rn,εlarge+Rn,εsmall,R_n, =R_n, ^large+R_n, ^small, where Rn,εlarge≔∑G∈n,εt⁡(Kr,WG)≥δexp⁡(−wt(Kr,WG)nr)R_n, ^large _ subarraycG _n, \\ t(K_r,W_G)≥δ subarray (-w\,t(K_r,W_G)n^r ) and Rn,εsmall≔∑G∈n,εt⁡(Kr,WG)<δexp⁡(−wt(Kr,WG)nr).R_n, ^small _ subarraycG _n, \\ t(K_r,W_G)<δ subarray (-w\,t(K_r,W_G)n^r ). For every M>0M>0, Lemma 5.3 gives, for all sufficiently large n, (5.23) Rn,εlarge≤exp⁡(−Mn2).R_n, ^large≤ (-Mn^2). Every summand in Rn,εsmallR_n, ^small is at most 11, and every graph in this sum satisfies WG∈ℱδ,ε(r,q).W_G _δ, ^(r,q). Hence Rn,εsmall≤|G∈n:WG∈ℱδ,ε(r,q)|.R_n, ^small≤ | \G _n:\ W_G _δ, ^(r,q) \ |. If ℱδ,ε(r,q)F_δ, ^(r,q) is empty, this upper bound is 00. If it is nonempty, then it is cut-closed by Lemma 5.10, and Lemma 4.12 gives supW∈ℱδ,ε(r,q)Ent⁡(W)≤sq−c′. _W _δ, ^(r,q) (W)≤ s_q-c . Lemma 5.9, with counting error c′/4c /4, now gives, for every sufficiently large n, (5.24) Rn,εsmall≤exp⁡((sq−3c′4)n2).R_n, ^small≤ ( (s_q- 3c 4 )n^2 ). Set Cq≔qln⁡28.C_q q 28. Lemma 5.11 gives Z~n,r≥exp⁡(sqn2−Cq). Z_n,r≥ (s_qn^2-C_q). Choose M=1+c′M=1+c . Combining this estimate with (5.23) and (5.24) gives ℙ⁡(n∈n,ε) ( G_n _n, ) ≤exp⁡(−(M+sq)n2+Cq)+exp⁡(−3c′4n2+Cq). ≤ (-(M+s_q)n^2+C_q )+ (- 3c 4n^2+C_q ). For every sufficiently large n, both terms on the right are at most exp(−c′n2/2) (-c n^2/2). Increasing the threshold for n once more gives 2exp(−c′n2/2)≤exp(−c′n2/4).2 (-c n^2/2)≤ (-c n^2/4). Therefore, for every sufficiently large n, ℙ(δ□(Wn,Bq⋆)≥ε)≤exp(−c′n2/4).P ( _ (W_ G_n,B_q )≥ )≤ (-c n^2/4). The theorem follows with c=c′/4c=c /4. The constant c depends only on ε and r. The threshold for n may also depend on w, through Lemma 5.3. ∎ 5.6. Probability bounds needed for the rounding argument Lemma 5.12. The following probability bounds hold: (i) Markov’s inequality. If Y≥0Y≥ 0 almost surely and t>0t>0, then ℙ⁡(Y≥t)≤⁡[Y]t.P(Y≥ t)≤ E[Y]t. (i) Hoeffding’s inequality. Let m≥1m≥ 1, and let Y1,…,YmY_1,…,Y_m be independent random variables. Suppose that, for each i∈[m]i∈[m], there are real numbers ai≤bia_i≤ b_i such that ai≤Yi≤bia_i≤ Y_i≤ b_i almost surely. Set V≔∑i=1m(bi−ai)2.V _i=1^m(b_i-a_i)^2. If V>0V>0, then, for every t≥0t≥ 0, ℙ⁡(|∑i=1mYi−∑i=1m⁡[Yi]|≥t)≤2exp⁡(−2t2V).P ( | _i=1^mY_i- _i=1^mE[Y_i] |≥ t )≤ 2 (- 2t^2V ). If V=0V=0, then ∑i=1mYi=∑i=1m⁡[Yi] _i=1^mY_i= _i=1^mE[Y_i] almost surely. Consequently, for every t>0t>0, ℙ⁡(|∑i=1mYi−∑i=1m⁡[Yi]|≥t)=0.P ( | _i=1^mY_i- _i=1^mE[Y_i] |≥ t )=0. In particular, if 0≤Yi≤10≤ Y_i≤ 1 almost surely for every i∈[m]i∈[m], and if S≔∑i=1mYi,S _i=1^mY_i, then, for every t≥0t≥ 0, ℙ⁡(|S−⁡[S]|≥t)≤2exp⁡(−2t2m).P (|S-E[S]|≥ t )≤ 2 (- 2t^2m ). (i) McDiarmid’s inequality. Let m≥1m≥ 1, let S1,…,SmS_1,…,S_m be finite sets, and let X1,…,XmX_1,…,X_m be independent random variables such that Xi∈SiX_i∈ S_i almost surely for every i∈[m]i∈[m]. Let f:S1×⋯×Sm→ℝf:S_1×·s× S_m be a function. Assume that there is a number L>0L>0 such that changing only one coordinate can change the value of f by at most L. More precisely, |f⁡(x1,…,xi,…,xm)−f⁡(x1,…,xi′,…,xm)|≤L |f(x_1,…,x_i,…,x_m)-f(x_1,…,x_i ,…,x_m) |≤ L for every i∈[m]i∈[m], every xi,xi′∈Six_i,x_i ∈ S_i, and every fixed choice of the other coordinates. Then, for every t≥0t≥ 0, ℙ⁡(|f⁡(X1,…,Xm)−⁡[f⁡(X1,…,Xm)]|≥t)≤2exp⁡(−2t2mL2).P ( |f(X_1,…,X_m)-E[f(X_1,…,X_m)] |≥ t )≤ 2 (- 2t^2mL^2 ). Proof. Item (i) is Markov’s inequality; see [23, Thm. 3.1], with the notation there renamed as X=YX=Y and a=ta=t. For item (i), first assume that V>0V>0. If t>0t>0, Hoeffding’s inequality [23, Thm. 4.14] gives ℙ⁡(|∑i=1mYi−∑i=1m⁡[Yi]|≥t)≤2exp⁡(−2t2V).P ( | _i=1^mY_i- _i=1^mE[Y_i] |≥ t )≤ 2 (- 2t^2V ). If t=0t=0, the same bound is also true, because the probability on the left is at most 11, while the right-hand side is 22. Now assume that V=0.V=0. Then ∑i=1m(bi−ai)2=0. _i=1^m(b_i-a_i)^2=0. Each term in this sum is nonnegative, so bi−ai=0for every i∈[m].b_i-a_i=0 every i∈[m]. Thus ai=bia_i=b_i for every i. Since ai≤Yi≤bia_i≤ Y_i≤ b_i almost surely, each YiY_i is almost surely constant. Hence Yi=⁡[Yi]almost surely for every i∈[m].Y_i=E[Y_i] surely for every i∈[m]. Adding over i=1,…,mi=1,…,m gives ∑i=1mYi=∑i=1m⁡[Yi] _i=1^mY_i= _i=1^mE[Y_i] almost surely. Therefore, for every t>0t>0, ℙ⁡(|∑i=1mYi−∑i=1m⁡[Yi]|≥t)=0.P ( | _i=1^mY_i- _i=1^mE[Y_i] |≥ t )=0. For the last part of item (i), assume that 0≤Yi≤1almost surely for every i∈[m],0≤ Y_i≤ 1 surely for every i∈[m], and set S≔∑i=1mYi.S _i=1^mY_i. Taking ai=0andbi=1a_i=0 b_i=1 for every i gives V=∑i=1m(bi−ai)2=∑i=1m1=m.V= _i=1^m(b_i-a_i)^2= _i=1^m1=m. The bound already proved therefore gives, for every t≥0t≥ 0, ℙ⁡(|S−⁡[S]|≥t)≤2exp⁡(−2t2m).P (|S-E[S]|≥ t )≤ 2 (- 2t^2m ). For item (i), the bounded-difference condition is exactly the hypothesis of McDiarmid’s inequality in [23, Sec. 13.5.1, Thm. 13.7]. Applying that theorem with n=mn=m, c=Lc=L, and λ=tλ=t gives the stated bound for t>0t>0. The theorem applies here because the random variables take values in finite sets. For t=0t=0, the bound is immediate, since the right-hand side is 22. ∎ 5.7. Transforming cut-distance closeness to a vertex partition The next lemma turns cut-distance closeness to Bq⋆B_q into a partition of the finite vertex set. It controls the part sizes, the edge density between every pair of parts, and the total number of edges inside the parts. Lemma 5.13. Let q≥2q≥ 2 and 0<ε≤10< ≤ 1, and set ρ≔ε100q2.ρ 100q^2. There exists Ndet=Ndet(ε,q)N_det=N_det( ,q) such that the following holds for every n≥Ndetn≥ N_det. If G is a graph on [n][n] and δ□(WG,Bq⋆)<ρ, _ (W_G,B_q )<ρ, then there is a partition [n]=V1⊔⋯⊔Vq[n]=V_1 ·s V_q with ||Vα|−n/q|≤εnfor every α∈[q], ||V_α|-n/q |≤ n every α∈[q], each VαV_α has size at least 22, |eG(Vα,Vβ)|Vα||Vβ|−12|≤εfor all distinct α,β∈[q], | e_G(V_α,V_β)|V_α||V_β|- 12 |≤ all distinct α,β∈[q], ∑α=1qeG(Vα)≤εn210q, _α=1^qe_G(V_α)≤ n^210q, and ∑α=1qeG(Vα)∑α=1q(|Vα|2)≤ε. _α=1^qe_G(V_α) _α=1^q |V_α|2≤ . Moreover, if G′G is obtained from G by deleting all edges whose endpoints lie in the same part, then G′G is q-partite and dedit(G,G′)≤ε10q.d_edit(G,G )≤ 10q. Proof. We use a random coloring argument and color the vertices independently using probabilities obtained from the graphon relabeling. We then show that the desired properties hold with positive probability and fix one coloring for which they hold. Let (aij)i,j=1n(a_ij)_i,j=1^n be the adjacency matrix of G. Thus aij=aji,aii=0.a_ij=a_ji, a_i=0. Let Wq⋆W_q and its canonical blocks A1,…,AqA_1,…,A_q be as in Notation 4.3. By that notation, δ□(WG,Bq⋆)=δ□(WG,Wq⋆)<ρ. _ (W_G,B_q )= _ (W_G,W_q )<ρ. Since the infimum in the definition of cut distance is strictly smaller than ρ, there is a measure-preserving bijection ψ:[0,1]→[0,1]ψ:[0,1]→[0,1] such that ‖WG−(Wq⋆)ψ‖□<ρ.\|W_G-(W_q )^ψ\|_ <ρ. Set ϕ≔ψ−1.φ ψ^-1. Since the cut norm is invariant under measure-preserving relabelings, we get (5.25) ‖WGϕ−Wq⋆‖□ \|W_G^φ-W_q \|_ =‖(WG−(Wq⋆)ψ)ϕ‖□ =\|(W_G-(W_q )^ψ)^φ\|_ =‖WG−(Wq⋆)ψ‖□ =\|W_G-(W_q )^ψ\|_ <ρ. <ρ. Let I1,…,InI_1,…,I_n be the intervals from Definition 3.2. These intervals form a measurable partition of [0,1][0,1]. Define Ji≔ϕ−1(Ii),i∈[n].J_i φ^-1(I_i), i∈[n]. Then J1,…,JnJ_1,…,J_n form a measurable partition of [0,1][0,1], and λ⁡(Ji)=1nfor every i∈[n].λ(J_i)= 1n every i∈[n]. For i∈[n]i∈[n] and α∈[q]α∈[q], set pi,α≔nλ(Ji∩Aα).p_i,α nλ(J_i∩ A_α). For each fixed i, these numbers can be used as probabilities: 0≤pi,α≤1and∑α=1qpi,α=1.0≤ p_i,α≤ 1 _α=1^qp_i,α=1. Also, for each fixed α, ∑i=1npi,α=nλ(Aα)=nq. _i=1^np_i,α=nλ(A_α)= nq. We now define an auxiliary random coloring of the vertices. Let Σ≔(ξ1,…,ξn) ( _1,…, _n) be an [q]n[q]^n-valued random vector whose coordinates are independent and satisfy ℙcol(ξi=α)=pi,α,i∈[n],α∈[q].P_col( _i=α)=p_i,α, i∈[n],\ α∈[q]. Equivalently, for every C=(C1,…,Cn)∈[q]nC=(C_1,…,C_n)∈[q]^n, ℙcol(Σ=C)=∏i=1npi,Ci.P_col( =C)= _i=1^np_i,C_i. Here ℙcolP_col and colE_col denote probability and expectation with respect to this product probability measure on [q]n[q]^n. For a coloring C=(C1,…,Cn)∈[q]nC=(C_1,…,C_n)∈[q]^n, define its color classes by Vα(C)≔i∈[n]:Ci=α,α∈[q].V_α(C) \i∈[n]:C_i=α\, α∈[q]. The parts are almost balanced. For every α∈[q]α∈[q] and i∈[n]i∈[n], set Zi(α)≔ξi=α.Z_i^(α) 1_\ _i=α\. For each fixed α, the random variables Z1(α),…,Zn(α)Z_1^(α),…,Z_n^(α) are independent and satisfy 0≤Zi(α)≤1almost surely.0≤ Z_i^(α)≤ 1 surely. Moreover, |Vα(Σ)|=∑i=1nZi(α)|V_α( )|= _i=1^nZ_i^(α) and col[|Vα(Σ)|]=∑i=1ncol[Zi(α)]=∑i=1npi,α=nq.E_col[|V_α( )|]= _i=1^nE_col[Z_i^(α)]= _i=1^np_i,α= nq. Applying Lemma 5.12(i) to Z1(α),…,Zn(α)Z_1^(α),…,Z_n^(α), with m=nm=n and t=εn10q,t= n10q, gives ℙcol(||Vα(Σ)|−nq|≥εn10q)≤2exp⁡(−ε250q2n).P_col ( ||V_α( )|- nq |≥ n10q )≤ 2 (- ^250q^2n ). Define Ωbal≔C∈[q]n:||Vα(C)|−nq|≤εn10qfor every α∈[q]. _bal \C∈[q]^n: ||V_α(C)|- nq |≤ n10q\ for every α∈[q] \. By the union bound, (5.26) ℙcol(Ωbalc)≤2qexp⁡(−ε250q2n).P_col( _bal^c)≤ 2q (- ^250q^2n ). If C∈ΩbalC∈ _bal, then for every α∈[q]α∈[q], ||Vα(C)|−nq|≤εn10q≤εn. ||V_α(C)|- nq |≤ n10q≤ n. Moreover, since ε≤1 ≤ 1, |Vα(C)|≥nq−εn10q≥9n10q.|V_α(C)|≥ nq- n10q≥ 9n10q. Thus, if n≥2qn≥ 2q, then |Vα(C)|≥9/5|V_α(C)|≥ 9/5. Since |Vα(C)||V_α(C)| is an integer, every part has at least two vertices. After relabeling by ϕφ, the empirical graphon WGϕW_G^φ is equal to aija_ij on Ji×JjJ_i× J_j, except possibly on a null set. Hence, for all α,β∈[q]α,β∈[q], ∫Aα×AβWGϕ(x,y)xy _A_α× A_βW_G^φ(x,y)\,dx\,dy =∑i,j=1naijλ(Ji∩Aα)λ(Jj∩Aβ) = _i,j=1^na_ijλ(J_i∩ A_α)λ(J_j∩ A_β) (5.27) =1n2∑i,j=1naijpi,αpj,β. = 1n^2 _i,j=1^na_ijp_i,αp_j,β. Edges inside the parts. Fix α∈[q]α∈[q]. Then 2eG(Vα(Σ))=∑i,j=1naijξi=αξj=α.2e_G(V_α( ))= _i,j=1^na_ij1_\ _i=α\1_\ _j=α\. The diagonal terms vanish because aii=0a_i=0. For i≠ji≠ j, independence gives col[ξi=αξj=α]=pi,αpj,α.E_col [1_\ _i=α\1_\ _j=α\ ]=p_i,αp_j,α. Using (5.27), we obtain 2n2col[eG(Vα(Σ))]=∫Aα×AαWGϕ. 2n^2E_col[e_G(V_α( ))]= _A_α× A_αW_G^φ. The graphon Wq⋆W_q is 00 on Aα×AαA_α× A_α. Therefore 0≤∫Aα×AαWGϕ=∫Aα×Aα(WGϕ−Wq⋆)≤‖WGϕ−Wq⋆‖□<ρ.0≤ _A_α× A_αW_G^φ= _A_α× A_α(W_G^φ-W_q )≤\|W_G^φ-W_q \|_ <ρ. Hence col[eG(Vα(Σ))]≤ρn22.E_col[e_G(V_α( ))]≤ ρ n^22. Summing over all α∈[q]α∈[q], we get col[∑α=1qeG(Vα(Σ))]≤qρn22.E_col [ _α=1^qe_G(V_α( )) ]≤ qρ n^22. For C∈[q]nC∈[q]^n, set Y⁡(C)≔∑α=1qeG(Vα(C)).Y(C) _α=1^qe_G(V_α(C)). Define Ωin≔C∈[q]n:Y⁡(C)≤εn210q. _in \C∈[q]^n:Y(C)≤ n^210q \. By Lemma 5.12(i), (5.28) ℙcol(Ωinc) _col( _in^c) ≤col[Y(Σ)]εn2/(10q) ≤ E_col[Y( )] n^2/(10q) ≤qρn2/2εn2/(10q) ≤ qρ n^2/2 n^2/(10q) =5q2ρε = 5q^2ρ =120. = 120. Here the last equality uses ρ=ε/(100q2)ρ= /(100q^2). Lemma 3.12(i) gives ∑α=1q(|Vα(C)|2)=12(∑α=1q|Vα(C)|2−n)≥12(n2q−n). _α=1^q |V_α(C)|2= 12 ( _α=1^q|V_α(C)|^2-n )≥ 12 ( n^2q-n ). If n≥2qn≥ 2q, then ∑α=1q(|Vα(C)|2)≥n24q. _α=1^q |V_α(C)|2≥ n^24q. Thus every C∈ΩinC∈ _in satisfies ∑α=1qeG(Vα(C))∑α=1q(|Vα(C)|2)≤εn2/(10q)n2/(4q)=2ε5<ε. _α=1^qe_G(V_α(C)) _α=1^q |V_α(C)|2≤ n^2/(10q)n^2/(4q)= 2 5< . Edges between distinct parts. For 1≤α<β≤q1≤α<β≤ q and C∈[q]nC∈[q]^n, define Fα,β(C)≔eG(Vα(C),Vβ(C)).F_α,β(C) e_G(V_α(C),V_β(C)). Fix 1≤α<β≤q1≤α<β≤ q. Since Vα(Σ)V_α( ) and Vβ(Σ)V_β( ) are disjoint, Fα,β(Σ)=∑i,j=1naijξi=αξj=β.F_α,β( )= _i,j=1^na_ij1_\ _i=α\1_\ _j=β\. Each edge between the two color classes is counted exactly once. The diagonal terms vanish because aii=0a_i=0. For i≠ji≠ j, independence gives col[ξi=αξj=β]=pi,αpj,β.E_col [1_\ _i=α\1_\ _j=β\ ]=p_i,αp_j,β. Therefore col[Fα,β(Σ)]=∑i,j=1naijpi,αpj,β.E_col[F_α,β( )]= _i,j=1^na_ijp_i,αp_j,β. Using (5.27), we obtain 1n2col[Fα,β(Σ)]=∫Aα×AβWGϕ(x,y)xy. 1n^2E_col[F_α,β( )]= _A_α× A_βW_G^φ(x,y)\,dx\,dy. On Aα×AβA_α× A_β, the graphon Wq⋆W_q equals 1/21/2. Since λ2(Aα×Aβ)=1q2,λ^2(A_α× A_β)= 1q^2, we have ∫Aα×AβWq⋆(x,y)xy=12q2. _A_α× A_βW_q (x,y)\,dx\,dy= 12q^2. By Definition 3.5, applied with S=AαS=A_α and T=AβT=A_β, and by (5.25), |∫Aα×AβWGϕ−∫Aα×AβWq⋆| | _A_α× A_βW_G^φ- _A_α× A_βW_q | =|∫Aα×Aβ(WGϕ−Wq⋆)| = | _A_α× A_β(W_G^φ-W_q ) | ≤‖WGϕ−Wq⋆‖□ ≤\|W_G^φ-W_q \|_ <ρ. <ρ. Consequently, (5.29) |col[Fα,β(Σ)]−n22q2|≤ρn2. |E_col[F_α,β( )]- n^22q^2 |≤ρ n^2. Thus n2/(2q2)n^2/(2q^2) is the deterministic target value; in general it is not the exact value of col[Fα,β(Σ)]E_col[F_α,β( )]. Changing one coordinate of C can change the counted status only of edges incident to the corresponding vertex. There are at most n−1n-1 such edges, and each contributes at most 11 to the change. Hence Fα,βF_α,β changes by at most n−1n-1, and therefore by at most n. By Lemma 5.12(i), with t=εn240q2,t= n^240q^2, we obtain ℙcol(|Fα,β(Σ)−col[Fα,β(Σ)]|>εn240q2)≤2exp⁡(−ε2800q4n).P_col ( |F_α,β( )-E_col[F_α,β( )] |> n^240q^2 )≤ 2 (- ^2800q^4n ). Define Ωcross≔C∈[q]n:|Fα,β(C)−col[Fα,β(Σ)]|≤εn240q2for every 1≤α<β≤q. _cross \C∈[q]^n: array[]l |F_α,β(C)-E_col[F_α,β( )] |≤ n^240q^2\\[5.69054pt] for every 1≤α<β≤ q array \. By the union bound, (5.30) ℙcol(Ωcrossc)≤q⁡(q−1)exp⁡(−ε2800q4n).P_col( _cross^c)≤ q(q-1) (- ^2800q^4n ). If C∈ΩcrossC∈ _cross, then for every α<βα<β, the definition of Ωcross _cross, (5.29), and the triangle inequality give (5.31) |eG(Vα(C),Vβ(C))−n22q2| |e_G(V_α(C),V_β(C))- n^22q^2 | ≤|Fα,β(C)−col[Fα,β(Σ)]|+|col[Fα,β(Σ)]−n22q2| ≤ |F_α,β(C)-E_col[F_α,β( )] |+ |E_col[F_α,β( )]- n^22q^2 | ≤εn240q2+ρn2 ≤ n^240q^2+ρ n^2 =7εn2200q2 = 7 n^2200q^2 ≤εn220q2. ≤ n^220q^2. Assume also that C∈ΩbalC∈ _bal. Let |Vα(C)|=nq+Δα,|Vβ(C)|=nq+Δβ.|V_α(C)|= nq+ _α, |V_β(C)|= nq+ _β. Then |Δα|,|Δβ|≤εn10q.| _α|,| _β|≤ n10q. Hence ||Vα(C)||Vβ(C)|−n2q2| ||V_α(C)||V_β(C)|- n^2q^2 | ≤nq(|Δα|+|Δβ|)+|ΔαΔβ| ≤ nq (| _α|+| _β| )+| _α _β| ≤εn25q2+ε2n2100q2 ≤ n^25q^2+ ^2n^2100q^2 ≤21εn2100q2 ≤ 21 n^2100q^2 ≤εn24q2. ≤ n^24q^2. Therefore (5.32) |12|Vα(C)||Vβ(C)|−n22q2|≤εn28q2. | 12|V_α(C)||V_β(C)|- n^22q^2 |≤ n^28q^2. Combining (5.31) and (5.32), and using the triangle inequality, gives |eG(Vα(C),Vβ(C))−12|Vα(C)||Vβ(C)|| |e_G(V_α(C),V_β(C))- 12|V_α(C)||V_β(C)| | ≤|eG(Vα(C),Vβ(C))−n22q2|+|n22q2−12|Vα(C)||Vβ(C)|| ≤ |e_G(V_α(C),V_β(C))- n^22q^2 |+ | n^22q^2- 12|V_α(C)||V_β(C)| | ≤εn220q2+εn28q2=7εn240q2. ≤ n^220q^2+ n^28q^2= 7 n^240q^2. The balance event also gives |Vα(C)||Vβ(C)|≥81100n2q2≥45n2q2.|V_α(C)||V_β(C)|≥ 81100 n^2q^2≥ 45 n^2q^2. Thus |eG(Vα(C),Vβ(C))|Vα(C)||Vβ(C)|−12| | e_G(V_α(C),V_β(C))|V_α(C)||V_β(C)|- 12 | ≤7εn2/(40q2)(4/5)n2/q2 ≤ 7 n^2/(40q^2)(4/5)n^2/q^2 =7ε32 = 7 32 <ε. < . By symmetry, the same estimate holds for every ordered pair of distinct parts. Fixing a coloring with the desired properties. Choose Ndet(ε,q)N_det( ,q) so large that, for every n≥Ndetn≥ N_det, (5.33) n n ≥2q, ≥ 2q, 2qexp⁡(−ε250q2n) 2q (- ^250q^2n ) ≤140, ≤ 140, q⁡(q−1)exp⁡(−ε2800q4n) q(q-1) (- ^2800q^4n ) ≤140. ≤ 140. It follows from (5.26), (5.28), (5.30), and (5.33) that ℙcol(Ωbalc)≤140,ℙcol(Ωinc)≤120,ℙcol(Ωcrossc)≤140.P_col( _bal^c)≤ 140, _col( _in^c)≤ 120, _col( _cross^c)≤ 140. Therefore ℙcol(Ωbal∩Ωin∩Ωcross) _col ( _bal∩ _in∩ _cross ) ≥1−140−120−140 ≥ 1- 140- 120- 140 =910>0. = 910>0. So there exists a coloring C∈Ωbal∩Ωin∩Ωcross.C∈ _bal∩ _in∩ _cross. Set Vα≔Vα(C),α∈[q].V_α V_α(C), α∈[q]. The estimates above show that this partition has the required part sizes, the required between-part edge densities, and the required bound on the number of edges inside the parts. Finally, let G′G be obtained from G by deleting all edges inside the parts V1,…,VqV_1,…,V_q. Then G′G is q-partite, and |E⁡(G)△E⁡(G′)|=∑α=1qeG(Vα)≤εn210q.|E(G) E(G )|= _α=1^qe_G(V_α)≤ n^210q. By the definition of deditd_edit in Section 1, dedit(G,G′)=|E⁡(G)△E⁡(G′)|n2≤ε10q.d_edit(G,G )= |E(G) E(G )|n^2≤ 10q. ∎ We now use the cut-distance concentration theorem to prove the finite-graph structure theorem. Proof of Theorem 2.7(i). Fix ε>0 >0. Since Lemma 5.13 is stated for parameters at most 11, set η≔min⁡ε,1,ρ≔η100q2.η \ ,1\, ρ η100q^2. Let n∼ℙn,r G_n _n,r. Applying Theorem 2.7(i) with the parameter ρ, we get constants c0=c0(ρ,r)>0andN0=N0(ρ,r,w)c_0=c_0(ρ,r)>0 N_0=N_0(ρ,r,w) such that, for every n≥N0n≥ N_0, ℙ⁡(δ□(Wn,Bq⋆)≥ρ)≤exp⁡(−c0n2).P ( _ (W_ G_n,B_q )≥ρ )≤ (-c_0n^2). Let Ndet=Ndet(η,q)N_det=N_det(η,q) be the threshold from Lemma 5.13, and define n0≔max⁡N0,Ndet.n_0 \N_0,N_det\. Then, for every n≥n0n≥ n_0, with probability at least 1−exp⁡(−c0n2)1- (-c_0n^2), we have δ□(Wn,Bq⋆)<ρ. _ (W_ G_n,B_q )<ρ. On this event, Lemma 5.13, applied with η in place of ε , gives a partition [n]=V1⊔⋯⊔Vq[n]=V_1 ·s V_q satisfying all the conclusions of that lemma with parameter η. Since η≤ε,η≤ , the same partition satisfies the required bounds in Theorem 2.7(i) with parameter ε . In particular, if n′ G_n is obtained from n G_n by deleting all edges whose endpoints lie in the same part, then n′ G_n is q-partite and dedit(n,n′)≤η10q≤ε10q≤ε2,d_edit( G_n, G_n )≤ η10q≤ 10q≤ 2, because q≥2q≥ 2. Thus the theorem holds with c≔c0.c c_0. Since ρ=η/(100q2)ρ=η/(100q^2), and since q=r−1q=r-1, the constant c depends only on ε and r. The threshold n0n_0 may also depend on w. ∎ 6. Examples and consequences We first discuss the boundary case r=2r=2 and the first case covered by Theorem 2.7, namely r=3r=3. We then show that the induced subgraph on any fixed number of labeled vertices converges in distribution to a stochastic block model, derive the limiting clique densities, and give an exponential bound for colorability with fewer than r−1r-1 colors. Finally, we extend the model to several fixed clique penalties. 6.1. The case r=2r=2 The notions defined in Section 2 are straightforwardly extended to the case r=2r=2, and we get N2(G)=n2−2|E⁡(G)|,N_2(G)=n^2-2|E(G)|, and Z~n,2=(1+e−2w)(n2). Z_n,2= (1+e^-2w ) n2. The possible edges are therefore independent, and each is present with probability e−2w1+e−2w=11+e2w. e^-2w1+e^-2w= 11+e^2w. Thus ℙn,2P_n,2 is exactly the G⁡(n,1/(1+e2w))G (n,1/(1+e^2w) ) distribution. In particular, the (r−1)(r-1)-partite behavior in Theorem 2.7 begins at r=3r=3. 6.2. The case r=3r=3 Here q=r−1=2q=r-1=2. By Corollary 2.6, the reduced mass of a graph G is e−6wK3(G).e^-6wK_3(G). Thus triangles are penalized. By Theorem 2.7(i), the empirical graphon converges in probability, in cut distance, to the class represented by W2⋆W_2 . The canonical representative W2⋆W_2 has two equal blocks and takes value 00 within each block and 1/21/2 between the blocks. 6.3. A stochastic block model limit For m∈ℕm and probability measures α and β on mG_m, their total variation distance is dTV(α,β)≔12∑J∈m|α⁡(J)−β⁡(J)|.d_TV(α,β) 12 _J _m|α(J)-β(J)|. Definition 6.1. For m∈ℕm , J∈mJ _m, and a graphon W, define the induced density of J in W by tind(J,W)≔∫[0,1]m∏i,j∈E⁡(J)W(xi,xj)∏1≤i<j≤mi,j∉E⁡(J)(1−W(xi,xj))dx1⋯dxm.t_ind(J,W) _[0,1]^m _\i,j\∈ E(J)W(x_i,x_j) _ subarrayc1≤ i<j≤ m\\ \i,j\∉ E(J) subarray (1-W(x_i,x_j) )\,dx_1·s dx_m. This is the induced-density formula in [22, Sec. 7.2, Eq. (7.3)]. Under the graphon sampling construction from Section 3, it equals the probability of obtaining the labeled graph J; see [22, Sec. 10.1, immediately before Eq. (10.3)]. Corollary 6.2 (Stochastic block model limit for fixed induced subgraphs). Fix an integer r≥3r≥ 3, set q=r−1q=r-1, and let w>0w>0 and m∈ℕm . For every n≥mn≥ m, let n∼ℙn,r G_n _n,r, and let n,m H_n,m be the subgraph of n G_n induced by [m][m]. Define a random graph m(q) S_m^(q) on [m][m] as follows. Choose C1,…,CmC_1,…,C_m independently and uniformly from [q][q]. Given these labels, include the possible edges independently, with probability ℙSBM(i,j∈E⁡(m(q))∣C1,…,Cm)=0,Ci=Cj,12,Ci≠Cj,1≤i<j≤m.P_SBM (\i,j\∈ E( S_m^(q)) C_1,…,C_m )= cases0,&C_i=C_j,\\ 12,&C_i≠ C_j, cases 1≤ i<j≤ m. Here ℙSBM(Sm(q))P_SBM(S_m^(q)) denotes probability of getting Sm(p)S_m^(p) under this construction. Define probability measures νn,m _n,m and νm(q) _m^(q) on mG_m by νn,m(J)≔ℙ⁡(n,m=J),νm(q)(J)≔ℙSBM(m(q)=J) for J∈m. _n,m(J) ( H_n,m=J), _m^(q)(J) _SBM( S_m^(q)=J) for \ J _m. Then limn→∞dTV(νn,m,νm(q))=0. _n→∞d_TV ( _n,m, _m^(q) )=0. The limiting measure νm(q) _m^(q) depends on q=r−1q=r-1 but not on w. Proof. Fix J∈mJ _m. For the induced density from Definition 6.1, inclusion-exclusion gives [22, Sec. 7.2, Eq. (7.4)] tind(J,W)=∑F∈mE⁡(J)⊆E⁡(F)(−1)|E⁡(F)∖E⁡(J)|t(F,W).t_ind(J,W)= _ subarraycF _m\\ E(J) E(F) subarray(-1)^|E(F) E(J)|t(F,W). By [7, Thm. 3.7(a)], each homomorphism density in this sum is continuous in cut distance. Therefore tind(J,⋅)t_ind(J,·) is also continuous in cut distance. Theorem 2.7(i) and the final identity in Notation 4.3 give, for every ε>0 >0, limn→∞ℙ⁡(|tind(J,Wn)−tind(J,Wq⋆)|≥ε)=0. _n→∞P ( |t_ind(J,W_ G_n)-t_ind(J,W_q ) |≥ )=0. Since the absolute difference is bounded by 11, for every ε>0 >0, its expectation is at most ε plus the probability that it is at least ε . Hence, (6.1) limn→∞⁡[|tind(J,Wn)−tind(J,Wq⋆)|]=0. _n→∞E [ |t_ind(J,W_ G_n)-t_ind(J,W_q ) | ]=0. Define a probability measure ν¯n,m ν_n,m on mG_m by ν¯n,m(J)≔⁡[tind(J,Wn)]. ν_n,m(J) [t_ind(J,W_ G_n) ]. By (2.3), the probability assigned to a graph G depends only on Kr(G)K_r(G), which is invariant under vertex relabeling. Hence the distribution of n G_n is invariant under vertex relabeling. Consequently, if ι:[m]→[n] :[m]→[n] is an independent uniformly chosen injection, then n,m H_n,m has the same distribution as the graph on [m][m] in which i,j\i,j\ is an edge exactly when ι⁡(i),ι⁡(j)∈E⁡(n)\ (i), (j)\∈ E( G_n). On the other hand, sampling from WGW_G corresponds to choosing vertices of G independently, so the same vertex may be chosen more than once. The probability of choosing the same vertex more than once is at most (m2)/n m2/n. Therefore, by [22, Eq. (10.1)], dTV(νn,m,ν¯n,m)≤(m2)n.d_TV( _n,m, ν_n,m)≤ m2n. By Notation 4.3, graphon sampling from Wq⋆W_q is exactly the construction of m(q) S_m^(q), therefore tind(J,Wq⋆)=νm(q)(J).t_ind(J,W_q )= _m^(q)(J). It follows that dTV(νn,m,νm(q)) d_TV ( _n,m, _m^(q) ) ≤(m2)n+dTV(ν¯n,m,νm(q)) ≤ m2n+d_TV ( ν_n,m, _m^(q) ) ≤(m2)n+12∑J∈m⁡[|tind(J,Wn)−tind(J,Wq⋆)|]. ≤ m2n+ 12 _J _mE [ |t_ind(J,W_ G_n)-t_ind(J,W_q ) | ]. The sum is finite, and each term tends to zero by (6.1). This proves the result. ∎ Remark 6.3 (The limiting model is not Erdős-Rényi). Let q≥2q≥ 2 and m≥2m≥ 2, and consider the model m(q) S_m^(q) defined above. For 1≤i<j≤m1≤ i<j≤ m, let Xij≔i,j∈E(m(q)).X_ij 1_\\i,j\∈ E( S_m^(q))\. For each edge, ℙSBM(Xij=1)=ℙSBM(Ci≠Cj)12=q−1q⋅12=q−12q.P_SBM(X_ij=1)=P_SBM(C_i≠ C_j)\, 12= q-1q· 12= q-12q. Any two distinct edge indicators are independent. This is immediate for vertex-disjoint edges because they use different labels and different edge choices. If the edges share a vertex, say i,j\i,j\ and i,k\i,k\, then ℙSBM(Xij=Xik=1)=(q−1q)214=(q−12q)2,P_SBM(X_ij=X_ik=1)= ( q-1q )^2 14= ( q-12q )^2, which is the product of their individual probabilities. However, if m≥3m≥ 3, the three indicators associated with the triangle on 1,2,3\1,2,3\ are not independent as a triple, since ℙSBM(X12=X13=X23=1)=(q−1)(q−2)8q2,P_SBM(X_12=X_13=X_23=1)= (q-1)(q-2)8q^2, whereas independence would give (q−12q)3. ( q-12q )^3. Indeed, (q−12q)3−(q−1)(q−2)8q2=q−18q3>0. ( q-12q )^3- (q-1)(q-2)8q^2= q-18q^3>0. Thus any two edge indicators are independent, but the three triangle indicators are not independent as a triple. In particular, m(q) S_m^(q) is not an Erdős-Rényi graph when m≥3m≥ 3. 6.4. Limiting clique densities For any fixed integer r≥3r≥ 3 we now determine the limiting density, with respect to ℙn,rP_n,r, of KsK_s for all s≥2s≥ 2. Corollary 6.4. Fix an integer r≥3r≥ 3 and let w>0w>0. Let n∼ℙn,r G_n _n,r, and set q=r−1q=r-1. For every fixed integer s≥2s≥ 2, (6.2) t⁡(Ks,Wq⋆)=q(q−1)⋯(q−s+1)qs2(s2),2≤s≤q,0,s>q.t(K_s,W_q )= cases q(q-1)·s(q-s+1)q^s2 s2,&2≤ s≤ q,\\[8.53581pt] 0,&s>q. cases Moreover, for every η>0η>0, there are constants c=c⁡(η,r,s)>0c=c(η,r,s)>0 and N=N⁡(η,r,s,w)≥sN=N(η,r,s,w)≥ s such that, for every n≥Nn≥ N, (6.3) ℙn,r(G∈n:|s!Ks(G)ns−t⁡(Ks,Wq⋆)|≥η)≤e−cn2.P_n,r ( \G _n: | s!\,K_s(G)n^s-t(K_s,W_q ) |≥η \ )≤ e^-cn^2. Consequently, for every η>0η>0, (6.4) limn→∞ℙ⁡(|Ks(n)(ns)−t⁡(Ks,Wq⋆)|≥η)=0. _n→∞P ( | K_s( G_n) ns-t(K_s,W_q ) |≥η )=0. Thus every fixed clique KsK_s with 2≤s≤r−12≤ s≤ r-1 has a positive limiting density, while every fixed clique KsK_s with s≥rs≥ r has limiting density zero. Proof. Suppose first that 2≤s≤q2≤ s≤ q. By Definition 3.3, t(Ks,Wq⋆)=∫[0,1]s∏1≤i<j≤sWq⋆(xi,xj)dx1⋯dxs.t(K_s,W_q )= _[0,1]^s _1≤ i<j≤ sW_q (x_i,x_j)\,dx_1·s dx_s. Equivalently, choose x1,…,xsx_1,…,x_s independently and uniformly at random from [0,1][0,1]. By Notation 4.3, the index of the canonical block containing each xix_i is uniform on [q][q], and these block indices are independent. Since Wq⋆W_q is zero within each block, the integrand is nonzero only when x1,…,xsx_1,…,x_s lie in distinct blocks. The set of such points has measure q(q−1)⋯(q−s+1)qs. q(q-1)·s(q-s+1)q^s. On this set, every factor in the integrand is equal to 1/21/2. Since KsK_s has (s2) s2 edges, it follows that t⁡(Ks,Wq⋆)=q(q−1)⋯(q−s+1)qs2(s2).t(K_s,W_q )= q(q-1)·s(q-s+1)q^s2 s2. If s>qs>q, then among any s points x1,…,xsx_1,…,x_s, at least two lie in the same canonical block. The corresponding factor in the defining integral is zero. Hence t⁡(Ks,Wq⋆)=0.t(K_s,W_q )=0. This proves (6.2). By Lemma 3.18, with s in place of r, every graph G∈nG _n satisfies t⁡(Ks,WG)=s!Ks(G)ns.t(K_s,W_G)= s!\,K_s(G)n^s. Lemma 3.14 and Notation 4.3 therefore give |s!Ks(G)ns−t⁡(Ks,Wq⋆)|≤(s2)δ□(WG,Bq⋆). | s!\,K_s(G)n^s-t(K_s,W_q ) |≤ s2\, _ (W_G,B_q ). Thus, if the left-hand side is at least η, then δ□(WG,Bq⋆)≥η(s2). _ (W_G,B_q )≥ η s2. Applying Theorem 2.7(i) with η/(s2)η/ s2 in place of ε proves (6.3). Finally, for n≥sn≥ s, set Xn≔s!Ks(n)ns,an≔n(n−1)⋯(n−s+1)ns.X_n s!\,K_s( G_n)n^s, a_n n(n-1)·s(n-s+1)n^s. Then Ks(n)(ns)=Xnan. K_s( G_n) ns= X_na_n. Equation (6.3) says that XnX_n converges in probability to t⁡(Ks,Wq⋆)t(K_s,W_q ). Since an>0a_n>0 and limn→∞an=1, _n→∞a_n=1, the quotient Xn/anX_n/a_n converges in probability to the same limit. This is exactly (6.4). ∎ Example 6.5. For example, let r=4r=4, so that q=3q=3, and let n∼ℙn,4 G_n _n,4. Then t⁡(K3,W3⋆)=3⋅2⋅133 23=136,t⁡(K4,W3⋆)=0.t(K_3,W_3 )= 3· 2· 13^3\,2^3= 136, t(K_4,W_3 )=0. Hence, for every η>0η>0, limn→∞ℙ⁡(|K3(n)(n3)−136|≥η)=0,limn→∞ℙ⁡(K4(n)(n4)≥η)=0. _n→∞P ( | K_3( G_n) n3- 136 |≥η )=0, _n→∞P ( K_4( G_n) n4≥η )=0. Thus a positive proportion of triples still form triangles, even though the proportion of four-element sets that form a copy of K4K_4 tends to zero. 6.5. Colorability with fewer than r−1r-1 colors Corollary 6.6. Fix an integer r≥3r≥ 3 and let w>0w>0. Set q=r−1q=r-1, and let n∼ℙn,r G_n _n,r. Recall that χ⁡(n)χ( G_n) denotes the chromatic number of n G_n. For every n∈ℕn and every integer k with 1≤k<q1≤ k<q, (6.5) ℙ⁡(χ⁡(n)≤k)≤exp⁡(−(q−k)ln⁡22kqn2+nln⁡k+qln⁡28).P (χ( G_n)≤ k )≤ (- (q-k) 22kqn^2+n k+ q 28 ). Consequently, there are constants c=c⁡(r,k)>0c=c(r,k)>0 and N=N⁡(r,k)∈ℕN=N(r,k) such that ℙ⁡(χ⁡(n)≤k)≤e−cn2for every n≥N.P (χ( G_n)≤ k )≤ e^-cn^2 every n≥ N. In particular, when r≥4r≥ 4, the probability that n G_n is (r−2)(r-2)-partite tends to zero exponentially in n2n^2. Proof. Fix a map from [n][n] to a set of k colors, and let m1,…,mkm_1,…,m_k be the sizes of its color classes. A graph for which this map is a proper coloring can have edges only between different classes. The number of pairs in different classes is 12(n2−∑i=1kmi2)≤12(1−1k)n2, 12 (n^2- _i=1^km_i^2 )≤ 12 (1- 1k )n^2, where the inequality follows from Lemma 3.12(i). Hence at most 2(1−1/k)n2/22^(1-1/k)n^2/2 graphs have this fixed proper coloring. Since there are knk^n such maps, (6.6) |G∈n:χ⁡(G)≤k|≤kn2(1−1/k)n2/2. |\G _n:χ(G)≤ k\ |≤ k^n2^(1-1/k)n^2/2. A k-colorable graph has no clique with more than k vertices. Since k<q<rk<q<r, every graph counted in (6.6) is KrK_r-free and has reduced mass 11. Hence (6.6) and (5.17) give ℙ⁡(χ⁡(n)≤k)≤exp⁡(ln⁡22(1−1k)n2+nln⁡k−sqn2+qln⁡28).P (χ( G_n)≤ k )≤ ( 22 (1- 1k )n^2+n k-s_qn^2+ q 28 ). Using (5.1) gives (6.5). Since q−k>0q-k>0, the coefficient of n2n^2 is negative, which proves the final estimate. ∎ 6.6. Several fixed clique penalties We now consider a set-up with soft constraints for several clique sizes. Fix an integer ℓ≥3 ≥ 3. For each k∈3,…,ℓk∈\3,…, \ let a weight wk≥0w_k≥ 0 be fixed. Assume that at least one of these wkw_k is positive and set r≔min⁡k∈3,…,ℓ:wk>0,q≔r−1.r \k∈\3,…, \:w_k>0\, q r-1. Thus wk=0w_k=0 for k<rk<r. For all k∈3,…,ℓk∈\3,…, \ and every G∈nG _n, define Nk(G):=nk−k!Kk(G).N_k(G):=n^k-k!\,K_k(G). Hence Nk(G)N_k(G) is the number of k-tuples of vertices of G that do not form a k-clique in G. We now define the “unnormalized mass” of G∈nG _n as the number exp(∑k=3ℓwkNk(G))=exp(∑k=rℓwknk)exp(−∑k=rℓk!wkKk(G)). ( _k=3 w_kN_k(G) )= ( _k=r w_kn^k ) (- _k=r k!\,w_k\,K_k(G) ). The first factor is independent of G and cancels after normalization. We therefore define the “reduced mass” of G∈nG _n by Mnmc(G)≔exp(−∑k=rℓk!wkKk(G)),M_n^mc(G) (- _k=r k!\,w_k\,K_k(G) ), and then the corresponding reduced partition function, probability measure, and reduced free energy are defined by (6.7) Z~nmc Z_n^mc ≔∑G∈nMnmc(G), _G _nM_n^mc(G), ℙnmc(A) _n^mc(A) ≔1Z~nmc∑G∈AMnmc(G), for A⊆n, and 1 Z_n^mc _G∈ AM_n^mc(G), for \ A _n,\ \ and Fnmc F_n^mc ≔1n2ln⁡Z~nmc. 1n^2 Z_n^mc. Theorem 6.7 (The smallest positively weighted clique determines the limit structure). Let nmc∼ℙnmc, G_n^mc _n^mc, that is, n G_n is a random graph from nG_n under the probability distribution ℙnmcP_n^mc. Then the following statements hold: (i) limn→∞Fnmc=ln⁡22(1−1r−1). _n→∞F_n^mc= 22 (1- 1r-1 ). (i) For every ε>0 >0, there are constants c=c⁡(ε,r)>0andN=N⁡(ε,r,wr)c=c( ,r)>0 N=N( ,r,w_r) such that, for every n≥Nn≥ N, ℙ⁡(δ□(Wnmc,Bq⋆)≥ε)≤e−cn2.P ( _ (W_ G_n^mc,B_q )≥ )≤ e^-cn^2. (i) For every ε>0 >0, there are constants c=c⁡(ε,r)>0andN=N⁡(ε,r,wr)c=c( ,r)>0 N=N( ,r,w_r) such that, for every n≥Nn≥ N, with probability at least 1−e−cn21-e^-cn^2, there is a partition [n]=V1⊔⋯⊔Vq[n]=V_1 ·s V_q with the following properties: (a) For every i∈[q]i∈[q], ||Vi|−n/q|≤εn. ||V_i|-n/q |≤ n. (b) For all distinct i,j∈[q]i,j∈[q], |enmc(Vi,Vj)|Vi||Vj|−12|≤ε. | e_ G_n^mc(V_i,V_j)|V_i||V_j|- 12 |≤ . (c) The total number of edges inside parts is ∑i=1qenmc(Vi)≤εn210q. _i=1^qe_ G_n^mc(V_i)≤ n^210q. (d) The total density of edges inside the parts is at most ε : ∑i=1qenmc(Vi)∑i=1q(|Vi|2)≤ε. _i=1^qe_ G_n^mc(V_i) _i=1^q |V_i|2≤ . If n′ G_n is obtained by deleting all edges whose endpoints lie in the same part, then n′ G_n is q-partite and dedit(nmc,n′)≤ε10q≤ε2.d_edit ( G_n^mc, G_n )≤ 10q≤ 2. In particular, the reduced free-energy limit and the cut-distance limit depend on the weight vector (w3,…,wℓ)(w_3,…,w_ ) only through r. Once r and wrw_r are fixed, the constants in parts (i) and (i) can be chosen independently of ℓ and of the weights wr+1,…,wℓw_r+1,…,w_ . Proof. Let Z~n,r Z_n,r, Fn,r(wr)F_n,r(w_r), and ℙn,rP_n,r denote the reduced partition function, reduced free energy, and probability measure of the single-KrK_r model with weight wrw_r, and set Cq≔qln⁡28.C_q q 28. Since the higher weights are nonnegative, every G∈nG _n satisfies (6.8) 0<Mnmc(G)≤exp⁡(−r!wrKr(G))≤1.0<M_n^mc(G)≤ (-r!\,w_rK_r(G) )≤ 1. Every graph in the balanced q-partite family used in the proof of Lemma 5.11 is KrK_r-free and hence KkK_k-free for every k≥rk≥ r. Its multi-clique reduced mass is therefore 11. Let sq:=ln⁡22(1−1q).s_q:= 22 (1- 1q ). The same lower-bound construction, together with (6.8), gives (6.9) exp⁡(sqn2−Cq)≤Z~nmc≤Z~n,r. (s_qn^2-C_q )≤ Z_n^mc≤ Z_n,r. This comparison explains the role of the smallest positively weighted clique; the lower bound is unaffected by any clique penalty, while the upper bound retains only the KrK_r penalty. For part (i), taking logarithms in (6.9) and dividing by n2n^2 gives sq−Cqn2≤Fnmc≤Fn,r(wr).s_q- C_qn^2≤ F_n^mc≤ F_n,r(w_r). The conclusion follows from Theorem 2.7(i). For parts (i) and (i), set Rn≔Z~n,rZ~nmc.R_n Z_n,r Z_n^mc. By (6.8), every event ⊆nA _n satisfies (6.10) ℙnmc()≤Rnℙn,r().P_n^mc(A)≤ R_n\,P_n,r(A). Moreover, (6.9) implies 0≤1n2ln⁡Rn≤Fn,r(wr)−sq+Cqn2,0≤ 1n^2 R_n≤ F_n,r(w_r)-s_q+ C_qn^2, and hence, by Theorem 2.7(i), (6.11) limn→∞1n2ln⁡Rn=0. _n→∞ 1n^2 R_n=0. The upper bound depends only on n, r, and wrw_r, and it tends to 00. Since the same bound holds simultaneously for every ℓ≥r ≥ r and every choice of wr+1,…,wℓ≥0w_r+1,…,w_ ≥ 0, the convergence is uniform in those parameters. Consequently, suppose that a sequence of events (n)(A_n) satisfies ℙn,r(n)≤e−an2P_n,r(A_n)≤ e^-an^2 for some a>0a>0 and all sufficiently large n. After increasing the threshold if necessary, (6.11) gives Rn≤ean2/2R_n≤ e^an^2/2, and (6.10) gives ℙnmc(n)≤e−an2/2.P_n^mc(A_n)≤ e^-an^2/2. For part (i), apply this observation to n=G∈n:δ□(WG,Bq⋆)≥εA_n= \G _n: _ (W_G,B_q )≥ \ and use Theorem 2.7(i). For part (i), let ℬn,εB_n, be the set of graphs that admit no partition satisfying the five properties stated there. Theorem 2.7(i) gives an exponential bound for ℙn,r(ℬn,ε)P_n,r(B_n, ), so the same observation gives the required bound under ℙnmcP_n^mc. The edit-distance conclusion follows from any partition satisfying those five properties, exactly as in Theorem 2.7(i). For each of parts (i) and (i), one may choose c=c⁡(ε,r)>0c=c( ,r)>0 and N=N⁡(ε,r,wr)N=N( ,r,w_r). Neither choice depends on ℓ or on the higher weights wr+1,…,wℓw_r+1,…,w_ . ∎ References [1] Juan Alvarado, Yuyi Wang, Jan Ramon, Limits of multi-relational graphs, Machine Learning, Vol. 112 (2023) 177–216. [2] Balogh, J., Bollobás, B., and Simonovits, M., The typical structure of graphs without given excluded subgraphs, Random Structures and Algorithms, Vol. 34 (2009) 305–318. [3] Balogh, J., Bollobás, B., and Simonovits, M., The fine structure of octahedron-free graphs, Journal of Combinatorial Theory, Series B, Vol. 101 (2011) 67–84. [4] J. Balogh and J. Butterfield, Excluding induced subgraphs: Critical graphs, Random Structures and Algorithms, Vol. 38 (2011) 100–120. [5] József Balogh, Robert Morris, Wojciech Samotij and Lutz Warnke, The typical structure of sparse Kr+1K_r+1-free graphs, Transactions of the American Mathematical Society, Vol. 368 (2016), 6439–6485. [6] József Balogh, Neal Bushaw, Maurício Collares, Hong Liu, Robert Morris, and Maryam Sharifzadeh, The typical structure of graphs with no large cliques, Combinatorica, Vol. 37 (2017) 617–632. [7] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801–1851, DOI: 10.1016/j.aim.2008.07.008. [8] Guy Van den Broeck, Kristian Kersting, Sriraam Natarajan, David Poole (editors), An Introduction to Lifted Probabilistic Inference, MIT Press (2021). [9] S. Chatterjee and P. Diaconis, Estimating and understanding exponential random graph models, Ann. Statist. 41 (2013), no. 5, 2428–2461, DOI: 10.1214/13-AOS1155. [10] S. Chatterjee and S. R. S. Varadhan, The large deviation principle for the Erdős–Rényi random graph, European J. Combin. 32 (2011), no. 7, 1000–1017, DOI: 10.1016/j.ejc.2011.03.014. [11] Luc De Raedt, Kristian Kersting, Sriraam Natarajan, David Poole, Statistical Relational Artificial Intelligence: Logic, Probability, and Computation, Morgan & Claypool Publishers (2016). [12] P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of KnK_n-free graphs, in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I, Atti dei Convegni Lincei, no. 17, Accademia Nazionale dei Lincei, Rome, 1976, 19–27. [13] Lise Getoor, Ben Taskar (editors), Introduction to Statistical Relational Learning, MIT Press (2007). [14] J. Hladký, P. Hu, and D. Piguet, Tilings in graphons, European J. Combin. 93 (2021), 103284, DOI: 10.1016/j.ejc.2020.103284. [15] Hundack, C., Prömel, H. J., and Steger, A., Extremal graph problems for graphs with a color-critical vertex, Combinatorics, Probability and Computing, Vol. 2 (1993) 465–477. [16] S. Janson, Graphons, cut norm and distance, couplings and rearrangements, New York J. Math. Monographs 4 (2013), 1–76. [17] J. Kim, D. Kühn, D. Osthus, T. Townsend, Forbidding induced even cycles in a graph: typical structure and counting, Journal of Combinatorial Theory, Ser. B, Vol. 131 (2018) 170–219. [18] D. J. Kleitman, B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Transactions of the American Mathematical Society, Vol. 205 (1975) 205–220. [19] Ph. G. Kolaitis, H. J. Prömel, and B. L. Rothschild, Kℓ+1K_ +1-free graphs: asymptotic structure and a 00–11 law, Trans. Amer. Math. Soc. 303 (1987), no. 2, 637–671, DOI: 10.1090/S0002-9947-1987-0902790-6. [20] Koponen, V., Random graphs with bounded maximum degree: asymptotic structure and a logical limit law, Discrete Mathematics and Theoretical Computer Science, Vol. 14 (2012) 229–254. [21] V. Koponen, Domain size asymptotics for Markov logic networks, arXiv:2509.04192v2 [cs.AI], 2026, DOI: 10.48550/arXiv.2509.04192. [22] L. Lovász, Large Networks and Graph Limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012, DOI: 10.1090/coll/060. [23] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd ed., Cambridge University Press, Cambridge, 2017, DOI: 10.1017/9781316651124. [24] Hans Jürgen Prömel, Angelika Steger, Excluding induced subgraphs: quadrilaterals, Random Structures and Algorithms, Vol. 2 (1991) 55–71. [25] Bruce Reed, The Global Structure of a Typical Graph Without H as an Induced Subgraph when H is a Cycle, https://arxiv.org/abs/2506.03544. [26] M. Richardson and P. Domingos, Markov logic networks, Machine Learning 62 (2006), no. 1–2, 107–136, DOI: 10.1007/s10994-006-5833-1. [27] G. Robins, P. Pattison, Y. Kalish, and D. Lusher, An introduction to exponential random graph (p∗)(p ) models for social networks, Social Networks 29 (2007), no. 2, 173–191, DOI: 10.1016/j.socnet.2006.08.002. [28] W. Rudin, Principles of Mathematical Analysis, 3rd ed., International Series in Pure and Applied Mathematics, McGraw-Hill, Inc., New York, 1976. [29] Caroline Terry, Structure and enumeration theorems for hereditary properties in finite relational languages, Annals of Pure and Applied Logic, Vol. 169 (2018) 413–449. [30] Y. Tousinejad and V. Koponen, Random coloured digraphs defined by a Markov logic network, arXiv:2606.23715 [math.LO], 2026, DOI: 10.48550/arXiv.2606.23715. [31] N. C. Wormald, Models of random regular graphs, in J. Lamb and D. Preece (editors), Surveys in Combinatorics, 1999, Vol. 267 of London Mathematical Society Lecture Note Series, 239–298, Cambridge University Press (1999).

Instant research discovery