Exponential random graph models with soft clique constraints

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

arXiv:2608.30869v1 [math.CO] 31 Aug 2026

YASMIN TOUSINEJAD AND VERA KOPONEN Abstract. Let r ≥ 3 be fixed, and let Gn be the set of all simple graphs with vertex set [n] = {1, . . . , n}. We consider an exponential random graph model which gives higher probability to G ∈ Gn than to H ∈ Gn if G has fewer r-cliques than H. But all graphs in Gn 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 → ∞, a random graph from Gn 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 ε > 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, . . . , n tends to 1 as n → ∞. More generally, Kolaitis, Prömel and Rothschild [19] proved that, for every fixed r ≥ 3, the proportion of (r − 1)-partite graphs among all Kr -free graphs with vertices 1, . . . , n tends to 1 as n → ∞. We can say that asymptotically almost surely (a.a.s.) a Kr -free graph is (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} 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], 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] 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 Date: 31 August, 2026.

1

2

YASMIN TOUSINEJAD AND VERA KOPONEN

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 ≥ 3) r-cliques, that is, copies of the complete graph on r vertices, denoted Kr . 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, with probability tending to 1 as the number n of vertices tends to infinity, the following holds for a random graph: n . (1) There is a partition of the vertex set into r − 1 parts, each of size close to r−1 1 (2) The density of edges between any two different parts is close to 2 . (3) For every ε > 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 > 0). We also prove (Corollary 6.6) that if r ≥ 4 then the probability that a random graph is (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] converges in distribution to a stochastic block model with r − 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 1 2 . 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 < . . . < rk and for each ri we penalize an ri -clique with weight wi > 0. (The larger wi is, the more strongly ri -cliques are penalized.) We show (Theorem 6.7) that, for all choices of weights w1 , . . . , wk > 0, the asymptotic behaviour of random graphs under this model is determined by r1 . 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 := r1 . 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 Kr in graphons, and the cut distance of a graphon from a “balanced (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}. For n ∈ N, let Gn be the set of all undirected graphs without loops (i.e. simple graphs) with vertex set [n]. For every finite graph G, let E(G) denote its edge set and let χ(G) denote its chromatic number. If n ∈ N, G ∈ Gn , and A ⊆ [n], set eG (A) := {{u, v} ∈ E(G) : u, v ∈ A} .

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

3

If in addition B ⊆ [n] is disjoint from A, define eG (A, B) := {{u, v} ∈ E(G) : |{u, v} ∩ A| = 1, |{u, v} ∩ B| = 1} . For n ∈ N and graphs G, H ∈ Gn , define the n2 -normalized edge-edit distance between G and H by 1 dedit (G, H) := 2 |E(G)△E(H)|. n Here △ denotes symmetric difference. Thus dedit (G, H) is the number of edge insertions and deletions needed to turn G into H, normalized by n2 . For n ∈ N and p ∈ [0, 1], the notation Hn ∼ G(n, p) means that Hn is a random element of Gn sampled by including an unordered pair {i, j} as an edge with probability p, independently of whether other pairs have been included n or not. In particular, Hn ∼ G(n, 12 ) means that every graph in Gn has probability 2−( 2 ) , so Hn is uniformly distributed on Gn . For every integer s ≥ 2, Ks denotes a complete graph with s vertices. For every finite graph G, let Ks (G) denote the number of unordered copies of Ks in G, in other words, the number of subgraphs of G that are isomorphic to Ks . 2. The probability model and the main results Throughout this article r ≥ 3 is a fixed integer and w > 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 ∈ Gn , let (2.1)

Nr (G) := nr − r! Kr (G),

so Nr (G) is the number of ordered r-tuples (v1 , . . . , vr ) ∈ [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 ∈ Gn , we define its unnormalized mass by
µn,r (G) := exp w Nr (G) . We then define the partition function (or normalizing constant) by X Zn,r := µn,r (J). J∈Gn

Finally, we define the probability measure of the model by 1 X µn,r (G) for all A ⊆ Gn . Pn,r (A) := Zn,r G∈A

For a single graph G ∈ Gn , we also set Pn,r (G) := Pn,r ({G}) =

µn,r (G) . Zn,r

Since w is fixed in the model, we suppress the dependence on w in the notation µn,r , Zn,r , and Pn,r . Note that if G, H ∈ Gn and Kr (G) < Kr (H), then Pn,r (G) > Pn,r (H). The distribution Pn,r is exactly the probability distribution on Gn obtained from a Markov logic network [26] with one soft constraint of the form _ ¬E(xi , xj ) with weight w, 1≤i<j≤r

4

YASMIN TOUSINEJAD AND VERA KOPONEN

where ¬E(xi , xj ) expresses that there is no edge between xi and xj . 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 . 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), and the falsifying tuples are still exactly the r! orderings of the vertices of each copy of Kr . So the number of satisfied groundings becomes Nrdist (G) = n(n − 1) · · · (n − r + 1) − r! Kr (G). If we use the same weight w, then the corresponding unnormalized mass is  
 dist µdist n,r (G) := exp w Nr (G) = exp w n(n − 1) · · · (n − r + 1) − r! Kr (G) . Compare this with our present convention,
µn,r (G) = exp w[nr − r! Kr (G)] . Subtracting the exponents gives    µn,r (G) = exp w nr − n(n − 1) · · · (n − r + 1) µdist n,r (G). The factor

   exp w nr − n(n − 1) · · · (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 X dist := Zn,r µdist n,r (J), J∈Gn

then

   dist Zn,r = exp w nr − n(n − 1) · · · (n − r + 1) Zn,r ,

and hence

µdist µn,r (G) n,r (G) . = dist Zn,r Zn,r So, for the same clause weight w, the two counting conventions define exactly the same probability measure on Gn . Thus the choice between these two conventions does not affect which graphs are more or less likely. Pn,r (G) =

2.2. The equivalent exponential random graph model. The distribution Pn,r can be defined in the setting of exponential random graph models [27]. Definition 2.4. Fix n, k ∈ N. An Exponential Random Graph Model (ERGM) on Gn is a probability distribution of the form
Pk exp i=1 ϑi Ti (G) Pn,ϑ (G) := for all G ∈ Gn , ZnERGM (ϑ) S where T1 , . . . , Tk are real-valued functions on n∈N Gn , ϑ = (ϑ1 , . . . , ϑk ) ∈ Rk is a parameter vector, and ZnERGM (ϑ) :=

X J∈Gn

exp

k X i=1

ϑi Ti (J)

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

5

is the normalizing constant. All else being equal, a positive value of ϑi rewards larger values of Ti (G) in the exponent, while a negative value penalizes them. Note that if k = 1, ϑ1 = w, and T1 (G) = Nr (G), then for all G ∈ Gn .

Pn,r (G) = Pn,ϑ (G) Hence Pn,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 Zen,r := Zen,r (w) :=

X

exp −r! w Kr (J)

and

J∈Gn

(2.2) Fn,r := Fn,r (w) :=

1 ln Zen,r . n2

We call Zen,r the reduced partition function and Fn,r (w) the reduced free energy. (b) For a graph G ∈ Gn , we call
exp −r! w Kr (G) the reduced mass of G. Thus Zen,r is the sum of the reduced masses of all graphs in Gn . The partition function Zn,r sums the unnormalized masses of all graphs in Gn . As the next lemma shows, its logarithm contains the graph-independent term wnr . 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 ∈ Gn ,

µn,r (G) = exp w nr exp −r! w Kr (G) . Moreover,
Zn,r = exp w nr Zen,r , and (2.3)

exp −r! w Kr (G) exp −r! w Kr (G)
= . Pn,r (G) = P en,r Z J∈Gn exp −r! w Kr (J)

Proof. Insert (2.1) into the definition of µn,r (G):
µn,r (G) = exp w [nr − r! Kr (G)] . r

Now factor out the deterministic term ewn . The formulas for Zn,r and Pn,r follow immediately. □ 2.4. Main results. Recall that we have fixed an integer r ≥ 3 and a real w > 0. The notation Gn ∼ Pn,r means that Gn is a random graph from Gn under the distribution Pn,r . (So if J ∈ Gn then P(Gn = J) = Pn,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 ∈ Gn , its empirical graphon WG 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⋆ is defined in Definition 4.1; informally, it consists of the balanced q-block graphons that are equal to 0 on the diagonal blocks and equal to 21 on the off-diagonal blocks.

6

YASMIN TOUSINEJAD AND VERA KOPONEN

Theorem 2.7. Fix r ≥ 3, set q = r − 1. Let Gn ∼ Pn,r . Then the following hold. (i) The reduced free energy satisfies   ln 2 1 lim Fn,r (w) = 1− . n→∞ 2 q (ii) For every ε > 0, there are constants c = c(ε, r) > 0 and N = N (ε, r, w) such that, for every n ≥ N ,
2 P δ□ (WGn , Bq⋆ ) ≥ ε ≤ e−cn . (iii) For every ε > 0, there are constants c = c(ε, r) > 0 and n0 = n0 (ε, r, w) such 2 that, for every n ≥ n0 , with probability at least 1 − e−cn , the graph Gn has a partition [n] = V1 ⊔ · · · ⊔ Vq with the following properties: (a) Each part is almost balanced: |Vi | − n/q ≤ εn

for every i ∈ [q].

(b) Each between-part edge density is close to 12 : eGn (Vi , Vj ) 1 − ≤ε |Vi ||Vj | 2

for all distinct i, j ∈ [q].

(c) The total number of edges inside the parts satisfies q X

eGn (Vi ) ≤

i=1

εn2 . 10q

(d) The total density of edges inside the parts is at most ε: Pq i=1 eGn (Vi )
≤ ε. Pq |V | i

i=1

2

In particular, if G′n is obtained from Gn by deleting all edges whose endpoints lie in the same part, then G′n is q-partite and ε ε dedit (Gn , 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 Gn of the form
exp n2 T (G) T
Pn (G) = P 2 J∈Gn exp n T (J) S where T is a function from n∈N Gn into the reals. If we rewrite the distribution Pn,r so that, for an appropriate choice of T and all n, Pn,r = PTn then, for all n and all G ∈ Gn , we must have wNr (G) . T (G) := n2 Recall that Nr (G) is the number of r-tuples of vertices of G that do not form an r-clique. So if G ∈ Gn does not have an r-clique (e.g. if G is (r − 1)-partite), then Nr (G) = nr

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

7

where r ≥ 3. It follows that maxG∈Gn T (G) is unbounded as n → ∞. But the results of [9] assume that maxG∈Gn T (G) is bounded as 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] such that W (x, y) = W (y, x) for almost every (x, y) ∈ [0, 1]2 . Let W denote the family of these measurable functions. Let λ denote Lebesgue measure on [0, 1]. For each integer m ≥ 1, let λm denote the product Lebesgue measure on [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 , . . . , Xn independently and uniformly from [0, 1]. Conditional on X1 , . . . , Xn , put each edge {i, j} with i < j into the graph independently with probability W (Xi , Xj ). Definition 3.2 (Empirical graphon). Let n ∈ N, and let G be a graph with vertex set [n] and adjacency matrix (aij )1≤i,j≤n , where aij = aji

and

aii = 0.

Split [0, 1] into n intervals of equal length by setting hn − 1 i hi − 1 i  , for 1 ≤ i < n, In = ,1 . Ii = n n n The empirical graphon of G is the graphon WG : [0, 1]2 → [0, 1] defined as follows. If x ∈ Ii and y ∈ Ij , then WG (x, y) := aij . Thus WG records the adjacency matrix of G on the n2 rectangles Ii ×Ij . It is measurable, symmetric, and takes only the values 0 and 1. Also, WG = 0 on each rectangle Ii × Ii , because aii = 0. Definition 3.3 (Homomorphism density). Let H be a finite simple graph with vertex set V (H) = {1, . . . , k}. For a graphon W , the homomorphism density of H in W is Z Y t(H, W ) := W (xi , xj ) dx1 · · · dxk . [0,1]k {i,j}∈E(H)

Remark 3.4. For H = Kr this becomes Z Y t(Kr , W ) =

W (xa , xb ) dx1 · · · dxr .

[0,1]r 1≤a<b≤r

The integrand is nonnegative. So if t(Kr , W ) = 0, then the product inside the integral must vanish almost everywhere. From now on, a graphon W is called a graphon of zero Kr -density if t(Kr , W ) = 0, that is, if its Kr -homomorphism density is zero.

8

YASMIN TOUSINEJAD AND VERA KOPONEN

Definition 3.5 (Cut norm). For an integrable function U : [0, 1]2 → R, the cut norm is Z U (x, y) dx dy . ∥U ∥□ := sup S,T ⊆[0,1] S,T measurable

S×T

Definition 3.6 (Cut distance). A measurable map ϕ : [0, 1] → [0, 1] is measurepreserving if λ(ϕ−1 (A)) = λ(A)

for every Lebesgue-measurable A ⊆ [0, 1].

A measure-preserving bijection is a bijection ϕ : [0, 1] → [0, 1] such that both ϕ and ϕ−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)). Thus W ϕ is obtained from W by applying ϕ to both variables. When ϕ is a measurepreserving bijection, we call W ϕ a relabeling of W . For graphons W1 and W2 , their cut distance is δ□ (W1 , W2 ) := inf ∥W1 − W2ϕ ∥□ , ϕ

where the infimum is taken over all measure-preserving bijections ϕ : [0, 1] → [0, 1]. Relabeling by a measure-preserving bijection does not change the cut norm. Indeed, let F : [0, 1]2 → R be a measurable function with Z |F (x, y)| dx dy < ∞, [0,1]2

and let ϕ be a measure-preserving bijection. Define F ϕ (x, y) := F (ϕ(x), ϕ(y)). Then ∥F ϕ ∥□ = ∥F ∥□ . This follows by changing variables in the integral over S × T . Since ϕ is measurepreserving and bijective, the sets ϕ(S) and ϕ(T ) run through the same measurable subsets of [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, F) := inf δ□ (W, V ). V ∈F

The cut distance δ□ is a pseudometric on W. Indeed, let U, V, W ∈ W. To see symmetry, let ϕ be a measure-preserving bijection. By invariance of the cut norm under relabeling, −1 −1 ∥U − V ϕ ∥□ = ∥U ϕ − V ∥□ = ∥V − U ϕ ∥□ . Taking the infimum over ϕ gives δ□ (U, V ) = δ□ (V, U ). For the triangle inequality, if ϕ and ψ are measure-preserving bijections, then ∥U − W ψ◦ϕ ∥□ ≤ ∥U − V ϕ ∥□ + ∥V ϕ − (W ψ )ϕ ∥□ = ∥U − V ϕ ∥□ + ∥V − W ψ ∥□ . Taking the infimum over ϕ and ψ proves the triangle inequality. Nonnegativity and δ□ (U, U ) = 0 are immediate.

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

9

Notation 3.8 (Reduced graphon space). Define W ∼V

⇐⇒

δ□ (W, V ) = 0,

and let f := W/ ∼, W

f π:W→W

f := π(W ) and, for n ∈ N and G ∈ Gn , be the quotient space and quotient map. We use W fG := π(WG ). For reduced graphons define W e , Ve ) := δ□ (U, V ), d□ (U where U and V are arbitrary representatives. This definition does not depend on the chosen representatives. Indeed, if U ′ ∼ U and V ′ ∼ V , then δ□ (U ′ , V ′ ) ≤ δ□ (U ′ , U ) + δ□ (U, V ) + δ□ (V, V ′ ) = δ□ (U, V ). The same argument with (U, V ) and (U ′ , V ′ ) interchanged gives δ□ (U, V ) ≤ δ□ (U ′ , V ′ ). Hence δ□ (U ′ , V ′ ) = δ□ (U, V ). f It is a metric because nonnegativity, symmetry, and the Thus d□ is well defined on W. triangle inequality are inherited from δ□ . Also, e , Ve ) = 0 d□ (U e = Ve . The metric space (W, f d□ ) is compact; holds exactly when U ∼ V , which means U see [22, Thm. 9.23]. For F ⊆ W, we use f π(F) := {π(W ) : W ∈ F} ⊆ W for its quotient image. Remark 3.9 (Zero cut distance). For graphons U and V , the condition δ□ (U, V ) = 0 means that U and V represent the same graph limit. Equivalently, there exist measurepreserving maps ϕ, ψ : [0, 1] → [0, 1] such that Uϕ = V ψ

almost 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 is weaker than almost-everywhere equality after a single measure-preserving relabeling. f This By Notation 3.8, graphons at zero cut distance represent the same point of W. quotient space is the reduced graphon space used in [10, Sec. 1.3]. Notation 3.10. For an integrable function U : [0, 1]2 → R, the L1 -norm is defined as Z |U (x, y)| dx dy. ∥U ∥1 := [0,1]2

Notation 3.11 (Indicator functions). For any set or event A, 1A denotes its indicator. Thus 1A (z) = 1 when z ∈ A and 1A (z) = 0 otherwise.

10

YASMIN TOUSINEJAD AND VERA KOPONEN

Lemma 3.12. We will use the following two forms of the Cauchy-Schwarz inequality. (i) If S ⊆ [0, 1]2 is measurable and f : S → R is measurable with Z f 2 < ∞, S

then Z

2 Z 2 |f | ≤ λ (S) f 2 .

S

S

(ii) If m ≥ 1 is an integer and x1 , . . . , xm ∈ R, then !2 m m X X ≤m x2a . xa a=1

a=1

Equivalently, m X a=1

1 x2a ≥ m

m X

!2 xa

.

a=1

Consequently, if q ∈ N, n ∈ Z≥0 , m1 , . . . , mq ∈ Z≥0 , and q X

ma = n,

a=1

then

 q  X ma a=1

2

1 = 2

q X

! m2a − n

a=1

1 ≥ 2



 n2 −n . q

Proof. For (i), apply [28, Thm. 11.35] to the functions |f | and 1 on S. We get Z 1/2 Z 1/2 Z 2 |f | ≤ f 1 . S

S

S

Since Z

1 = λ2 (S),

S

it follows that Z

2 Z 2 |f | ≤ λ (S) f 2 .

S

S

For (ii), apply [28, Thm. 1.35] to the two lists x1 , . . . , x m

and

!2

!

1, . . . , 1.

This gives m X

xa

≤

a=1

m X

x2a

a=1

m X

! 1

=m

a=1

a=1

Dividing by m, we obtain m X a=1

1 x2a ≥ m

m X

!2 xa

a=1

Now apply (ii) with m = q and xa = ma . Since q X a=1

ma = n,

m X

.

x2a .

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

we have

q X

m2a ≥

a=1

11

n2 . q

Therefore  q  X ma a=1

2

q

1X 1 = ma (ma − 1) = 2 2 a=1

q X a=1

! m2a − n

1 ≥ 2



 n2 −n . q □

Lemma 3.13. Let F : [0, 1]2 → R be bounded and measurable, and let f, g : [0, 1] → [0, 1] be measurable. Then Z [0,1]2

F (x, y) f (x) g(y) dx dy ≤ ∥F ∥□ .

Proof. By [16, Eq. (4.2) and Rem. 4.1], Z ∥F ∥□ =

F (x, y)ϕ(x)ψ(y) dx dy .

sup ϕ,ψ:[0,1]→[0,1] ϕ,ψ measurable

[0,1]2

Taking ϕ = f and ψ = g gives Z [0,1]2

F (x, y)f (x)g(y) dx dy ≤ ∥F ∥□ . □

Lemma 3.14 (Clique density is Lipschitz in cut distance). Let r ≥ 2. For all graphons U and V ,   r ∥U − V ∥□ . |t(Kr , U ) − t(Kr , V )| ≤ 2 Consequently,   r |t(Kr , U ) − t(Kr , V )| ≤ δ□ (U, V ). 2 In particular, the map W 7→ t(Kr , W ) is continuous with respect to cut distance. Proof. By [16, Rem. 2.1], every Lebesgue-measurable graphon on [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   r m := , D := U − V. 2
Choose once and for all an ordering of the 2r edges of Kr . Equivalently, choose an ordering of the pairs (i1 , j1 ), . . . , (im , jm ),

1 ≤ iℓ < jℓ ≤ r,

so that every pair appears exactly once. Vertex s carries the single variable xs ∈ [0, 1]. The symbols iℓ and jℓ record which two vertices form the ℓ-th edge in the chosen list. For example, when r = 4, one possible ordering is (i1 , j1 ) = (1, 2), (i2 , j2 ) = (1, 3), (i3 , j3 ) = (1, 4), (i4 , j4 ) = (2, 3), (i5 , j5 ) = (2, 4), (i6 , j6 ) = (3, 4).

12

YASMIN TOUSINEJAD AND VERA KOPONEN

By Remark 3.4, m Y

Z t(Kr , W ) =

[0,1]r ℓ=1

W (xiℓ , xjℓ ) dx1 · · · dxr .

This means that we choose numbers x1 , . . . , xr ∈ [0, 1], one number for each vertex of the clique. For every edge {i, j} of the clique, we include the factor W (xi , xj ). Then we multiply all these factors together. Finally, we average over all choices of (x1 , . . . , xr ) ∈ [0, 1]r . Since the set [0, 1]r has total measure 1, the integral here is literally an average. Applying this formula to U and to V , we obtain ! Z m m Y Y V (xiℓ , xjℓ ) dx1 · · · dxr . t(Kr , U ) − t(Kr , V ) = U (xiℓ , xjℓ ) − [0,1]r

ℓ=1

ℓ=1

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 , use Uℓ := U (xiℓ , xjℓ ),

Vℓ := V (xiℓ , xjℓ ).

Now define

m Y

P0 :=

Vℓ ,

ℓ=1

and for s = 1, . . . , m define Ps :=

s Y

! Uℓ

m Y

! Vℓ

.

ℓ=s+1

ℓ=1

Thus P0 is the product built entirely from V , while Pm is the product built entirely from U. Therefore m m m Y Y X Uℓ − Vℓ = Pm − P0 = (Ps − Ps−1 ). ℓ=1

s=1

ℓ=1

For each s, only the s-th factor changes when one passes from Ps−1 to Ps , so ! ! Y Y Ps − Ps−1 = Uℓ (Us − Vs ) Vℓ . ℓ<s

ℓ>s

Substituting back the definitions of Uℓ and Vℓ , we get m Y

m Y

U (xiℓ , xjℓ ) −

ℓ=1

V (xiℓ , xjℓ ) =

m X Y s=1

ℓ=1

!

!

U (xiℓ , xjℓ ) D(xis , xjs )

ℓ<s

Y

V (xiℓ , xjℓ ) .

ℓ>s

If s = 1 or s = m, one of the products is empty; by convention, an empty product is equal to 1. Substituting this into the integral and using the triangle inequality, we obtain m X |t(Kr , U ) − t(Kr , V )| ≤ Is , s=1

where Z (3.1)

Is := [0,1]r

! Y

U (xiℓ , xjℓ ) D(xis , xjs )

ℓ<s

We now estimate one such term.

! Y ℓ>s

V (xiℓ , xjℓ )

dx1 · · · dxr .

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

13

Fix s ∈ {1, . . . , m} and use (is , js ) = (a, b). Let x b = (xt )t∈[r]\{a,b} ,

db x :=

Y

dxt ,

t∈[r]\{a,b}

where the coordinates are taken in increasing order. Thus x b denotes all variables except 0 xa and xb . When r = 2, [0, 1] is interpreted as a one-point probability space, so integration with respect to db x means evaluation at that point. Because every graphon takes values in [0, 1], the integrand in (3.1) is measurable and bounded in absolute value by 1. Thus it is integrable on [0, 1]r . We can therefore write the integral by first averaging over the two variables xa and xb , and then averaging over the remaining r − 2 variables, which we collect in x b. The distinguished edge {a, b} contributes the factor D(xa , xb ). Every other edge of Kr falls into exactly one of the following three types. An edge of the form {a, c} with c ∈ / {a, b} contributes a factor that depends on xa but not on xb . An edge of the form {b, c} with c ∈ / {a, b} contributes a factor that depends on xb but not on xa . An edge of the form {c, d} with c, d ∈ / {a, b} contributes a factor that depends on neither xa nor xb ; once x b is fixed, it is constant. Because Kr is a simple graph, there is only one edge joining a and b. So the factor D(xa , xb ) is the only factor that depends on both variables at the same time. Figure 1 illustrates this factorization in the case K4 .

Figure 1. In the integral defining t(K4 , W ), vertex i carries the variable xi , and the edge {i, j} contributes the factor W (xi , xj ). If the distinguished edge is {3, 4}, then that edge contributes the factor (U − V )(x3 , x4 ). Once x1 and x2 are fixed, the remaining factors split into a function of x3 , a function of x4 , and a constant. Therefore, for each fixed choice of x b, the whole integrand in (3.1) can be written in the form C(b x) D(xa , xb ) Axb(xa ) Bxb(xb ),

14

YASMIN TOUSINEJAD AND VERA KOPONEN

where Axb, Bxb : [0, 1] → [0, 1] are measurable and C(b x) ∈ [0, 1]. More concretely, Axb is the product of all remaining factors coming from edges that touch a but not b, Bxb is the product of all remaining factors coming from edges that touch b but not a, and C(b x) is the product of all remaining factors coming from edges that touch neither a nor b. Empty products are interpreted as 1. These functions take values in [0, 1] because every graphon factor does. Using this factorization and averaging first in xa and xb , we get Z Z Is = C(b x) D(xa , xb ) Axb(xa ) Bxb(xb ) dxa dxb db x [0,1]r−2

(3.2) Z

[0,1]2

Z

≤ [0,1]r−2

[0,1]2

D(xa , xb ) C(b x)Axb(xa ) Bxb(xb ) dxa dxb db x.

For each fixed x b, define fxb(xa ) := C(b x)Axb(xa ),

gxb(xb ) := Bxb(xb ).

Then fxb, gxb : [0, 1] → [0, 1] are measurable, so Lemma 3.13 applies and gives Z D(xa , xb ) fxb(xa ) gxb(xb ) dxa dxb ≤ ∥D∥□ . [0,1]2

Substituting this bound into (3.2) yields Z Is ≤ ∥D∥□ db x = ∥D∥□ , [0,1]r−2

because the set [0, 1]r−2 has total measure 1. This bound is the same for every s ∈ [m]. Hence |t(Kr , U ) − t(Kr , V )| ≤

m X s=1

Is ≤

m X s=1

  r ∥D∥□ = m ∥D∥□ = ∥U − V ∥□ . 2

This proves the first inequality. We now pass from cut norm to cut distance. Let ϕ be any measure-preserving bijection of [0, 1]. By Definition 3.6, V ϕ (x, y) = V (ϕ(x), ϕ(y)). Define Φ : [0, 1]r → [0, 1]r ,

Φ(x1 , . . . , xr ) := (ϕ(x1 ), . . . , ϕ(xr )).

Since ϕ preserves Lebesgue measure on [0, 1], the map Φ preserves the product measure on [0, 1]r . Therefore t(Kr , V ϕ ) = t(Kr , V ). Applying the inequality already proved to U and V ϕ , we obtain   r |t(Kr , U ) − t(Kr , V )| = |t(Kr , U ) − t(Kr , V ϕ )| ≤ ∥U − V ϕ ∥□ . 2 Now take the infimum over all measure-preserving bijections ϕ. By the definition of δ□ ,   r |t(Kr , U ) − t(Kr , V )| ≤ δ□ (U, V ). 2 Thus W 7→ t(Kr , W ) is Lipschitz with respect to cut distance, and in particular it is continuous. □

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

15

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) := −p ln p − (1 − p) ln(1 − p),

p ∈ [0, 1],

with the convention 0 ln 0 := 0. If pN
is an integer, then the number of 0–1 strings of N length N with exactly pN ones is pN , and for large N the logarithm of this number has leading term N h(p). Thus h(p) measures the entropy contribution per possible edge when the edge density is p. In particular, 1 h(0) = h(1) = 0, 0 ≤ h(p) ≤ ln 2, h = ln 2. 2 So the entropy is zero when the presence or absence of an edge is completely determined, and it is largest at p = 12 , where the two possibilities are most evenly balanced. Definition 3.15 (Graphon entropy). For a graphon W , define (3.3)

1 Ent(W ) := 2

Z

h W (x, y) dx dy.

[0,1]2

The factor 12 is needed because the square [0, 1]2 counts both (x, y) and (y, x), while an edge is an unordered pair. Lemma 3.16. For every p ∈ [0, 1], (3.4)

 1 2 h(p) ≤ ln 2 − 2 p − . 2

Proof. Set  1 2 . ψ(p) := ln 2 − h(p) − 2 p − 2 For p ∈ (0, 1), h′ (p) = ln

1−p , p

so ψ ′ (p) = ln

 1 p −4 p− . 1−p 2

Also, 1 − 4 ≥ 0, p(1 − p) because p(1 − p) ≤ 1/4. Thus ψ is convex on (0, 1) and extends continuously to [0, 1]. Since 1 1 = 0, ψ′ = 0, ψ 2 2 the point p = 1/2 is a global minimizer. Hence ψ(p) ≥ 0 for every p ∈ [0, 1], which gives (3.4). □ ψ ′′ (p) =

Lemma 3.17. If U, V ∈ W satisfy δ□ (U, V ) = 0, then Ent(U ) = Ent(V ). Consequently, f ) := Ent(W ), Ent(W f is a well-defined function on W.

f = π(W ), W

16

YASMIN TOUSINEJAD AND VERA KOPONEN

Proof. By Remark 3.9, there are measure-preserving maps ϕ, ψ : [0, 1] → [0, 1] such that U ϕ = V ψ almost everywhere. The product maps ϕ × ϕ and ψ × ψ preserve λ2 , hence Ent(U ) = Ent(U ϕ ) = Ent(V ψ ) = Ent(V ). □ Graphon entropy controls the number of finite graphs with prescribed large-scale structure. More precisely, for a cut-closed family F, the n2 -scale upper bound is governed by supW ∈F Ent(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(ii) to show that the probability of staying a fixed cut distance away from Bq⋆ decreases exponentially in n2 . Lemma 4.5 shows that, among graphons with zero Kr -density, entropy is maximized exactly by the graphons at zero cut distance from Bq⋆ . Lemma 3.18. For every n ∈ N, every graph G with vertex set [n], and every integer r ≥ 2, r! Kr (G) . t(Kr , WG ) = nr Proof. Let (aij )1≤i,j≤n be the adjacency matrix of G, and let I1 , . . . , In be the intervals from Definition 3.2. Splitting [0, 1]r into the boxes Iv1 × · · · × Ivr ,

v1 , . . . , vr ∈ [n],

gives (3.5)

t(Kr , WG ) =

1 nr

X

Y

avs ,vt .

v1 ,...,vr ∈[n] 1≤s<t≤r

Since every entry of the adjacency matrix is either 0 or 1, the summand corresponding to (v1 , . . . , vr ) is equal to 1 exactly when the vertices v1 , . . . , vr are pairwise distinct and form a copy of Kr in G. Indeed, if vs = vt for some s < t, then the product contains the factor avs ,vt = avs ,vs = 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 Kr in G. Every unordered copy has exactly r! such orderings, and therefore X Y (3.6) avs ,vt = r! Kr (G). v1 ,...,vr ∈[n] 1≤s<t≤r

Combining (3.5) and (3.6) gives t(Kr , WG ) =

r! Kr (G) , nr □

as required. Remark 3.19. For n ≥ r, Lemma 3.18 gives t(Kr , WG ) =

n(n − 1) · · · (n − r + 1) Kr (G)
. n nr r

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

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

17

For fixed r, n(n − 1) · · · (n − r + 1) = 1. n→∞ nr lim

4. Entropy maximizers and stability In this section we define a family of “balanced q-partite graphons” (recall q := r − 1) and prove results which relate the distance of a graphon W to a balanced q-partite graphon to the homomorphism density of Kr 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 Kr -homomorphism density 0. This will be used in the proof of Theorem 2.7 in Section 5. 4.1. The family Bq⋆ and the balanced Turán graphons. Definition 4.1. Let q ≥ 2. The family Bq⋆ consists of all graphons W : [0, 1]2 → [0, 1] for which there exists a measurable partition 1 for every i ∈ [q], [0, 1] = A1 ⊔ · · · ⊔ Aq , λ(Ai ) = q such that W (x, y) = 0 for almost every (x, y) ∈ Ai × Ai

for every i,

and W (x, y) = 12

for almost every (x, y) ∈ Ai × Aj

for all distinct i, j ∈ [q].

Equivalently, the values of W on the q 2 block products are given by the following blockvalue matrix:



0

1 2  .. . 1 2

1 2

··· 0 ··· .. . . . . 1 2 ···

1 2 1 2



..  . 0

with blocks of equal size. So Bq⋆ is the graphon analogue of the family of balanced complete q-partite graphs, except that the off-diagonal blocks have value 12 instead of 1. Notation 4.2 (Balanced complete q-partite graphons). Define           A , . . . , A ⊆ [0, 1] are measurable,   1 q ⋆ [ [0, 1] = A ⊔ · · · ⊔ A , Uq := 1 : . 1 q   Ai × A j 1   λ(A ) = for every i ∈ [q]   i q    1≤i,j≤q  i̸=j

These are the balanced complete q-partite {0, 1}-valued graphons. By construction,   1 ⋆ ⋆ Bq = W ∈ W : W = U almost everywhere for some U ∈ Uq . 2 Notation 4.3 (Canonical representative of Bq⋆ ). We fix one balanced partition of [0, 1] by setting hq − 1 i ha − 1 a Aa := , for a = 1, . . . , q − 1, Aq := ,1 . q q q Thus 1 [0, 1] = A1 ⊔ · · · ⊔ Aq , λ(Aa ) = for every a ∈ [q]. q

18

YASMIN TOUSINEJAD AND VERA KOPONEN

Define the canonical element Wq⋆ ∈ Bq⋆ by ( 0, if x, y ∈ Aa for some a ∈ [q], Wq⋆ (x, y) := 1 2 , if x ∈ Aa , y ∈ Ab for some distinct a, b ∈ [q]. Equivalently, Wq⋆ =

1 1 [ 2

Aa × A b

.

1≤a,b≤q a̸=b

Every graphon in Bq⋆ is equal almost everywhere to a relabeling of Wq⋆ . Indeed, suppose that V ∈ Bq⋆ corresponds to a balanced partition [0, 1] = B1 ⊔ · · · ⊔ Bq . For each i ∈ [q], both Bi and Ai are measurable subsets of [0, 1] with Lebesgue measure 1/q. Equip these sets with their normalized restricted Lebesgue measures. By [16, Cor. A.11], there is a measure-preserving bijection ϕi : Bi → Ai . Since the same normalization factor q is used on both sets, ϕi also preserves the original Lebesgue measure. Pasting ϕ1 , . . . , ϕq gives a measure-preserving bijection ϕ : [0, 1] → [0, 1] such that ϕ(Bi ) = Ai up to null sets for every i ∈ [q]. Therefore V = (Wq⋆ )ϕ almost everywhere. In particular, δ□ (V, Wq⋆ ) = 0 for every V ∈ Bq⋆ . Define f ⋆ := π(W ⋆ ), e ⋆ := π(B ⋆ ). W B q q q q Then eq⋆ = {W fq⋆ }. B Consequently, for every graphon W , δ□ (W, Bq⋆ ) = δ□ (W, Wq⋆ ). Lemma 4.4. Fix r ≥ 3 and set q = r − 1. Let U be a {0, 1}-valued graphon and assume t(Kr , U ) = 0. Then

Z

1 U (x, y) dx dy ≤ 1 − . q [0,1]2 Moreover, equality holds if and only if δ□ (U, Uq⋆ ) = 0.

Proof. This is the Kr -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, Uq⋆ ) = 0. □ Lemma 4.5 (Entropy maximizers among graphons of zero Kr -density). Fix r ≥ 3 and set q = r − 1. Then 1 ln 2  sup{Ent(W ) : t(Kr , W ) = 0} = 1− . 2 q A graphon W with t(Kr , W ) = 0 attains this supremum if and only if δ□ (W, Bq⋆ ) = 0.

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

19

e ⋆ = {W f ⋆ }. Equivalently, the reduced maximizer set is the singleton B q q Remark 4.6. Lemma 4.5 can also be deduced from [9, Thm. 8.2]. In that theorem, take H = Kr and p = 1/2. Since χ(Kr ) = r, the graphon g appearing there is the balanced (r − 1)-partite {0, 1}-valued graphon. Hence pg = 12 g is a representative of the reduced f ⋆ ; equivalently, class W q f⋆. π(pg) = W q

The off-diagonal support of g has measure 1 − 1/q. Therefore     1 1 ln 2 Ent 1− , g = 2 2 q which also gives the value of the constrained maximum. For p = 1/2, the Erdős-Rényi rate function I 1 , defined in (5.9) below, satisfies 2

ln 2 − Ent(W ). 2 Thus minimizing I 1 under the constraint t(Kr , W ) = 0 is the same as maximizing 2 Ent(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. I 1 (W ) = 2

Proof of Lemma 4.5. Let W be a graphon satisfying t(Kr , W ) = 0. Set S := {(x, y) ∈ [0, 1]2 : W (x, y) > 0}, U := 1S . Since W is measurable and symmetric almost everywhere, the function U is also measurable and symmetric almost everywhere. Also, U only takes the values 0 and 1. Hence U is a graphon. We first show that U has zero Kr -density. By Remark 3.4, the integrand defining t(Kr , W ) is nonnegative. Since t(Kr , W ) = 0, we have Y W (xa , xb ) = 0 1≤a<b≤r

for almost every (x1 , . . . , xr ) ∈ [0, 1]r . If Y

U (xa , xb ) = 1,

1≤a<b≤r

then every factor U (xa , xb ) is equal to 1. By the definition of U , this means that every corresponding factor W (xa , xb ) is strictly positive. Thus Y W (xa , xb ) > 0. 1≤a<b≤r

This can happen only on a null set. Therefore t(Kr , U ) = 0. We now bound the entropy of W . Since W = 0 on S c and h(0) = 0, Definition 3.15 gives Z 1 h(W (x, y)) dx dy. Ent(W ) = 2 S By Lemma 3.16, we have h(p) ≤ ln 2 for every p ∈ [0, 1]. Hence Z ln 2 2 ln 2 (4.1) Ent(W ) ≤ λ (S) = U (x, y) dx dy. 2 2 [0,1]2

20

YASMIN TOUSINEJAD AND VERA KOPONEN

Since U is a {0, 1}-valued graphon and t(Kr , U ) = 0, Lemma 4.4 gives Z 1 U (x, y) dx dy ≤ 1 − . (4.2) q [0,1]2 Combining (4.1) and (4.2), we get ln 2 Ent(W ) ≤ 2

  1 1− . q

Therefore

  ln 2 1 sup{Ent(W ) : t(Kr , W ) = 0} ≤ 1− . 2 q Next we show that this upper bound is attained. Consider the canonical graphon Wq⋆ from Notation 4.3. The graphon Wq⋆ has value 0 on the diagonal blocks and value 1/2 on the off-diagonal blocks. Since q = r − 1, any choice of r points in [0, 1] contains two points in the same canonical block. For that pair, the corresponding factor in the Kr -integrand is 0. Hence t(Kr , Wq⋆ ) = 0.

(4.3)

The diagonal blocks have total measure 1/q, and the off-diagonal blocks have total measure 1 − 1/q. Using Definition 3.15, together with   1 h(0) = 0 and h = ln 2, 2 we obtain       1 1 1 ln 2 1 ⋆ (4.4) Ent(Wq ) = 1− h = 1− . 2 q 2 2 q Thus   1 ln 2 1− . sup{Ent(W ) : t(Kr , W ) = 0} = 2 q 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. Use the same notation as above, S = {(x, y) ∈ [0, 1]2 : W (x, y) > 0},

U = 1S .

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, Uq⋆ ) = 0. Equality in (4.1) gives h(W (x, y)) = ln 2

for almost every (x, y) ∈ S.

By Lemma 3.16, equality h(p) = ln 2 is possible only when p = 1/2. Hence 1 for almost every (x, y) ∈ S. W (x, y) = 2 Also, by the definition of S, we have W = 0 almost everywhere on S c . Therefore 1 W = U almost everywhere. 2 By Notation 4.2, the family Bq⋆ consists exactly of the graphons 12 V with V ∈ Uq⋆ , up to almost-everywhere equality. Since δ□ (U, Uq⋆ ) = 0,

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

21

we get 

 1 ⋆ δ□ U, Bq = 0. 2 Indeed, for every η > 0, choose Vη ∈ Uq⋆ such that δ□ (U, Vη ) < 2η. Then 12 Vη ∈ Bq⋆ , and by homogeneity of the cut norm,   1 1 1 δ□ U, Vη ≤ δ□ (U, Vη ) < η. 2 2 2 Since W = 21 U almost everywhere, it follows that δ□ (W, Bq⋆ ) = 0. Conversely, suppose that δ□ (W, Bq⋆ ) = 0. By Notation 4.3, this is equivalent to δ□ (W, Wq⋆ ) = 0. Using Lemma 3.14 and (4.3), we get t(Kr , W ) = t(Kr , Wq⋆ ) = 0. Using Lemma 3.17 and (4.4), we get   1 1− . 2 q

ln 2 Ent(W ) = Ent(Wq⋆ ) =

Thus W satisfies the constraint t(Kr , W ) = 0 and attains the maximum entropy. We have shown that the entropy maximizers are exactly the graphons W satisfying δ□ (W, Bq⋆ ) = 0. Finally, Notation 4.3 gives eq⋆ = {W fq⋆ }, B f ⋆ }. so the reduced maximizer set is the singleton {W q

□

Remark 4.7. By Lemma 3.18, the reduced mass of G ∈ Gn is

exp −r! w Kr (G) = exp −n2 Ln t(Kr , WG ) , Ln := wnr−2 . The corresponding graphon functional is therefore Tn (W ) = −Ln t(Kr , W ). For fixed L > 0, let   ⋆ e FL := π arg max {Ent(W ) − L t(Kr , W )} . W ∈W

For the ERGM with zero edge coefficient and clique coefficient −L, [9, Thm. 3.2] gives exponential concentration around FeL⋆ . The concentration rate is not given uniformly in L. Moreover, [9, Thm. 7.1] gives   f, W f ⋆ = 0. lim sup d□ W q L→∞ f e⋆ W ∈FL

These results describe an iterated limit in which one first lets n → ∞ with L fixed and then lets L → ∞. In the fixed-weight MLN considered here, Ln = wnr−2 ,

lim Ln = +∞.

n→∞

22

YASMIN TOUSINEJAD AND VERA KOPONEN

Thus n and Ln grow together. Since the concentration rate for fixed L is not uniform 2 in L, the fixed-coefficient theorem does not directly give a bound of the form e−cn with c > 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⋆ , the entropy drops. Lemma 4.8. Fix r ≥ 3 and set q = r − 1. For every ε > 0 there exists γr (ε) > 0 such that the following holds. If U is a {0, 1}-valued graphon and satisfies t(Kr , U ) = 0, then

δ□ (U, Uq⋆ ) ≥ ε,

Z

 1 − γr (ε). U ≤ 1− q [0,1]2

Proof. Fix ε > 0 and define   U is a {0, 1}-valued graphon,  Z mε := sup U : t(Kr , U ) = 0, .  [0,1]2  δ□ (U, Uq⋆ ) ≥ ε If the set inside the supremum is empty, take   1 1 1− . γr (ε) = 2 q The conclusion then holds automatically. Hence assume that the set is nonempty. By Lemma 4.4, 1 mε ≤ 1 − . q We claim that the inequality is strict. Assume instead that 1 mε = 1 − . q By the definition of the supremum, there exists a sequence (Un ) of {0, 1}-valued graphons such that Z 1 t(Kr , Un ) = 0, δ□ (Un , Uq⋆ ) ≥ ε, lim Un = 1 − . n→∞ [0,1]2 q en ∈ W f be the equivalence class of Un . By Notation 3.8, the metric space (W, f d□ ) Let U is compact; see [22, Thm. 9.23]. Hence, after passing to a subsequence, we may assume that en , U e) = 0 lim d□ (U n→∞

e ∈ W. f Choose any representative U ∈ U e . Since the metric on W f is induced for some U by δ□ , this means exactly that lim δ□ (Un , U ) = 0.

n→∞

By Lemma 3.14, the map t(Kr , ·) is continuous with respect to cut distance. Therefore lim t(Kr , Un ) = t(Kr , U ) = 0.

n→∞

Also, the limit still stays at least ε away from Uq⋆ . Indeed, δ□ (U, Uq⋆ ) ≥ δ□ (Un , Uq⋆ ) − δ□ (Un , U ), and letting n → ∞ gives

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

23

δ□ (U, Uq⋆ ) ≥ ε.

(4.5)

We also need the edge density to pass to the limit. For graphons W and V , and for any measure-preserving bijection ϕ, Z Z Vϕ V = [0,1]2

[0,1]2

by a change of variables. Therefore Z Z (W − V ) = [0,1]2

(W − V ϕ ) .

[0,1]2

By Definition 3.5, we may choose S = T = [0, 1] in the supremum defining the cut norm, so Z (W − V ϕ ) ≤ ∥W − V ϕ ∥□ . [0,1]2

Taking the infimum over all measure-preserving bijections ϕ gives Z (W − V ) ≤ δ□ (W, V ). [0,1]2

Apply this to (W, V ) = (Un , U ) and let n → ∞: Z

Z U = lim

(4.6)

n→∞

[0,1]2

1 Un = 1 − . q [0,1]2

Now define the positivity set of U by S := {(x, y) ∈ [0, 1]2 : U (x, y) > 0},

V := 1S .

The function V is measurable, {0, 1}-valued, and symmetric almost everywhere; hence it is a graphon. Moreover, 0 ≤ U ≤ V ≤ 1. We show first that V is a graphon of zero Kr -density. If Y V (xa , xb ) = 1, 1≤a<b≤r

then each factor U (xa , xb ) is strictly positive, so Y U (xa , xb ) > 0. 1≤a<b≤r

But the integrand defining t(Kr , U ) is nonnegative and has integral 0. So this can happen only on a set of measure 0. Hence t(Kr , V ) = 0. Because U ≤ V , equation (4.6) gives Z Z V ≥ [0,1]2

1 U =1− . q [0,1]2

On the other hand, V is a {0, 1}-valued graphon of zero Kr -density, so Lemma 4.4 gives Z 1 V ≤1− . q [0,1]2

24

YASMIN TOUSINEJAD AND VERA KOPONEN

Thus

Z

1 V =1− . q By the equality case in Lemma 4.4, this implies [0,1]2

δ□ (V, Uq⋆ ) = 0. Finally, V −U ≥0 pointwise and Z

Z

Z

(V − U ) =

V −

[0,1]2

[0,1]2

U = 0. [0,1]2

A nonnegative integrable function with integral 0 is zero almost everywhere. So U =V

almost everywhere.

Therefore δ□ (U, Uq⋆ ) = 0, contradicting the earlier bound δ□ (U, Uq⋆ ) ≥ ε in (4.5). This contradiction shows that 1 mε < 1 − . q Now define  1 γr (ε) := 1 − − mε > 0. q This is exactly the desired gap.

□

Lemma 4.9 (Entropy gap away from Bq⋆ ). Fix r ≥ 3 and set q = r − 1. For every ε > 0 there exists cr,ε > 0 such that every graphon W satisfying t(Kr , W ) = 0,

δ□ (W, Bq⋆ ) ≥ ε

also satisfies Ent(W ) ≤

1 ln 2  1− − cr,ε . 2 q

Proof. Fix ε > 0 and let W be a graphon with δ□ (W, Bq⋆ ) ≥ ε.

t(Kr , W ) = 0, As before, set

S := {(x, y) ∈ [0, 1]2 : W (x, y) > 0}, U := 1S . The function U is measurable, {0, 1}-valued, and symmetric almost everywhere; hence it is a graphon. Since t(Kr , W ) = 0, Remark 3.4 implies that Y W (xa , xb ) = 0 1≤a<b≤r

for almost every (x1 , . . . , xr ) ∈ [0, 1]r . If Y

U (xa , xb ) = 1,

1≤a<b≤r

then every factor W (xa , xb ) is strictly positive, and therefore Y W (xa , xb ) > 0. 1≤a<b≤r

This can happen only on a null set. Hence t(Kr , U ) = 0.

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

25

Moreover, W = 0 on S c , while h(u) ≤ ln 2 for every u ∈ [0, 1]. Therefore Z Z ln 2 2 1 ln 2 h(W (x, y)) dx dy ≤ U. Ent(W ) = λ (S) = 2 S 2 2 [0,1]2 We now split into two cases. Case 1: δ□ (U, Uq⋆ ) ≥ ε/2. Then Lemma 4.8 gives Z

 1 U ≤ 1− − γr (ε/2). q [0,1]2

Hence

ln 2  1  ln 2 1− − γr (ε/2). 2 q 2 Thus, in Case 1, the claimed bound holds with entropy loss ln22 γr (ε/2). Case 2: δ□ (U, Uq⋆ ) < ε/2. Choose U ⋆ ∈ Uq⋆ such that ε δ□ (U, U ⋆ ) < . 2 Set 1 V ⋆ := U ⋆ . 2 By Notation 4.2, the family Bq⋆ consists exactly of graphons that are equal almost everywhere to 12 U for some U ∈ Uq⋆ . Since U ⋆ ∈ Uq⋆ and V ⋆ = 12 U ⋆ , it follows that V ⋆ ∈ Bq⋆ . Since δ□ (W, Bq⋆ ) ≥ ε, we have δ□ (W, V ⋆ ) ≥ ε. Also, by homogeneity of the cut distance, 1  1 1  1 ε δ□ U, V ⋆ = δ□ U, U ⋆ = δ□ (U, U ⋆ ) < . 2 2 2 2 4 So the triangle inequality gives  3ε  1  1 δ□ W, U ≥ δ□ (W, V ⋆ ) − δ□ U, V ⋆ > . 2 2 4 Since  1  1 1 δ□ W, U ≤ W − U ≤ W− U , 2 2 □ 2 1 it follows that 1 3ε W− U > . 2 1 4 Because U = 1S and W = 0 on S c , this means Z 3ε 1 W− > . 2 4 S Ent(W ) ≤

Since U is {0, 1}-valued and is a graphon of zero Kr -density, Lemma 4.4 gives Z 1 λ2 (S) = U ≤1− . q [0,1]2 By Lemma 3.12(i), Z W− S

1 2

2

≤ λ2 (S)

Therefore Z  S

1 W− 2

2

 Z  1 2 W− . 2 S

3ε 2 4 ≥ . 1 − 1q

26

YASMIN TOUSINEJAD AND VERA KOPONEN

For every (x, y) ∈ S, we also have W (x, y) ∈ [0, 1]. Hence Lemma 3.16 gives  1 2 h(W (x, y)) ≤ ln 2 − 2 W (x, y) − for every (x, y) ∈ S. 2 Using this inequality in the entropy identity above, we obtain  Z   1 2 1 ln 2 − 2 W (x, y) − dx dy Ent(W ) ≤ 2 S 2 Z  ln 2 2 1 2 = dx dy λ (S) − W (x, y) − 2 2 S ε2 ln 2  1 9 ≤ 1− − . 2 q 16 (1 − 1q ) Here the last inequality uses the two estimates already proved above: Z  9 ε2 1 1 2 2 dx dy ≥ λ (S) ≤ 1 − and W (x, y) − . q 2 16 (1 − 1q ) S Combine the two cases and define ) ( 9 ln 2 ε2 cr,ε := min > 0. γr (ε/2), 2 16 (1 − 1q ) Then Ent(W ) ≤

ln 2  1 1− − cr,ε . 2 q □

The graphon removal lemma in [14, Lem. 2.3] is stated with the strict assumption t(Kr , W ) < δ. We will use the following non-strict version, obtained by applying that lemma with a smaller threshold. Lemma 4.10 (Graphon Kr removal). Fix r ≥ 3. For every η > 0 there exists δ = δKr (η) > 0 such that whenever a graphon W satisfies t(Kr , W ) ≤ δ, there exists a graphon W ′ with t(Kr , W ′ ) = 0,

∥W − W ′ ∥1 ≤ η.

Proof. Apply [14, Lem. 2.3] with F = Kr and error η. This gives a number δ0 > 0 such that, whenever t(Kr , W ) < δ0 , ′ there is a graphon W satisfying t(Kr , W ′ ) = 0

and

Now define δKr (η) :=

∥W − W ′ ∥1 ≤ η. δ0 . 2

If t(Kr , W ) ≤ δKr (η), then δ0 < δ0 . 2 Thus W satisfies the strict hypothesis of [14, Lem. 2.3], applied with F = Kr and error η. Hence there exists a graphon W ′ such that t(Kr , W ) ≤

t(Kr , W ′ ) = 0 This is the required graphon.

and

∥W − W ′ ∥1 ≤ η. □

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

27

Lemma 4.11 (Entropy is continuous in L1 ). For graphons U and V , and for every α > 0, (4.7)

| Ent(U ) − Ent(V )| ≤

1 ln 2 ∥U − V ∥1 ω(α) + , 2 2 α

where ω(α) := sup{|h(x) − h(y)| : x, y ∈ [0, 1], |x − y| ≤ α}. In particular, Ent is uniformly continuous on W with respect to ∥ · ∥1 . For every τ > 0 there exists η > 0 such that, for all graphons U and V , ∥U − V ∥1 ≤ η

| Ent(U ) − Ent(V )| ≤ τ.

=⇒

Proof. Fix α > 0 and define the two sets A := {(x, y) ∈ [0, 1]2 : |U (x, y) − V (x, y)| ≤ α}, B := {(x, y) ∈ [0, 1]2 : |U (x, y) − V (x, y)| > α}. Then 1 2

Z

1 ≤ 2

Z

| Ent(U ) − Ent(V )| =

(h(U ) − h(V )) [0,1]2

1 |h(U ) − h(V )| + 2 A

Z |h(U ) − h(V )|. B

On the set A we have |h(U ) − h(V )| ≤ ω(α), so Z |h(U ) − h(V )| ≤ ω(α). A

On the set B we use only the bound 0 ≤ h ≤ ln 2, and since B ⊆ [0, 1]2 , we get Z |h(U ) − h(V )| ≤ (ln 2) λ2 (B). B

Also, since |U − V | > α on B, ∥U − V ∥1 ≥ α λ2 (B),

so

λ2 (B) ≤

∥U − V ∥1 . α

Putting these estimates together yields (4.7). Finally, h is uniformly continuous on the compact interval [0, 1], and therefore lim ω(α) = 0.

α→0

Fix τ > 0. Choose α > 0 such that 1 τ ω(α) ≤ , 2 2 and then choose η > 0 such that ln 2 η τ ≤ . 2 α 2 If ∥U − V ∥1 ≤ η, then (4.7) gives | Ent(U ) − Ent(V )| ≤ τ. This proves the uniform continuity statement.

□

28

YASMIN TOUSINEJAD AND VERA KOPONEN

Lemma 4.12. Fix r ≥ 3 and set q = r − 1. For every ε > 0 there exist δr,ε > 0 and c′r,ε > 0 such that every graphon W satisfying t(Kr , W ) ≤ δr,ε

and

δ□ (W, Bq⋆ ) ≥ ε,

also satisfies Ent(W ) ≤

ln 2  1 1− − c′r,ε . 2 q

Proof. Fix ε > 0. Apply Lemma 4.9 with ε/2. This gives a constant cr,ε/2 > 0 such that every V that is a graphon of zero Kr -density and satisfies ε δ□ (V, Bq⋆ ) ≥ 2 satisfies ln 2  1 Ent(V ) ≤ 1− − cr,ε/2 . 2 q Choose η > 0 so small that ε η≤ 2 and 1 sup | Ent(U ) − Ent(V )| ≤ cr,ε/2 . 2 U,V ∈W ∥U −V ∥1 ≤η

This is possible by Lemma 4.11. Now apply Lemma 4.10 with this η. We obtain δr,ε > 0 such that every graphon W with t(Kr , W ) ≤ δr,ε admits a graphon W ′ of zero Kr -density satisfying ∥W − W ′ ∥1 ≤ η. Suppose that t(Kr , W ) ≤ δr,ε

and δ□ (W, Bq⋆ ) ≥ ε.

Choose a corresponding graphon W ′ such that ∥W − W ′ ∥1 ≤ η. Since δ□ (W, W ′ ) ≤ ∥W − W ′ ∥□ ≤ ∥W − W ′ ∥1 ≤ η, the triangle inequality gives ε δ□ (W ′ , Bq⋆ ) ≥ δ□ (W, Bq⋆ ) − δ□ (W, W ′ ) ≥ ε − η ≥ . 2 So Lemma 4.9 implies ln 2  1 Ent(W ′ ) ≤ 1− − cr,ε/2 . 2 q Also, 1 | Ent(W ) − Ent(W ′ )| ≤ cr,ε/2 2 by our choice of η. Therefore 1 ln 2  1 1 Ent(W ) ≤ Ent(W ′ ) + cr,ε/2 ≤ 1− − cr,ε/2 . 2 2 q 2 Thus the lemma holds with c′r,ε :=

1 c > 0. 2 r,ε/2 □

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

29

5. Proof of Theorem 2.7 Recall that we have fixed r ≥ 3 and w > 0 and we continue to let q := r − 1. We first prove some technical results in sections 5.1 – 5.3. Then we prove parts (i), (ii), and (iii) of Theorem 2.7, in this order, in sections 5.4 – 5.7. Notation 5.1 (Balanced q-partite entropy level). We write   ln 2 1 (5.1) sq := 1− . 2 q r

Corollary 2.6 shows that the graph-independent factor ewn disappears after normalization. Thus the probability measure Pn,r is determined by the reduced masses
exp −r! w Kr (G) , G ∈ Gn . By Lemma 3.18, t(Kr , WG ) =

r! Kr (G) . nr

Consequently, (5.2)

exp −r! w Kr (G) = exp −w t(Kr , WG )nr .

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 Kr -homomorphism density t(Kr , WGn ) = r! Kr (Gn )/nr goes to zero in probability for every fixed r ≥ 3 and every fixed w > 0, where Gn ∼ Pn,r . Lemma 5.2. Fix r ≥ 3 and w > 0. For every ε > 0 and every n ∈ N, define r A(r) n,ε := { G ∈ Gn : Kr (G) ≥ εn }.

Then   n 
−r! w εnr r . Pn,r A(r) ≤ |G | e = exp ln 2 − r! w εn n n,ε 2 In particular, for every ε > 0,
lim Pn,r A(r) n,ε = 0. n→∞

Equivalently, if Gn ∼ Pn,r , then for every δ > 0, lim P (t(Kr , WGn ) ≥ δ) = 0,

n→∞ (r)

because this event is {Gn ∈ An,δ/r! }. Thus t(Kr , WGn ) converges to 0 in probability. Proof. By (2.3), Pn,r (G) =

e−r! w Kr (G) . en,r Z

The denominator is at least 1, because a graph with no edges has no copy of Kr and contributes 1. So for every event A ⊆ Gn , X X Pn,r (A) = Pn,r (G) ≤ e−r! w Kr (G) . G∈A (r)

G∈A

Apply this with A = An,ε . On this event we have Kr (G) ≥ εnr , hence
r (r) −r! w εnr Pn,r A(r) ≤ |Gn | e−r! w εn . n,ε ≤ |An,ε | e

30

YASMIN TOUSINEJAD AND VERA KOPONEN

n Since |Gn | = 2( 2 ) , we have

−r! w εnr

|Gn | e

  n  ln 2 − r! w εnr . = exp 2

Because r ≥ 3, the term −r! w εnr is of strictly higher order than the exponent has limit −∞.

n 2

ln 2 = O(n2 ), so □

5.2. Graphs with a fixed positive clique density. A fixed positive lower bound on t(Kr , WG ) gives a negative term of order nr in the exponent. The total number of labeled graphs is only exp(O(n2 )). Since r ≥ 3, the penalty is stronger than this counting term. Lemma 5.3 (Fixed positive clique density is negligible). Fix 0 < δ ≤ 1. For every M > 0, there exists N = N (M, δ, r, w) such that, for every n ≥ N , X
exp −r! w Kr (G) ≤ exp(−M n2 ). (5.3) G∈Gn t(Kr ,WG )≥δ

Proof. If t(Kr , WG ) ≥ δ, then (5.2) gives
exp −r! w Kr (G) ≤ exp(−wδnr ). n Since |Gn | = 2( 2 ) , the total contribution of graphs satisfying t(Kr , WG ) ≥ δ is bounded by X
(5.4) exp −r! w Kr (G) ≤ exp(En ),

G∈Gn t(Kr ,WG )≥δ

where   n En := ln 2 − wδnr . 2

(5.5)

We now compare En with the n2 scale. By (5.5),
n En 2 = 2 ln 2 − wδnr−2 . n2 n Since
n n(n − 1) 1 1 2 = = − , 2 2 n 2n 2 2n we get En ln 2 ln 2 (5.6) = − − wδnr−2 . 2 n 2 2n Because r ≥ 3 and wδ > 0,   ln 2 ln 2 r−2 lim − − wδn = −∞. n→∞ 2 2n Therefore, by (5.6), there is N = N (M, δ, r, w) such that, for every n ≥ N , En ≤ −M. n2 Equivalently, En ≤ −M n2 . Combining this with (5.4), we obtain, for every n ≥ N , X
exp −r! w Kr (G) ≤ exp(En ) ≤ exp(−M n2 ). G∈Gn t(Kr ,WG )≥δ

This proves the lemma.

□

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

31

Thus graphs with t(Kr , WG ) ≥ δ have negligible total reduced mass on the n2 scale, for every fixed δ > 0. The main contribution must come from graphs with small empirical Kr -density. Lemma 4.5 identifies the largest entropy at zero Kr -density, and Lemma 4.12 gives a strict entropy loss away from Bq⋆ when the Kr -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 ⊆ W is called cut-closed if, whenever Wm ∈ F for every m and lim δ□ (Wm , W ) = 0,

m→∞

then W ∈ F. f Then the following Lemma 5.5. Let F ⊆ W be cut-closed, and let Fe be its image in W. statements hold. (1) If W ∈ F, V ∈ W, and δ□ (W, V ) = 0, then V ∈ F . (2) For every n ∈ N and every G ∈ Gn , WG ∈ F

⇐⇒

fG ∈ F. e W

(3) The set Fe is closed in the metric d□ . Proof. For the first statement, take the constant sequence Wm = W . Then lim δ□ (Wm , V ) = 0,

m→∞

so cut-closedness gives V ∈ F . e The forward implication in the second statement follows from the definition of F. fG ∈ F. e Then some V ∈ F satisfies δ□ (WG , V ) = 0. The first Conversely, suppose that W statement gives WG ∈ F. fm ∈ Fe and suppose that For the third statement, let W fm , W f ) = 0. lim d□ (W

m→∞

f . For each m, choose a representative Vm ∈ F of W fm . Choose a representative W of W By the definition of d□ , fm , W f ). δ□ (Vm , W ) = d□ (W Hence lim δ□ (Vm , W ) = 0.

m→∞

f ∈ F. e Cut-closedness gives W ∈ F , and therefore W

□

Notation 5.6 (Uniform measure on labeled graphs). For each n ∈ N, let Punif be the n n ( ) uniform probability measure on Gn . Since Gn contains 2 2 graphs, we have (5.7)

n

−( 2 ) Punif |A|, n (A) = 2

A ⊆ Gn .

We consider Gn as a probability space equipped with Punif n , and let Rn be the canonical random graph on this space; thus Rn (G) = G

for every G ∈ Gn .

Equivalently, each possible edge is present independently with probability 21 . Hence   1 Rn ∼ G n, . 2

32

YASMIN TOUSINEJAD AND VERA KOPONEN

f the event W fR ∈ Ae consists exactly of the graphs whose empirical For every Ae ⊆ W, n e Hence graphon class belongs to A.

fR ∈ Ae = Punif {G ∈ Gn : W fG ∈ A} e . (5.8) Punif W n n n Theorem 5.7. For a graphon W ∈ W, define Z 
 1 (5.9) I 1 (W ) := W ln(2W ) + (1 − W ) ln 2(1 − W ) dx dy, 2 2 [0,1]2 where 0 ln 0 = 0. f = π(W ), then The functional I 1 is constant on zero-cut-distance classes. Thus, if W 2

f ) := I 1 (W ) I 1 (W 2

2

is well-defined. Moreover, f ) = ln 2 − Ent(W f ). I 1 (W 2 2

(5.10)

f is closed, then If Fe ⊆ W n o 1 f e f ). (5.11) lim sup 2 ln Punif G ∈ G : W ∈ F ≤ − inf I 1 (W n G n f ∈F e 2 n→∞ n W Here inf ∅ = +∞, sup ∅ = −∞, and ln 0 = −∞. Proof. Recall that the binary entropy function is defined by h(u) = −u ln u − (1 − u) ln(1 − u),

u ∈ [0, 1],

with the convention 0 ln 0 = 0. For 0 < u < 1, we have


u ln(2u) + (1 − u) ln 2(1 − u) = u ln 2 + ln u + (1 − u) ln 2 + ln(1 − u)
= u + (1 − u) ln 2 + u ln u + (1 − u) ln(1 − u) = ln 2 − h(u). The same identity holds for u = 0 and u = 1 under the convention 0 ln 0 = 0. Hence it holds for every u ∈ [0, 1]. Integrating this identity gives ln 2 − Ent(W ). 2 By Lemma 3.17, entropy is unchanged under zero cut distance. Hence I 1 is also un2 f ) is well-defined and (5.10) follows. changed under zero cut distance, so I 1 (W I 1 (W ) = 2

2

Under the measure Punif from Notation 5.6, the random graph Rn has distribution n G(n, 12 ). We may therefore apply [10, Thm. 2.3] with p = 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 = 21 , 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). □ f be closed. For every n ∈ N, Lemma 5.8. Let Fe ⊆ W n o n o −(n f e f e 2) (5.12) Punif G ∈ G : W ∈ F = 2 G ∈ G : W ∈ F . n n G G n Consequently, (5.13)

lim sup n→∞

n o 1 f e f ). ln G ∈ G : W ∈ F ≤ sup Ent(W n G n2 f ∈F e W

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

33

e γ) such that, for every n ≥ N , If Fe ̸= ∅, then for every γ > 0 there is N = N (F, " # ! n o fG ∈ Fe ≤ exp f ) + γ n2 . (5.14) G ∈ Gn : W sup Ent(W f ∈F e W

Proof. Equation (5.12) follows immediately from the definition (5.7). Set n o e := G ∈ Gn : W fG ∈ Fe . Nn (F) e = 0, we obtain Using (5.12), with ln 0 = −∞ when Nn (F)
n n o 1 1 unif 2 e fG ∈ Fe . ln N ( F) = ln 2 + ln P G ∈ G : W n n n n2 n2 n2 Taking the upper limit and applying (5.11) gives 1 e ≤ ln 2 − inf I 1 (W f ). lim sup 2 ln Nn (F) 2 f ∈F e 2 n→∞ n W By (5.10), the right-hand side equals f ). sup Ent(W f ∈F e W

This proves (5.13). Finally, suppose that Fe ̸= ∅ and fix γ > 0. By (5.13), for all sufficiently large n, 1 f ) + γ. e ≤ sup Ent(W ln Nn (F) n2 f ∈F e W □

Exponentiating proves (5.14).

Lemma 5.9. Let F ⊆ W be a nonempty cut-closed family. For every γ > 0, there exists N = N (F, γ) such that, for every n ≥ N ,    (5.15) |{G ∈ Gn : WG ∈ F}| ≤ exp sup Ent(W ) + γ n2 . W ∈F

Equivalently, there is a nonnegative sequence αn (F) satisfying lim αn (F) = 0

n→∞

such that  (5.16)

|{G ∈ Gn : WG ∈ F}| ≤ exp

 sup Ent(W ) + αn (F) n

2



W ∈F

for every sufficiently large n. f Lemma 5.5 shows that Fe is closed and that Proof. Let Fe be the image of F in W. fG ∈ F. e WG ∈ F ⇐⇒ W Therefore |{G ∈ Gn : WG ∈ F}| =

n o fG ∈ Fe . G ∈ Gn : W

Entropy is constant on every zero-cut-distance class by Lemma 3.17, so f ) = sup Ent(W ). sup Ent(W W ∈F

f ∈F e W

e This proves (5.15). Now apply (5.14) to F. For the second form, set SF := sup Ent(W ) W ∈F

34

YASMIN TOUSINEJAD AND VERA KOPONEN

and Nn (F) := |{G ∈ Gn : WG ∈ F}| . If Nn (F) = 0, set bn = 0. If Nn (F) > 0, set   1 bn := max 0, 2 ln Nn (F) − SF . n We now show that limn→∞ bn = 0. Fix γ > 0. By (5.15), for all sufficiently large n,
Nn (F) ≤ exp (SF + γ)n2 . If Nn (F) = 0, then bn = 0. If Nn (F) > 0, the last inequality gives 1 ln Nn (F) − SF ≤ γ, n2 and therefore 0 ≤ bn ≤ γ. Since γ > 0 was arbitrary, it follows that lim bn = 0.

n→∞

Set αn (F) := bn +

1 . n

Then lim αn (F) = 0.

n→∞

If Nn (F) > 0, the definition of bn gives 1 ln Nn (F) ≤ SF + bn ≤ SF + αn (F). n2 Exponentiating gives (5.16). If Nn (F) = 0, then (5.16) is trivial. Thus (5.16) holds for every sufficiently large n. □ Lemma 5.10. Fix r ≥ 3 and set q = r − 1. The following subsets of W are cut-closed. (1) For every δ ∈ [0, 1], (r)

Fδ

:= {W ∈ W : t(Kr , W ) ≤ δ}.

(2) For every ε > 0, Dε,q := {W ∈ W : δ□ (W, Bq⋆ ) ≥ ε}. (3) For every δ ∈ [0, 1] and ε > 0, (r,q)

Fδ,ε Proof.

:= Fδ(r) ∩ Dε,q .

(1) Fix δ ∈ [0, 1]. We show that (r)

Fδ

= {W ∈ W : t(Kr , W ) ≤ δ}

is cut-closed. (r) Let (Wm )m≥1 be a sequence of graphons in Fδ , and suppose that lim δ□ (Wm , W ) = 0

m→∞

for some graphon W ∈ W. (r) Since each Wm belongs to Fδ , we have t(Kr , Wm ) ≤ δ

for every m.

By Lemma 3.14, the map W 7→ t(Kr , W )

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

35

is continuous in cut distance. Hence lim t(Kr , Wm ) = t(Kr , W ).

m→∞

Taking the limit in t(Kr , Wm ) ≤ δ gives t(Kr , W ) ≤ δ. Therefore

(r)

W ∈ Fδ . (r)

So Fδ is cut-closed. (2) Fix ε > 0. We prove that Dε,q = {W ∈ W : δ□ (W, Bq⋆ ) ≥ ε} is cut-closed. If H is a nonempty family of graphons, then the function W 7→ δ□ (W, H) is continuous in cut distance. Indeed, let U, V ∈ W. For every H ∈ H, the triangle inequality gives δ□ (U, H) ≤ δ□ (U, V ) + δ□ (V, H). Taking the infimum over all H ∈ H gives δ□ (U, H) ≤ δ□ (U, V ) + δ□ (V, H). So δ□ (U, H) − δ□ (V, H) ≤ δ□ (U, V ). Now if we switch the roles of U and V , we get δ□ (V, H) − δ□ (U, H) ≤ δ□ (U, V ). Therefore |δ□ (U, H) − δ□ (V, H)| ≤ δ□ (U, V ). Thus W 7→ δ□ (W, H) is continuous. Now apply this with H = Bq⋆ . This family is nonempty, because Wq⋆ ∈ Bq⋆ by Notation 4.3. Hence W 7→ δ□ (W, Bq⋆ ) is continuous in cut distance. Now let (Wm )m≥1 be a sequence of graphons in Dε,q , and suppose that lim δ□ (Wm , W ) = 0

m→∞

for some graphon W ∈ W. Since each Wm belongs to Dε,q , we have δ□ (Wm , Bq⋆ ) ≥ ε

for every m.

By the continuity established above, we have lim δ□ (Wm , Bq⋆ ) = δ□ (W, Bq⋆ ).

m→∞

Taking the limit in δ□ (Wm , Bq⋆ ) ≥ ε gives δ□ (W, Bq⋆ ) ≥ ε.

36

YASMIN TOUSINEJAD AND VERA KOPONEN

Therefore W ∈ Dε,q . So Dε,q is cut-closed. (3) Fix δ ∈ [0, 1] and ε > 0. We show that (r,q)

Fδ,ε

(r)

= Fδ ∩ Dε,q

is cut-closed. (r,q) Let (Wm )m≥1 be a sequence of graphons in Fδ,ε , and suppose that lim δ□ (Wm , W ) = 0

m→∞

for some graphon W ∈ W. Since (r,q) (r) Wm ∈ Fδ,ε = Fδ ∩ Dε,q , we have (r)

Wm ∈ Fδ

Wm ∈ Dε,q

and

for every m. (r) By item (1), Fδ is cut-closed. Hence (r)

W ∈ Fδ . By item (2), Dε,q is cut-closed. Hence W ∈ Dε,q . Therefore (r)

(r,q)

W ∈ Fδ ∩ Dε,q = Fδ,ε . (r,q)

So Fδ,ε

is cut-closed. □

5.4. The reduced free-energy limit. Lemma 5.11 (Balanced multipartite lower bound). Let n ∈ N, and use m, a ∈ Z≥0 ,

n = qm + a,

0 ≤ a < q.

Then, with sq as in Notation 5.1,      a q ln 2 ln 2 2 2 e a 1− (5.17) ≥ exp sq n − . Zn,r ≥ exp sq n − 2 q 8 Proof. Write [n] as the disjoint union of q possibly empty sets [n] = V1 ⊔ · · · ⊔ Vq whose sizes differ by at most one. Thus a sets have size m + 1, and the remaining q − a sets have size m. Put ni := |Vi |, i = 1, . . . , q. Let M be the number of unordered pairs of vertices lying in different parts. Then X M= ni nj . 1≤i<j≤q

Since q X i=1

!2 ni

=

q X i=1

n2i + 2

X 1≤i<j≤q

ni nj ,

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

37

we have 1 M= 2

(5.18)

n2 −

q X

! n2i

.

i=1

We now compute the sum of the squared part sizes. By the choice of the partition, q X

n2i = (q − a)m2 + a(m + 1)2

i=1

= qm2 + 2am + a. On the other hand, since n = qm + a, a2 n2 = qm2 + 2am + . q q Therefore (5.19)

q X i=1

2

  a +a 1− . q q

n n2i =

Substituting (5.19) into (5.18) gives     1 1 1 a 2 (5.20) M= 1− n − a 1− . 2 q 2 q Now choose an arbitrary subset of these M possible between-part edges, and put no edges inside the parts. This gives exactly 2M labeled graphs on [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−1, none of these graphs contains a copy of Kr . Therefore each of these graphs has reduced mass exp(−r! w Kr (G)) = 1. en,r , and so Thus all these graphs contribute 1 each to Z en,r ≥ 2M . Z Multiplying (5.20) by ln 2 and then using (5.1), we obtain     1 ln 2 a ln 2 1− n2 − a 1− (ln 2)M = 2 q 2 q   ln 2 a = sq n2 − a 1− . 2 q Consequently,    a ln 2 M 2 2 = exp sq n − a 1− . 2 q en,r ≥ 2M , this proves the first inequality in (5.17). Together with Z Finally, the function   x x 1− q is maximized on [0, q] at x = q/2, where its value is q/4. Since 0 ≤ a < q, we have   a q 0≤a 1− ≤ . q 4 Hence   ln 2 a q ln 2 − a 1− . ≥− 2 q 8

38

YASMIN TOUSINEJAD AND VERA KOPONEN

□

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 → ∞, and only afterward let L → ∞. Proof of Theorem 2.7(i). We prove the upper and lower bounds separately. Upper bound. Fix L > 0 and define X
(L) := exp −Ln2 t(Kr , WG ) . Zen,r G∈Gn

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. Moreover, t(Kr , W ) is continuous in cut distance by Lemma 3.14. Hence the functional W 7−→ −L t(Kr , W ) is bounded and continuous. We may therefore apply [9, Thm. 3.1], which gives 1 e(L) = sup {Ent(W ) − L t(Kr , W )} . (5.21) lim ln Z n,r n→∞ n2 W ∈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.

The rate functional I used there satisfies Z   1 W ln W + (1 − W ) ln(1 − W ) dx dy = − Ent(W ), I(W ) = 2 [0,1]2 with the usual convention at 0 and 1. Thus, at β2 = −L, their variational value is exactly sup {Ent(W ) − L t(Kr , W )} . W ∈W

Moreover, e2β1 1 = . 2β 1 2 1+e Theorem 7.1 of that paper therefore gives the limiting value   r−2 ln 2 1 ln 2 = 1− = sq , 2(r − 1) 2 q where we used q = r − 1. It follows that χ(Kr ) = r

(5.22)

and

p=

lim sup {Ent(W ) − L t(Kr , W )} = sq .

L→∞ W ∈W

We now compare the auxiliary model with the model in the theorem. Write Ln := wnr−2 . By (5.2), the reduced mass of a graph G is

exp −r! w Kr (G) = exp −n2 Ln t(Kr , WG ) . Since r ≥ 3 and w > 0, we have lim Ln = +∞.

n→∞

Thus, for every fixed L > 0, we have Ln ≥ L for all sufficiently large n. Since t(Kr , WG ) ≥ 0, this gives

exp −n2 Ln t(Kr , WG ) ≤ exp −n2 L t(Kr , WG ) .

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

39

Summing this inequality over all G ∈ Gn yields (L) en,r ≤ Zen,r Z

for all sufficiently large n. Taking logarithms, dividing by n2 , and using (5.21), we obtain 1 e(L) ln Z n,r n→∞ n2 = sup {Ent(W ) − L t(Kr , W )} .

lim sup Fn,r (w) ≤ lim n→∞

W ∈W

This holds for every fixed L > 0. We may therefore let L → ∞. Equation (5.22) then gives lim sup Fn,r (w) ≤ sq . n→∞

Lower bound. A graph whose edges lie only between the parts of a q-partite partition contains no copy of Kr , because q = r − 1. Such a graph therefore has reduced mass 1. Lemma 5.11 counts these graphs and gives Fn,r (w) ≥ sq −

q ln 2 . 8n2

Taking the lower limit gives lim inf Fn,r (w) ≥ sq . n→∞

The upper and lower bounds now agree. Therefore   ln 2 1 lim Fn,r (w) = sq = 1− . n→∞ 2 q □ 5.5. Exponential concentration in cut distance. We now prove Theorem 2.7(ii). Fix ε > 0. The event we need to estimate is δ□ (WGn , Bq⋆ ) ≥ ε. After choosing a small number δ > 0, we separate this event according to the empirical clique density t(Kr , WGn ). The part with t(Kr , WGn ) ≥ δ has very small total reduced mass by Lemma 5.3. The remaining part has t(Kr , WGn ) < δ

and

δ□ (WGn , Bq⋆ ) ≥ ε.

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−2 , for which limn→∞ Ln = +∞, the proof below establishes the required uniform diagonal estimate directly. Proof of Theorem 2.7(ii). Fix ε > 0, and let Gn ∼ Pn,r . Choose δ0 = δr,ε > 0

and

c′ = c′r,ε > 0

from Lemma 4.12, and set δ := min{δ0 , 1}. The conclusion of Lemma 4.12 still holds under the stronger condition t(Kr , W ) ≤ δ. Define  An,ε := G ∈ Gn : δ□ (WG , Bq⋆ ) ≥ ε .

40

YASMIN TOUSINEJAD AND VERA KOPONEN

By (2.3), P(Gn ∈ An,ε ) =

Rn,ε , en,r Z

where X

Rn,ε :=

exp −r! w Kr (G) .

G∈An,ε

Using (5.2), set large small Rn,ε = Rn,ε + Rn,ε ,

where X

large := Rn,ε

exp −w t(Kr , WG )nr

G∈An,ε t(Kr ,WG )≥δ

and X

small := Rn,ε

exp −w t(Kr , WG )nr .

G∈An,ε t(Kr ,WG )<δ

For every M > 0, Lemma 5.3 gives, for all sufficiently large n, (5.23)

large Rn,ε ≤ exp(−M n2 ).

small is at most 1, and every graph in this sum satisfies Every summand in Rn,ε (r,q)

WG ∈ Fδ,ε . Hence small Rn,ε ≤

n o (r,q) G ∈ Gn : WG ∈ Fδ,ε .

(r,q)

If Fδ,ε is empty, this upper bound is 0. If it is nonempty, then it is cut-closed by Lemma 5.10, and Lemma 4.12 gives Ent(W ) ≤ sq − c′ .

sup (r,q) W ∈Fδ,ε

Lemma 5.9, with counting error c′ /4, now gives, for every sufficiently large n,    3c′ small (5.24) Rn,ε ≤ exp sq − n2 . 4 Set Cq :=

q ln 2 . 8

Lemma 5.11 gives en,r ≥ exp(sq n2 − Cq ). Z Choose M = 1 + c′ . Combining this estimate with (5.23) and (5.24) gives  
3c′ 2 2 P(Gn ∈ An,ε ) ≤ exp −(M + sq )n + Cq + exp − n + Cq . 4 For every sufficiently large n, both terms on the right are at most exp(−c′ n2 /2). Increasing the threshold for n once more gives 2 exp(−c′ n2 /2) ≤ exp(−c′ n2 /4). Therefore, for every sufficiently large n,
P δ□ (WGn , Bq⋆ ) ≥ ε ≤ exp(−c′ n2 /4). The theorem follows with c = c′ /4. The constant c depends only on ε and r. The threshold for n may also depend on w, through Lemma 5.3. □

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

41

5.6. Probability bounds needed for the rounding argument. Lemma 5.12. The following probability bounds hold: (i) Markov’s inequality. If Y ≥ 0 almost surely and t > 0, then E[Y ] . t (ii) Hoeffding’s inequality. Let m ≥ 1, and let Y1 , . . . , Ym be independent random variables. Suppose that, for each i ∈ [m], there are real numbers ai ≤ bi such that P(Y ≥ t) ≤

ai ≤ Yi ≤ bi almost surely. Set m X V := (bi − ai )2 . i=1

If V > 0, then, for every t ≥ 0, P

m X

Yi −

i=1

m X

! E[Yi ] ≥ t

i=1

  2t2 . ≤ 2 exp − V

If V = 0, then m X

m X

Yi =

i=1

E[Yi ]

i=1

almost surely. Consequently, for every t > 0, P

m X i=1

Yi −

m X

! E[Yi ] ≥ t

= 0.

i=1

In particular, if 0 ≤ Yi ≤ 1 almost surely for every i ∈ [m], and if S :=

m X

Yi ,

i=1

then, for every t ≥ 0, 2t2 P |S − E[S]| ≥ t ≤ 2 exp − m



 .

(iii) McDiarmid’s inequality. Let m ≥ 1, let S1 , . . . , Sm be finite sets, and let X1 , . . . , Xm be independent random variables such that Xi ∈ Si almost surely for every i ∈ [m]. Let f : S1 × · · · × Sm → R be a function. Assume that there is a number L > 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 , . . . , x′i , . . . , xm ) ≤ L for every i ∈ [m], every xi , x′i ∈ Si , and every fixed choice of the other coordinates. Then, for every t ≥ 0,   2t2 P (|f (X1 , . . . , Xm ) − E[f (X1 , . . . , Xm )]| ≥ t) ≤ 2 exp − . mL2

42

YASMIN TOUSINEJAD AND VERA KOPONEN

Proof. Item (i) is Markov’s inequality; see [23, Thm. 3.1], with the notation there renamed as X = Y and a = t. For item (ii), first assume that V > 0. If t > 0, Hoeffding’s inequality [23, Thm. 4.14] gives !   m m X X 2t2 P . Yi − E[Yi ] ≥ t ≤ 2 exp − V i=1

i=1

If t = 0, the same bound is also true, because the probability on the left is at most 1, while the right-hand side is 2. Now assume that V = 0. Then m X (bi − ai )2 = 0. i=1

Each term in this sum is nonnegative, so bi − ai = 0

for every i ∈ [m].

Thus ai = bi for every i. Since ai ≤ Yi ≤ bi almost surely, each Yi is almost surely constant. Hence almost surely for every i ∈ [m].

Yi = E[Yi ] Adding over i = 1, . . . , m gives

m X

m X

Yi =

i=1

E[Yi ]

i=1

almost surely. Therefore, for every t > 0, P

m X

Yi −

i=1

m X

! E[Yi ] ≥ t

= 0.

i=1

For the last part of item (ii), assume that 0 ≤ Yi ≤ 1

almost surely for every i ∈ [m],

and set S :=

m X

Yi .

i=1

Taking ai = 0

and

bi = 1

for every i gives V =

m X i=1

(bi − ai )2 =

m X

1 = m.

i=1

The bound already proved therefore gives, for every t ≥ 0,   2t2 P (|S − E[S]| ≥ t) ≤ 2 exp − . m For item (iii), 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 = m, c = L, and λ = t gives the stated bound for t > 0. The theorem applies here because the random variables take values in finite sets. For t = 0, the bound is immediate, since the right-hand side is 2. □

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

43

5.7. Transforming cut-distance closeness to a vertex partition. The next lemma turns cut-distance closeness to Bq⋆ 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 ≥ 2 and 0 < ε ≤ 1, and set ε . ρ := 100q 2 There exists Ndet = Ndet (ε, q) such that the following holds for every n ≥ Ndet . If G is a graph on [n] and δ□ (WG , Bq⋆ ) < ρ, then there is a partition [n] = V1 ⊔ · · · ⊔ Vq with |Vα | − n/q ≤ εn for every α ∈ [q], each Vα has size at least 2, eG (Vα , Vβ ) 1 − ≤ε for all distinct α, β ∈ [q], |Vα ||Vβ | 2 q X

eG (Vα ) ≤

α=1

and

εn2 , 10q

Pq

α=1 eG (Vα )
≤ ε. |Vα | α=1 2

Pq

Moreover, if G′ is obtained from G by deleting all edges whose endpoints lie in the same part, then G′ is q-partite and ε . dedit (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 )ni,j=1 be the adjacency matrix of G. Thus aij = aji ,

aii = 0.

Let Wq⋆ and its canonical blocks A1 , . . . , Aq be as in Notation 4.3. By that notation, δ□ (WG , Bq⋆ ) = δ□ (WG , Wq⋆ ) < ρ. Since the infimum in the definition of cut distance is strictly smaller than ρ, there is a measure-preserving bijection ψ : [0, 1] → [0, 1] such that ∥WG − (Wq⋆ )ψ ∥□ < ρ. Set ϕ := ψ −1 . Since the cut norm is invariant under measure-preserving relabelings, we get ∥WGϕ − Wq⋆ ∥□ = ∥(WG − (Wq⋆ )ψ )ϕ ∥□ (5.25)

= ∥WG − (Wq⋆ )ψ ∥□ < ρ.

Let I1 , . . . , In be the intervals from Definition 3.2. These intervals form a measurable partition of [0, 1].

44

YASMIN TOUSINEJAD AND VERA KOPONEN

Define Ji := ϕ−1 (Ii ), i ∈ [n]. Then J1 , . . . , Jn form a measurable partition of [0, 1], and 1 λ(Ji ) = for every i ∈ [n]. n For i ∈ [n] and α ∈ [q], set pi,α := nλ(Ji ∩ Aα ). For each fixed i, these numbers can be used as probabilities: 0 ≤ pi,α ≤ 1

q X

and

pi,α = 1.

α=1

Also, for each fixed α, n X

pi,α = nλ(Aα ) =

i=1

n . q

We now define an auxiliary random coloring of the vertices. Let Σ := (ξ1 , . . . , ξn ) be an [q]n -valued random vector whose coordinates are independent and satisfy i ∈ [n], α ∈ [q].

Pcol (ξi = α) = pi,α , Equivalently, for every C = (C1 , . . . , Cn ) ∈ [q]n , Pcol (Σ = C) =

n Y

pi,Ci .

i=1

Here Pcol and Ecol denote probability and expectation with respect to this product probability measure on [q]n . For a coloring C = (C1 , . . . , Cn ) ∈ [q]n , define its color classes by Vα (C) := {i ∈ [n] : Ci = α},

α ∈ [q].

The parts are almost balanced. For every α ∈ [q] and i ∈ [n], set (α)

Zi

:= 1{ξi =α} . (α)

(α)

For each fixed α, the random variables Z1 , . . . , Zn (α)

0 ≤ Zi

≤1

are independent and satisfy

almost surely.

Moreover, |Vα (Σ)| =

n X

(α)

Zi

i=1

and Ecol [|Vα (Σ)|] =

n X

(α)

Ecol [Zi ] =

n X

pi,α =

i=1 i=1 (α) (α) Applying Lemma 5.12(ii) to Z1 , . . . , Zn , with m = n and

t=

n . q

εn , 10q

gives  Pcol

n εn |Vα (Σ)| − ≥ q 10q



 ε2 ≤ 2 exp − n . 50q 2 

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

45

Define  Ωbal :=

 εn n ≤ for every α ∈ [q] . C ∈ [q] : |Vα (C)| − q 10q n

By the union bound, Pcol (Ωcbal ) ≤ 2q exp

(5.26)



 ε2 − n . 50q 2

If C ∈ Ωbal , then for every α ∈ [q], |Vα (C)| −

εn n ≤ ≤ εn. q 10q

Moreover, since ε ≤ 1, εn 9n n − ≥ . q 10q 10q Thus, if n ≥ 2q, then |Vα (C)| ≥ 9/5. Since |Vα (C)| is an integer, every part has at least two vertices. After relabeling by ϕ, the empirical graphon WGϕ is equal to aij on Ji ×Jj , except possibly on a null set. Hence, for all α, β ∈ [q], Z n X WGϕ (x, y) dx dy = aij λ(Ji ∩ Aα )λ(Jj ∩ Aβ ) |Vα (C)| ≥

Aα ×Aβ

i,j=1 n

=

(5.27)

1 X aij pi,α pj,β . n2 i,j=1

Edges inside the parts. Fix α ∈ [q]. Then n X

2eG (Vα (Σ)) =

aij 1{ξi =α} 1{ξj =α} .

i,j=1

The diagonal terms vanish because aii = 0. For i ̸= j, independence gives h i Ecol 1{ξi =α} 1{ξj =α} = pi,α pj,α . Using (5.27), we obtain 2 Ecol [eG (Vα (Σ))] = n2

Z Aα ×Aα

WGϕ .

The graphon Wq⋆ is 0 on Aα × Aα . Therefore Z 0≤ Aα ×Aα

Z

WGϕ =

Aα ×Aα

(WGϕ − Wq⋆ ) ≤ ∥WGϕ − Wq⋆ ∥□ < ρ.

Hence Ecol [eG (Vα (Σ))] ≤

ρn2 . 2

Summing over all α ∈ [q], we get Ecol

" q X

# eG (Vα (Σ)) ≤

α=1

qρn2 . 2

For C ∈ [q]n , set Y (C) :=

q X α=1

eG (Vα (C)).

46

YASMIN TOUSINEJAD AND VERA KOPONEN

Define

 Ωin :=

εn2 C ∈ [q] : Y (C) ≤ 10q n

 .

By Lemma 5.12(i), Ecol [Y (Σ)] εn2 /(10q) qρn2 /2 ≤ 2 εn /(10q) 5q 2 ρ = ε 1 = . 20

Pcol (Ωcin ) ≤

(5.28)

Here the last equality uses ρ = ε/(100q 2 ). Lemma 3.12(ii) gives !    q  q X |Vα (C)| 1 X 1 n2 2 = |Vα (C)| − n ≥ −n . 2 2 2 q α=1

α=1

If n ≥ 2q, then  q  X |Vα (C)| 2

α=1

n2 . 4q

≥

Thus every C ∈ Ωin satisfies Pq

εn2 /(10q) 2ε α=1 eG (Vα (C)) ≤ = < ε.
2 |Vα (C)| n /(4q) 5 α=1 2

Pq

Edges between distinct parts. For 1 ≤ α < β ≤ q and C ∈ [q]n , define Fα,β (C) := eG (Vα (C), Vβ (C)). Fix 1 ≤ α < β ≤ q. Since Vα (Σ) and Vβ (Σ) are disjoint, Fα,β (Σ) =

n X

aij 1{ξi =α} 1{ξj =β} .

i,j=1

Each edge between the two color classes is counted exactly once. The diagonal terms vanish because aii = 0. For i ̸= j, independence gives h i Ecol 1{ξi =α} 1{ξj =β} = pi,α pj,β . Therefore Ecol [Fα,β (Σ)] =

n X

aij pi,α pj,β .

i,j=1

Using (5.27), we obtain 1 Ecol [Fα,β (Σ)] = n2

Z Aα ×Aβ

WGϕ (x, y) dx dy.

On Aα × Aβ , the graphon Wq⋆ equals 1/2. Since λ2 (Aα × Aβ ) = we have

Z Aα ×Aβ

1 , q2

Wq⋆ (x, y) dx dy =

1 . 2q 2

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

47

By Definition 3.5, applied with S = Aα and T = Aβ , and by (5.25), Z Z ϕ WG − Wq⋆ Aα ×Aβ

Aα ×Aβ

Z = Aα ×Aβ

(WGϕ − Wq⋆ )

≤ ∥WGϕ − Wq⋆ ∥□ < ρ. Consequently, Ecol [Fα,β (Σ)] −

(5.29)

n2 ≤ ρn2 . 2q 2

Thus n2 /(2q 2 ) is the deterministic target value; in general it is not the exact value of Ecol [Fα,β (Σ)]. Changing one coordinate of C can change the counted status only of edges incident to the corresponding vertex. There are at most n − 1 such edges, and each contributes at most 1 to the change. Hence Fα,β changes by at most n − 1, and therefore by at most n. By Lemma 5.12(iii), with εn2 t= , 40q 2 we obtain     ε2 εn2 ≤ 2 exp − n . Pcol |Fα,β (Σ) − Ecol [Fα,β (Σ)]| > 40q 2 800q 4 Define

  εn2   |Fα,β (C) − Ecol [Fα,β (Σ)]| ≤ Ωcross := C ∈ [q]n : 40q 2  .  for every 1 ≤ α < β ≤ q By the union bound,   ε2 c (5.30) Pcol (Ωcross ) ≤ q(q − 1) exp − n . 800q 4 If C ∈ Ωcross , then for every α < β, the definition of Ωcross , (5.29), and the triangle inequality give eG (Vα (C), Vβ (C)) −

n2 2q 2

≤ |Fα,β (C) − Ecol [Fα,β (Σ)]| + Ecol [Fα,β (Σ)] − (5.31)

εn2 + ρn2 40q 2 7εn2 = 200q 2 εn2 ≤ . 20q 2 ≤

Assume also that C ∈ Ωbal . Let n |Vα (C)| = + ∆α , q

|Vβ (C)| =

n + ∆β . q

n2 2q 2

48

YASMIN TOUSINEJAD AND VERA KOPONEN

Then |∆α |, |∆β | ≤

εn . 10q

Hence |Vα (C)||Vβ (C)| −

n n2 ≤ |∆ | + |∆ | + |∆α ∆β | α β q2 q εn2 ε2 n 2 ≤ 2 + 5q 100q 2 21εn2 ≤ 100q 2 εn2 ≤ 2. 4q

Therefore 1 n2 εn2 |Vα (C)||Vβ (C)| − 2 ≤ 2 . 2 2q 8q

(5.32)

Combining (5.31) and (5.32), and using the triangle inequality, gives 1 eG (Vα (C), Vβ (C)) − |Vα (C)||Vβ (C)| 2 1 n2 n2 − |Vα (C)||Vβ (C)| ≤ eG (Vα (C), Vβ (C)) − 2 + 2q 2q 2 2 εn2 7εn2 εn2 + = . ≤ 20q 2 8q 2 40q 2 The balance event also gives |Vα (C)||Vβ (C)| ≥

81 n2 4 n2 ≥ . 100 q 2 5 q2

Thus eG (Vα (C), Vβ (C)) 1 7εn2 /(40q 2 ) − ≤ |Vα (C)||Vβ (C)| 2 (4/5)n2 /q 2 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) so large that, for every n ≥ Ndet , n ≥ 2q,  ε2 1 2q exp − n ≤ , 2 50q 40   2 ε 1 q(q − 1) exp − n ≤ . 800q 4 40 

(5.33)

It follows from (5.26), (5.28), (5.30), and (5.33) that Pcol (Ωcbal ) ≤

1 , 40

Pcol (Ωcin ) ≤

1 , 20

Pcol (Ωccross ) ≤

1 . 40

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

49

Therefore
1 1 1 Pcol Ωbal ∩ Ωin ∩ Ωcross ≥ 1 − − − 40 20 40 9 = > 0. 10 So there exists a coloring C ∈ Ωbal ∩ Ωin ∩ Ωcross . Set 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′ be obtained from G by deleting all edges inside the parts V1 , . . . , Vq . Then G′ is q-partite, and |E(G) △ E(G′ )| =

q X

eG (Vα ) ≤

α=1

εn2 . 10q

By the definition of dedit in Section 1, dedit (G, G′ ) =

|E(G) △ E(G′ )| ε ≤ . 2 n 10q □

We now use the cut-distance concentration theorem to prove the finite-graph structure theorem. Proof of Theorem 2.7(iii). Fix ε > 0. Since Lemma 5.13 is stated for parameters at most 1, set η η := min{ε, 1}, ρ := . 100q 2 Let Gn ∼ Pn,r . Applying Theorem 2.7(ii) with the parameter ρ, we get constants c0 = c0 (ρ, r) > 0

and

N0 = N0 (ρ, r, w)

such that, for every n ≥ N0 ,
P δ□ (WGn , Bq⋆ ) ≥ ρ ≤ exp(−c0 n2 ). Let Ndet = Ndet (η, q) be the threshold from Lemma 5.13, and define n0 := max{N0 , Ndet }. Then, for every n ≥ n0 , with probability at least 1 − exp(−c0 n2 ), we have δ□ (WGn , Bq⋆ ) < ρ. On this event, Lemma 5.13, applied with η in place of ε, gives a partition [n] = V1 ⊔ · · · ⊔ Vq satisfying all the conclusions of that lemma with parameter η. Since η ≤ ε, the same partition satisfies the required bounds in Theorem 2.7(iii) with parameter ε.

50

YASMIN TOUSINEJAD AND VERA KOPONEN

In particular, if G′n is obtained from Gn by deleting all edges whose endpoints lie in the same part, then G′n is q-partite and η ε ε dedit (Gn , G′n ) ≤ ≤ ≤ , 10q 10q 2 because q ≥ 2. Thus the theorem holds with c := c0 . Since ρ = η/(100q 2 ), and since q = r − 1, the constant c depends only on ε and r. The threshold n0 may also depend on w. □ 6. Examples and consequences We first discuss the boundary case r = 2 and the first case covered by Theorem 2.7, namely r = 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 − 1 colors. Finally, we extend the model to several fixed clique penalties. 6.1. The case r = 2. The notions defined in Section 2 are straightforwardly extended to the case r = 2, and we get N2 (G) = n2 − 2|E(G)|, and

n en,2 = 1 + e−2w ( 2 ) . Z The possible edges are therefore independent, and each is present with probability

e−2w 1 = . −2w 1+e 1 + e2w
Thus Pn,2 is exactly the G n, 1/(1 + e2w ) distribution. In particular, the (r − 1)-partite behavior in Theorem 2.7 begins at r = 3. 6.2. The case r = 3. Here q = r − 1 = 2. By Corollary 2.6, the reduced mass of a graph G is e−6wK3 (G) . Thus triangles are penalized. By Theorem 2.7(ii), the empirical graphon converges in probability, in cut distance, to the class represented by W2⋆ . The canonical representative W2⋆ has two equal blocks and takes value 0 within each block and 1/2 between the blocks. 6.3. A stochastic block model limit. For m ∈ N and probability measures α and β on Gm , their total variation distance is 1 X dTV (α, β) := |α(J) − β(J)|. 2 J∈Gm

Definition 6.1. For m ∈ N, J ∈ Gm , and a graphon W , define the induced density of J in W by Z Y Y
1 − W (xi , xj ) dx1 · · · dxm . tind (J, W ) := W (xi , xj ) [0,1]m {i,j}∈E(J)

1≤i<j≤m {i,j}∈E(J) /

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)].

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

51

Corollary 6.2 (Stochastic block model limit for fixed induced subgraphs). Fix an integer r ≥ 3, set q = r − 1, and let w > 0 and m ∈ N. For every n ≥ m, let Gn ∼ Pn,r , and let Hn,m be the subgraph of Gn induced by [m]. (q) Define a random graph Sm on [m] as follows. Choose C1 , . . . , Cm independently and uniformly from [q]. Given these labels, include the possible edges independently, with probability (
0, Ci = Cj , (q) PSBM {i, j} ∈ E(Sm ) | C1 , . . . , Cm = 1 1 ≤ i < j ≤ m. 2 , Ci ̸= Cj , (q)

(p)

Here PSBM (Sm ) denotes probability of getting Sm under this construction. Define prob(q) ability measures νn,m and νm on Gm by (q) νm (J) := PSBM (S(q) m = J)

νn,m (J) := P(Hn,m = J),

for J ∈ Gm .

Then
(q) lim dTV νn,m , νm = 0.

n→∞

(q) The limiting measure νm depends on q = r − 1 but not on w.

Proof. Fix J ∈ Gm . For the induced density from Definition 6.1, inclusion-exclusion gives [22, Sec. 7.2, Eq. (7.4)] X tind (J, W ) = (−1)|E(F )\E(J)| t(F, W ). F ∈Gm E(J)⊆E(F )

By [7, Thm. 3.7(a)], each homomorphism density in this sum is continuous in cut distance. Therefore tind (J, ·) is also continuous in cut distance. Theorem 2.7(ii) and the final identity in Notation 4.3 give, for every ε > 0,
lim P tind (J, WGn ) − tind (J, Wq⋆ ) ≥ ε = 0. n→∞

Since the absolute difference is bounded by 1, for every ε > 0, its expectation is at most ε plus the probability that it is at least ε. Hence,   (6.1) lim E tind (J, WGn ) − tind (J, Wq⋆ ) = 0. n→∞

Define a probability measure ν̄n,m on Gm by   ν̄n,m (J) := E tind (J, WGn ) . By (2.3), the probability assigned to a graph G depends only on Kr (G), which is invariant under vertex relabeling. Hence the distribution of Gn is invariant under vertex relabeling. Consequently, if ι : [m] → [n] is an independent uniformly chosen injection, then Hn,m has the same distribution as the graph on [m] in which {i, j} is an edge exactly when {ι(i), ι(j)} ∈ E(Gn ). On the other hand, sampling from WG corresponds to choosing vertices of G independently, so the same vertex may be chosen more
than once. The probability of choosing m the same vertex more than once is at most 2 /n. Therefore, by [22, Eq. (10.1)],
m dTV (νn,m , ν̄n,m ) ≤

2

n

. (q)

By Notation 4.3, graphon sampling from Wq⋆ is exactly the construction of Sm , therefore (q) tind (J, Wq⋆ ) = νm (J).

52

YASMIN TOUSINEJAD AND VERA KOPONEN

It follows that (q) dTV νn,m , νm

≤ ≤

m 2

n

m 2

(q) + dTV ν̄n,m , νm

+

n

 1 X  E tind (J, WGn ) − tind (J, Wq⋆ ) . 2 J∈Gm

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 ≥ 2 and m ≥ 2, and consider (q) the model Sm defined above. For 1 ≤ i < j ≤ m, let Xij := 1{{i,j}∈E(S(q) )} . m

For each edge, PSBM (Xij = 1) = PSBM (Ci ̸= Cj )

1 q−1 1 q−1 = · = . 2 q 2 2q

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} and {i, k}, then     q−1 2 1 q−1 2 PSBM (Xij = Xik = 1) = = , q 4 2q which is the product of their individual probabilities. However, if m ≥ 3, the three indicators associated with the triangle on {1, 2, 3} are not independent as a triple, since PSBM (X12 = X13 = X23 = 1) =

(q − 1)(q − 2) , 8q 2

whereas independence would give 

q−1 2q

3 .

Indeed,  q−1 q − 1 3 (q − 1)(q − 2) − = > 0. 2 2q 8q 8q 3 Thus any two edge indicators are independent, but the three triangle indicators are not (q) independent as a triple. In particular, Sm is not an Erdős-Rényi graph when m ≥ 3. 

6.4. Limiting clique densities. For any fixed integer r ≥ 3 we now determine the limiting density, with respect to Pn,r , of Ks for all s ≥ 2. Corollary 6.4. Fix an integer r ≥ 3 and let w > 0. Let Gn ∼ Pn,r , and set q = r − 1. For every fixed integer s ≥ 2,    q(q − 1) · · · (q − s + 1) , 2 ≤ s ≤ q, s ⋆ (6.2) t(Ks , Wq ) = q s 2(2)  0, s > q. Moreover, for every η > 0, there are constants c = c(η, r, s) > 0 and N = N (η, r, s, w) ≥ s such that, for every n ≥ N ,   s! Ks (G) 2 ⋆ (6.3) Pn,r G ∈ Gn : − t(Ks , Wq ) ≥ η ≤ e−cn . s n

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

53

Consequently, for every η > 0, (6.4)

lim P

n→∞

Ks (Gn )
− t(Ks , Wq⋆ ) ≥ η n

! = 0.

s

Thus every fixed clique Ks with 2 ≤ s ≤ r − 1 has a positive limiting density, while every fixed clique Ks with s ≥ r has limiting density zero. Proof. Suppose first that 2 ≤ s ≤ q. By Definition 3.3, Z Y Wq⋆ (xi , xj ) dx1 · · · dxs . t(Ks , Wq⋆ ) = [0,1]s 1≤i<j≤s

Equivalently, choose x1 , . . . , xs independently and uniformly at random from [0, 1]. By Notation 4.3, the index of the canonical block containing each xi is uniform on [q], and these block indices are independent. Since Wq⋆ is zero within each block, the integrand is nonzero only when x1 , . . . , xs lie in distinct blocks. The set of such points has measure q(q − 1) · · · (q − s + 1) . qs On this set, every factor in the integrand is equal to 1/2. Since Ks has follows that q(q − 1) · · · (q − s + 1) t(Ks , Wq⋆ ) = . s q s 2(2)

s 2

edges, it

If s > q, then among any s points x1 , . . . , xs , at least two lie in the same canonical block. The corresponding factor in the defining integral is zero. Hence t(Ks , Wq⋆ ) = 0. This proves (6.2). By Lemma 3.18, with s in place of r, every graph G ∈ Gn satisfies t(Ks , WG ) =

s! Ks (G) . ns

Lemma 3.14 and Notation 4.3 therefore give s! Ks (G) − t(Ks , Wq⋆ ) ≤ ns

  s δ□ (WG , Bq⋆ ). 2

Thus, if the left-hand side is at least η, then δ□ (WG , Bq⋆ ) ≥

η
s . 2

Applying Theorem 2.7(ii) with η/ 2s

in place of ε proves (6.3).

Finally, for n ≥ s, set Xn :=

s! Ks (Gn ) , ns

an :=

n(n − 1) · · · (n − s + 1) . ns

Then X Ks (Gn )
= n. n an s Equation (6.3) says that Xn converges in probability to t(Ks , Wq⋆ ). Since an > 0 and lim an = 1,

n→∞

the quotient Xn /an converges in probability to the same limit. This is exactly (6.4). □

54

YASMIN TOUSINEJAD AND VERA KOPONEN

Example 6.5. For example, let r = 4, so that q = 3, and let Gn ∼ Pn,4 . Then t(K3 , W3⋆ ) =

3·2·1 1 = , 33 23 36

t(K4 , W3⋆ ) = 0.

Hence, for every η > 0, lim P

n→∞

1 K3 (Gn )
− ≥η n 36 3

! = 0,

lim P

n→∞

K4 (Gn )
≥η n

! = 0.

4

Thus a positive proportion of triples still form triangles, even though the proportion of four-element sets that form a copy of K4 tends to zero. 6.5. Colorability with fewer than r − 1 colors. Corollary 6.6. Fix an integer r ≥ 3 and let w > 0. Set q = r − 1, and let Gn ∼ Pn,r . Recall that χ(Gn ) denotes the chromatic number of Gn . For every n ∈ N and every integer k with 1 ≤ k < q,  
(q − k) ln 2 2 q ln 2 n + n ln k + . (6.5) P χ(Gn ) ≤ k ≤ exp − 2kq 8 Consequently, there are constants c = c(r, k) > 0 and N = N (r, k) ∈ N such that
2 P χ(Gn ) ≤ k ≤ e−cn for every n ≥ N. In particular, when r ≥ 4, the probability that Gn is (r − 2)-partite tends to zero exponentially in n2 . Proof. Fix a map from [n] to a set of k colors, and let m1 , . . . , mk 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 !   k X 1 1 1 2 2 1− n2 , n − mi ≤ 2 2 k i=1

where the inequality follows from Lemma 3.12(ii). Hence at most 2

2(1−1/k)n /2 graphs have this fixed proper coloring. Since there are k n such maps, (6.6)

2

{G ∈ Gn : χ(G) ≤ k} ≤ k n 2(1−1/k)n /2 .

A k-colorable graph has no clique with more than k vertices. Since k < q < r, every graph counted in (6.6) is Kr -free and has reduced mass 1. Hence (6.6) and (5.17) give    
ln 2 1 q ln 2 2 2 P χ(Gn ) ≤ k ≤ exp 1− n + n ln k − sq n + . 2 k 8 Using (5.1) gives (6.5). Since q − k > 0, the coefficient of n2 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. For each k ∈ {3, . . . , ℓ} let a weight wk ≥ 0 be fixed. Assume that at least one of these wk is positive and set r := min{k ∈ {3, . . . , ℓ} : wk > 0},

q := r − 1.

Thus wk = 0 for k < r. For all k ∈ {3, . . . , ℓ} and every G ∈ Gn , define Nk (G) := nk − k! Kk (G).

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

55

Hence Nk (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 ∈ Gn as the number ! ! ! ℓ ℓ ℓ X X X exp wk Nk (G) = exp wk nk exp − k! wk Kk (G) . k=3

k=r

k=r

The first factor is independent of G and cancels after normalization. We therefore define the “reduced mass” of G ∈ Gn by ! ℓ X Mnmc (G) := exp − k! wk Kk (G) , k=r

and then the corresponding reduced partition function, probability measure, and reduced free energy are defined by X Mnmc (G), Zenmc := G∈Gn

(6.7)

Pmc n (A) :=

1 X mc Mn (G), Zenmc

for A ⊆ Gn ,

and

G∈A

1 ln Zenmc . n2 Theorem 6.7 (The smallest positively weighted clique determines the limit structure). mc Let Gmc n ∼ Pn , that is, Gn is a random graph from Gn under the probability distribution Pmc n . Then the following statements hold:   1 . (i) limn→∞ Fnmc = ln22 1 − r−1 (ii) For every ε > 0, there are constants Fnmc :=

c = c(ε, r) > 0

and

N = N (ε, r, wr )

such that, for every n ≥ N ,

2 P δ□ WGmc , Bq⋆ ≥ ε ≤ e−cn . n (iii) For every ε > 0, there are constants c = c(ε, r) > 0

and

N = N (ε, r, wr ) 2

such that, for every n ≥ N , with probability at least 1 − e−cn , there is a partition [n] = V1 ⊔ · · · ⊔ Vq with the following properties: (a) For every i ∈ [q], |Vi | − n/q ≤ εn. (b) For all distinct i, j ∈ [q], eGmc (Vi , Vj ) 1 n − ≤ ε. |Vi ||Vj | 2 (c) The total number of edges inside parts is q X

eGmc (Vi ) ≤ n

i=1

εn2 . 10q

(d) The total density of edges inside the parts is at most ε: Pq (Vi ) i=1 eGmc n
≤ ε. Pq |V | i

i=1

2

56

YASMIN TOUSINEJAD AND VERA KOPONEN

If G′n is obtained by deleting all edges whose endpoints lie in the same part, then G′n is q-partite and
ε ε ′ dedit Gmc ≤ . n , Gn ≤ 10q 2 In particular, the reduced free-energy limit and the cut-distance limit depend on the weight vector (w3 , . . . , wℓ ) only through r. Once r and wr are fixed, the constants in parts (ii) and (iii) can be chosen independently of ℓ and of the weights wr+1 , . . . , wℓ . en,r , Fn,r (wr ), and Pn,r denote the reduced partition function, reduced free Proof. Let Z energy, and probability measure of the single-Kr model with weight wr , and set q ln 2 . 8 Since the higher weights are nonnegative, every G ∈ Gn satisfies
(6.8) 0 < Mnmc (G) ≤ exp −r! wr Kr (G) ≤ 1. Cq :=

Every graph in the balanced q-partite family used in the proof of Lemma 5.11 is Kr -free and hence Kk -free for every k ≥ r. Its multi-clique reduced mass is therefore 1. Let   1 ln 2 1− . sq := 2 q The same lower-bound construction, together with (6.8), gives
en,r . (6.9) exp sq n2 − Cq ≤ Zenmc ≤ Z 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 Kr penalty. For part (i), taking logarithms in (6.9) and dividing by n2 gives Cq ≤ Fnmc ≤ Fn,r (wr ). n2 The conclusion follows from Theorem 2.7(i). For parts (ii) and (iii), set Zen,r . Rn := Zenmc By (6.8), every event A ⊆ Gn satisfies sq −

Pmc n (A) ≤ Rn Pn,r (A).

(6.10) Moreover, (6.9) implies 0≤

Cq 1 ln Rn ≤ Fn,r (wr ) − sq + 2 , 2 n n

and hence, by Theorem 2.7(i), (6.11)

lim

1

n→∞ n2

ln Rn = 0.

The upper bound depends only on n, r, and wr , and it tends to 0. Since the same bound holds simultaneously for every ℓ ≥ r and every choice of wr+1 , . . . , wℓ ≥ 0, the convergence is uniform in those parameters. Consequently, suppose that a sequence of events (An ) satisfies 2

Pn,r (An ) ≤ e−an

EXPONENTIAL RANDOM GRAPH MODELS WITH SOFT CLIQUE CONSTRAINTS

57

for some a > 0 and all sufficiently large n. After increasing the threshold if necessary, 2 (6.11) gives Rn ≤ ean /2 , and (6.10) gives 2

−an /2 Pmc . n (An ) ≤ e

For part (ii), apply this observation to  An = G ∈ Gn : δ□ (WG , Bq⋆ ) ≥ ε and use Theorem 2.7(ii). For part (iii), let Bn,ε be the set of graphs that admit no partition satisfying the five properties stated there. Theorem 2.7(iii) gives an exponential bound for Pn,r (Bn,ε ), so the same observation gives the required bound under Pmc n . The edit-distance conclusion follows from any partition satisfying those five properties, exactly as in Theorem 2.7(iii). For each of parts (ii) and (iii), one may choose c = c(ε, r) > 0 and N = N (ε, r, wr ). Neither choice depends on ℓ or on the higher weights wr+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+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 Kn -free graphs, in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, 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ℓ+1 -free graphs: asymptotic structure and a 0–1 law, Trans. Amer. Math. Soc. 303 (1987), no. 2, 637–671, DOI: 10.1090/S0002-9947-19870902790-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.

58

YASMIN TOUSINEJAD AND VERA KOPONEN

[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∗ ) 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). Department of Mathematics, Uppsala University, Sweden. Email address: yasmin.tousinejad@math.uu.se Department of Mathematics, Uppsala University, Sweden. Email address: vera.koponen@math.uu.se

Related documents

• RamseyGadgets: A Graph Construction Dataset for LLMs#612434
• RamseyGadgets: A Graph Construction Dataset for LLMs#610957
• One Pass for All: A Discrete Diffusion Model for Knowledge Graph Triple Set Prediction#120562
• The transition probabilities on wheel graphs: An application of evolutionary games on graphs#298193
• Codegree Thresholds for $λ$-Choosability of Graphs#625299