Proof. The continuous function \(f(t)=t(1-\log t)\) on \([0,\infty)\) is at most \(1\) and tends to \(-\infty\) as \(t\to\infty\). Since \(M_G(w)\ge0\) for \(w\ge0\), \[F_G(w)\le f(\|w\|_\infty)+|V(G)|-1.\] Consequently \(F_G(w)\to-\infty\) as \(\|w\|_\infty\to\infty\), so continuity gives a maximum. If a maximizer had \(w_v=0\), changing just this coordinate to \(t>0\) would increase \(F_G\) by \[t\bigl(1-\log t-w(N_G(v))\bigr)>0\] for sufficiently small \(t\). All coordinates are therefore positive, and the first derivative in each coordinate gives (1). To obtain (2), expand the quadratic expression \(M_G(q)\) around \(w\). Its linear term is \(\sum_v(q_v-w_v)w(N_G(v))\), which cancels the corresponding term using (1). The inequality follows from maximality. ◻

Proof. The empty graph on no vertices is immediate. We induct on \(r\), starting with \(r=2\), when there are no edges and \(m_v=1\) suffices. Suppose \(r\ge3\) and set \(\eta=\varepsilon/4\).

Starting with all vertices, repeatedly choose a vertex whose open neighborhood in the remaining induced graph has weight greater than \(\eta s\), and remove that neighborhood as a set \(V_i\). These disjoint sets have weights \(s_i=w(V_i)>\eta s\), and each \(G[V_i]\) is \(K_{r-1}\)-free. Indeed, a \((r-1)\)-clique in such a neighborhood together with its chosen vertex would form a \(K_r\). When the procedure stops, the remaining set \(R\) satisfies \[ M_{G[R]}(w) =\frac12\sum_{v\in R}w_vw(N_G(v)\cap R) \le\frac12\eta s\,w(R)\le\frac12\eta s^2. \tag{4}\]

If no sets \(V_i\) were removed, take every \(m_v=1\). Otherwise put \(b=\sum_i s_i>0\) and \(p_i=s_i/(2b)\). Choose \(R\) with probability \(1/2\) and \(V_i\) with probability \(p_i\), putting all multipliers outside the chosen set equal to zero. On choosing \(R\), set \(m_v=2\) for \(v\in R\). On choosing \(V_i\), use the induction hypothesis there with precision \(\varepsilon/4\), and multiply its output by \(1/p_i\). The option of choosing \(R\) is retained even if \(R\) is empty; in that event all multipliers are zero.

Every vertex has mean multiplier one. Since \(p_i>\eta/2=\varepsilon/8\), each multiplier is at most \[\max\left\{2,\frac8\varepsilon b_{r-1}(\varepsilon/4)\right\} = b_r(\varepsilon).\] The equality follows directly from the displayed formula for \(b_r\). Only edges within the chosen set contribute. Therefore \[\begin{align*} \mathbb E M_G((w_vm_v)_v) &\le 2M_{G[R]}(w) +\sum_i\frac{\varepsilon s_i^2}{4p_i}\\ &\le \eta s^2+\frac{\varepsilon}{2}b^2 \le\frac34\varepsilon s^2. \end{align*}\] The finite construction and the induction hypothesis also give finite support for the joint law. ◻

Proof. First suppose \(S\cap D=\varnothing\), and put \(s=w(S)\) and \(t=w(D)\). The case \(s=0\) is immediate. Initially assume \(e^{-x}\le s\le e^x\). We will increase the weights on \(S\) and set those on \(D\) to zero. In the variational identity, this creates a negative quadratic term proportional to \(e_w(S,D)\). The random multipliers keep the positive quadratic term within \(S\) small, while their bounded range controls the vertex terms through a logarithm. Apply Lemma 3 to \(G[S]\) with \(\varepsilon=e^{-8x}\), and set \(k=e^{4x}\). Define a nonnegative random vector by \[q_v= \begin{cases} (1+km_v)w_v,&v\in S,\\ 0,&v\in D,\\ w_v,&v\notin S\cup D. \end{cases}\] The expected quadratic term in (2) is at most \[ \mathbb E M_G(q-w) \le k^2\varepsilon s^2+\frac12t^2-k e_w(S,D). \tag{6}\] Here the last term uses \(\mathbb E m_v=1\); no independence between the multipliers is required. The choice \(k^2\varepsilon=1\) keeps the first term controlled despite the increase in the weights on \(S\).

For \(y\ge0\), \((1+y)\log(1+y)-y\le y\log(1+y)\). Also \[\log(1+kb_r(e^{-8x}))\le A_rx, \qquad A_r=4+8(r-2)+(1+r(r-2))\log2.\] It follows that the expected sum of vertex terms in (2) is at most \(t+kA_rxs\). Combining this with (6) and dividing by \(k\) gives \[\begin{align*} e_w(S,D) &\le A_rxs+e^{-4x}s^2+e^{-4x}(t+t^2/2)\\ &\le (A_r+3)xs. \end{align*}\] For the last inequality, use \(s,t\le e^x\) and \(s\ge e^{-x}\): the three error terms divided by \(s\) are at most \(e^{-3x}\), \(e^{-2x}\), and \(e^{-x}/2\), respectively, and their sum is at most \(3x\).

If instead \(0<s<e^{-x}\), apply the estimate just proved with \(x'=\log(1/s)>x\). Both set weights are at most \(e^{x'}\) and \(s=e^{-x'}\), so \[e_w(S,D)\le(A_r+3)x's\le(A_r+3)g_x(s).\] Thus the bound with constant \(A_r+3\) holds for all disjoint sets.

For arbitrary \(S,D\), assign each vertex independently to one of two classes with equal probabilities. Let \(S'\) be the part of \(S\) in the first class and \(D'\) the part of \(D\) in the second. These sets are disjoint, their weights satisfy the same upper bounds, and \[\mathbb E e_w(S',D')=\frac14e_w(S,D).\] There are no loops, so each directed edge in this expectation has two distinct endpoints. The disjoint-set bound and monotonicity give \[\frac14e_w(S,D) \le (A_r+3)\mathbb E g_x(w(S')) \le (A_r+3)g_x(s).\] Finally, \(A_r+3\le r^2+6r-8\le4r^2\) for \(r\ge2\), which proves (5). ◻

Proof. For \(A,B\subseteq V(H)\), write \(A_0=\pi(A)\) and \(B_0=\pi(B)\). Duplicating vertices can increase their total weight, so \[w(A_0)\le\widetilde w(A),\qquad w(B_0)\le\widetilde w(B).\] The directed edges counted by \(e_{H,\widetilde w}(A,B)\) map injectively to directed edges counted by \(e_{G,w}(A_0,B_0)\), with their weights unchanged. Consequently, if \(\widetilde w(A),\widetilde w(B)\le e^x\), then \[e_{H,\widetilde w}(A,B) \le e_{G,w}(A_0,B_0) \le Cg_x(w(A_0)) \le Cg_x(\widetilde w(A)).\] This also covers overlapping sets and the case of an empty set.

The directed-edge condition implies injectivity on unordered edges: two edges with the same unordered image could be oriented to have the same directed image. It therefore gives the assertion about \(M\). For a fixed \(a\), two different neighbors \(b,b'\) cannot have the same image, since the directed edges \((a,b)\) and \((a,b')\) would then have the same image. Thus \(\pi\) maps \(N_H(a)\) injectively into \(N_G(\pi(a))\), giving the neighborhood bound.

Every triangle of \(H\) maps to a triangle of \(G\), since a homomorphism to a simple graph is injective on the vertices of a clique. Distinct triangles cannot have the same image: each of the three image edges has at most one preimage edge, and those three preimage edges determine the triangle. Triangle weights are unchanged, proving the assertion about \(T\). Finally, compositions preserve vertex weights, adjacency and injectivity on directed edges. ◻

Proof. Each triangle contributes its weight once for each of its three edges to the first sum in (8), and once for each of its six oriented edges to the second. Since \(c_{uv}\le L\), the first identity also proves (9).

Starting with \(G\), delete any edge whose common-neighbor weight in the current graph is less than \(\tau\), and continue until no such edge remains. The procedure terminates because \(G\) is finite. If \(\{u_i,v_i\}\) is the \(i\)th deleted edge and \(c_i\) its common-neighbor weight immediately before deletion, the triangle weight lost at that step is exactly \(w_{u_i}w_{v_i}c_i\). Telescoping gives \[T_G(w)-T_{G'}(w) =\sum_iw_{u_i}w_{v_i}c_i \le\tau\sum_iw_{u_i}w_{v_i} \le\tau M_G(w).\] This counts each destroyed triangle at its first deleted edge. The defining stopping rule gives \(c_{uv}\ge\tau\) on every remaining edge. If \(u\) is nonisolated, choose a remaining neighbor \(v\) to obtain \(s_u\ge c_{uv}\ge\tau\); summing \(w_vc_{uv}\ge\tau w_v\) over the remaining neighbors gives \(h_u\ge\tau s_u\). The last assertion follows from Lemma 6. ◻

Proof. Write \(m=|J|\). Take independent trials \((Z_t,U_t)_{t\ge1}\), with \(Z_t\) uniform on \(J\) and \(U_t\) uniform on \([0,1]\). For each \(i\), let \(Y_i=Z_t\) at the first trial satisfying \(U_t\le p_i(Z_t)\). A trial is accepted by row \(i\) with probability \(1/m\), and its accepted value has law \(p_i\). More explicitly, for \(y\in J\), \[\mathbb P(Y_i=y) =\sum_{t\ge1}(1-1/m)^{t-1}\frac{p_i(y)}m=p_i(y).\] Every row stops almost surely; since \(I\) is finite, all rows stop after a finite number of trials almost surely.

Fix two rows \(p,q\), and put \(d=\|p-q\|_{\mathrm{TV}}\). At the first trial accepted by either row, the probability that both accept is \[\frac{\sum_{y\in J}\min(p(y),q(y))} {\sum_{y\in J}\max(p(y),q(y))} =\frac{1-d}{1+d}.\] On this event their labels agree. They may also agree otherwise, so the disagreement probability is at most \(2d/(1+d)\). Finally, the label vector takes values in the finite set \(J^I\), so its induced law has finite support. The infinite sequence of trials is only a convenient construction of that finite joint law. ◻

Proof. Under the joint law \((u,v)\sim\mu\), \(y\sim K_u(v,\cdot)\), reversibility gives \[(u,v,y)\ \stackrel{\mathrm{law}}=\ (u,y,v).\] Both \(K_u(v,y)\) and \(K_u(y,v)\) are positive on this law’s support: all \(\pi_u\) are positive and \(\pi_u(v)K_u(v,y)=\pi_u(y)K_u(y,v)\). Consequently \[\ell:=\log\frac{w_v}{K_u(y,v)} \quad\text{satisfies}\quad \mathbb E\ell=H_j\le A_C\log x.\] The density bound applied to the reversed row gives \(\ell\ge-\log x\). Inadmissibility is precisely the event \(\ell>\sqrt x\). Applying Markov’s inequality to the nonnegative random variable \(\ell+\log x\) proves (24). No bound on an individual row’s entropy is needed here. ◻

Proof. Every old edge creates at most one new edge. The projection therefore maps directed edges injectively, and the new graph has neither loops nor multiple edges. At a fixed vertex \((u,y)\), different neighbors project to different vertices of \(H\), because \(H\) is simple and each edge \(uv\) was used at most once. By (23), \[w(N_{H'}(u,y)) \le w(A_{u,y}) \le e^{\sqrt x}.\] In particular, duplicating a vertex does not duplicate any of its incident edges at one fixed copy.

An old triangle \(\{u,v,z\}\) survives whenever its two labels agree at each corner and all six incidence labels are admissible. These conditions are also necessary for its three edges to form a triangle in \(H'\). A triangle of \(H'\) projects to three distinct old vertices, and hence to an old triangle. Moreover, there is at most one triangle over each old triangle, since each old edge has at most one preimage. The weights of a surviving triangle are unchanged.

Sample an ordered triangle \((u,v,z)\) with probability \(w_uw_vw_z/(6T_H(w))\). Its ordered-edge marginal is \(\mu\). At the corner \(u\), the shared coupling and the row-distance estimate give \[\mathbb E\,\mathbb P(Y_{u,v}\ne Y_{u,z}) \le 2B_C\sqrt{\frac{\log x}{x}}.\] Each of the other two corners has the same bound, by the permutation symmetry of the ordered-triangle law. Each of its six directed incidences has marginal \(\mu\), so Lemma 10 bounds the average inadmissibility probability of each by \(\delta_x\). A union bound, with no independence assumption between these events, therefore gives \[\frac{\mathbb E(T_H(w)-T_{H'}(w))}{T_H(w)} \le6B_C\sqrt{\frac{\log x}{x}}+6\delta_x \le a_C\frac{\log x}{\sqrt x}.\] The last inequality uses \(\log x\ge1\). All label vectors together have finite support. At least one of them has triangle mass at least its expectation, proving the claim. ◻

Proof. Peel edges whose current common-neighbor weight is less than \(1/x\). If \(H\) is the remaining graph, Lemma 7 gives \[T_H(w)\ge T_G(w)-M_G(w)/x.\] Edge deletion does not increase any weighted neighborhood, and it preserves the cross-mass condition. If \(H\) has no edges, take \(G'\) to be empty. Then \(T_G(w)\le M_G(w)/x\), which implies (29). Otherwise, apply Lemma 11 to \(H\). Since \(x\mapsto\log x/\sqrt x\) is decreasing for \(x\ge e^2\), (27) ensures \(0\le1-a_C\log x/\sqrt x\le1\). Hence \[\begin{align*} T_{G'}(w) &\ge\left(1-a_C\frac{\log x}{\sqrt x}\right) \left(T_G(w)-\frac{M_G(w)}x\right)\\ &\ge\left(1-a_C\frac{\log x}{\sqrt x}\right)T_G(w) -\frac{M_G(w)}x. \end{align*}\] The projection through \(H\) is still injective on directed edges. The edge-mass bound and inherited cross-mass condition follow from Lemma 6. ◻

Proof of Theorem 5. If \(G\) has no edges, both sides vanish. Otherwise choose \(x_0\ge1\) such that every neighborhood has weight at most \(e^{x_0}\). While \(x_i>X\), apply Proposition 12 and set \(x_{i+1}=\sqrt{x_i}\). Write \(G_i\) for the successive graphs, \(T_i=T_{G_i}(w)\) and \(M_i=M_{G_i}(w)\); the weights at each stage are the inherited weights of its vertex copies. Stop after \(k\) steps, when \(x_k\le X\). The procedure is finite, and the \(k=0\) case is allowed.

We record bounds independent of \(x_0\) and \(k\). If \(k>0\), put \(y=x_{k-1}>X\). The used parameters, in reverse order, are \(y,y^2,y^4,\ldots,y^{2^{k-1}}\). For \(f(t)=\log t/\sqrt t\) and \(t\ge X\ge32\), \[\frac{f(t^2)}{f(t)}=\frac2{\sqrt t}\le\frac12.\] As \(f\) is decreasing on \([X,\infty)\), it follows that \[ \sum_{i<k}a_Cf(x_i)\le2a_Cf(X)\le\frac12, \qquad \sum_{i<k}\frac1{x_i}\le\frac{1/X}{1-1/X}\le1. \tag{30}\] Both inequalities also hold for empty sums when \(k=0\).

Let \(\varepsilon_i=a_Cf(x_i)\). Iterating (29), using \(M_i\le M_0\) and \(0\le1-\varepsilon_i\le1\), gives \[T_k\ge\left(\prod_{i<k}(1-\varepsilon_i)\right)T_0 -M_0\sum_{i<k}\frac1{x_i} \ge\frac12T_0-M_0.\] Here \(\prod(1-\varepsilon_i)\ge1-\sum\varepsilon_i\). Every neighborhood of \(G_k\) has weight at most \(e^X\), so \[3T_k =\sum_{\{u,v\}\in E(G_k)}w_uw_vw(N_{G_k}(u)\cap N_{G_k}(v)) \le e^X M_k\le e^X M_0.\] Combining the last two displays proves the theorem with \(C_\triangle(C)=2(1+e^{X(C)}/3)\). All thresholds and constants depend only on \(C\); neither the number of vertices nor the initial neighborhood bound enters them. ◻