证明
Lemma 2. Let r≥2 be an integer, let G be a finite K_r -free graph with positive…Lemma 1. For every nonempty finite simple graph G , the function F_G attains…观点
First suppose S∩D=∅ , and put s=w(S) and t=w(D) . The case s=0 is immediate. Initially assume e^ -x ≤s≤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 2 to G[S] with ε=e^ -8x , and set k=e^ 4x . Define a nonnegative random vector by q_v= (1+km_v)w_v,, v∈S,; 0,, v∈D,; w_v,, v∉S∪D. The expected quadratic term in is at most 𝔼 M_G(q-w) ≤k^2εs^2+12t^2-k e_w(S,D). Here the last term uses 𝔼 m_v=1 ; no independence between the multipliers is required. The choice k^2ε=1 keeps the first term controlled despite the increase in the weights on S . For y≥0 , (1+y)(1+y)-y≤y(1+y) . Also (1+kb_r(e^ -8x ))≤A_rx, A_r=4+8(r-2)+(1+r(r-2))2. It follows that the expected sum of vertex terms in is at most t+kA_rxs . Combining this with and dividing by k gives e_w(S,D) , ≤A_rxs+e^ -4x s^2+e^ -4x (t+t^2/2); , ≤(A_r+3)xs. For the last inequality, use s,t≤e^x and s≥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'=(1/s)>x . Both set weights are at most e^ x' and s=e^ -x' , so e_w(S,D)≤(A_r+3)x's≤(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 𝔼 e_w(S',D')=14e_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 14e_w(S,D) ≤(A_r+3)𝔼 g_x(w(S')) ≤(A_r+3)g_x(s). Finally, A_r+3≤r^2+6r-8≤4r^2 for r≥2 , which proves .