794dc57 f0945ea
====================================================================
AN INDEPENDENCE BOUND OF ORDER (n log d)/d FOR GRAPHS THAT CONTAIN NO K_r
A complete, self-contained proof, written to be readable.
====================================================================
Notation used throughout, all in one place:
G a finite simple graph (no loops, no multiple edges).
V(G) its vertex set; n = |V(G)| is the number of vertices.
E(G) its edge set.
N(v) the set of neighbors of vertex v.
K_r the complete graph on r vertices.
K_r-free no r vertices of G are pairwise adjacent.
alpha(G) the independence number: the largest size of a set of
vertices with no two of them adjacent.
d the average degree, d = 2 |E(G)| / n.
log the natural logarithm. Also 0 log 0 = 0 by convention.
The main result:
THEOREM (main).
For every integer r >= 4 there is a positive constant c_r, depending
only on r, such that every finite simple K_r-free graph G on n >= 1
vertices with average degree d >= 2 satisfies
alpha(G) >= c_r * (n log d) / d.
Two facts put this in context. First, for general graphs the elementary
bound alpha(G) >= n/(d+1) cannot be improved, because a disjoint union of
cliques attains it. So excluding a clique must buy something extra; the
theorem says it buys a factor of order log d. Second, the order log d is
best possible up to the constant: there are triangle-free graphs (hence
K_r-free) of average degree d whose largest independent set is only
O(n log d / d). We do not try to make c_r large; we only show some c_r > 0
exists. The proof is an existence proof and says nothing about how to find
the independent set quickly.
--------------------------------------------------------------------
0. HOW THE PROOF IS ORGANIZED, AND WHY EACH PIECE IS THERE
--------------------------------------------------------------------
The engine of the proof is a single inequality about "triangle mass" being
controlled by "edge mass" once a good set of vertex weights is chosen.
The plan has three stages.
STAGE A (Section 1 and 2). Attach a positive weight w_v to each vertex
and look at the functional
F_G(w) = sum_v w_v (1 - log w_v) - (sum over edges {u,v} of w_u w_v).
Pick a weight vector w that maximizes F_G. A small variational argument
(the "random multiplier" lemma) then shows that the mass of edges crossing
from any vertex set S to any vertex set D cannot be much larger than the
weight of S, times a factor that grows only like log(weight). This is the
"cross-mass bound". Crucially it uses only that G is K_r-free.
STAGE B (Sections 3 to 6). We prove a clean structural statement: ANY
weighted graph obeying the cross-mass bound with some constant C has its
triangle mass bounded by a constant (depending only on C) times its edge
mass. The proof works no matter how uneven the weights are and no matter
how many vertices there are. The trick is to reduce the size of "weighted
neighborhoods" by splitting vertices into copies, losing only a little
triangle mass at each step, and to repeat until neighborhoods are tiny;
once neighborhoods are tiny, triangle mass is directly comparable to edge
mass. The delicate step is choosing, for each vertex, how to group its
incident edges into copies so that neighborhoods shrink and most triangles
survive. That choice is made by running short random walks inside
neighborhoods and coupling their outcomes.
STAGE C (Section 7). With the triangle bound in hand, we run an induction
on the vertex set: at each step delete the closed neighborhood of a
carefully chosen vertex, losing only O(log Delta) of the functional, where
Delta is the maximum degree. This produces a large independent set in
terms of maximum degree; deleting the minority of high-degree vertices
converts it to a bound in terms of average degree.
We now carry this out completely. Every lemma is proved.
--------------------------------------------------------------------
1. VERTEX WEIGHTS AND THE EXTREMAL FUNCTIONAL
--------------------------------------------------------------------
Let G be a finite simple graph. For a real vector a = (a_v) indexed by the
vertices, define the quadratic edge form
M_G(a) = sum over edges {u,v} of a_u a_v.
This is defined even when some a_v are negative (we will use that). For a
nonnegative weight vector w and a vertex set S, write w(S) = sum_{v in S} w_v.
For two vertex sets S and D define the directed cross mass
e_w(S,D) = sum over ordered pairs (u,v) with u in S, v in D and v a
neighbor of u, of w_u w_v.
So e_w(S,D) counts each edge between S and D once if S and D are disjoint,
and counts an edge twice if both its ends lie in S and in D. Note there
are no loops, so u and v are always distinct.
Define the functional
F_G(w) = sum_v w_v (1 - log w_v) - M_G(w),
and let F_G^* be its maximum over all w >= 0.
LEMMA 1.1 (the maximum is attained, and is stationary).
For every nonempty finite simple graph G:
(a) F_G attains a maximum over w >= 0;
(b) every maximizer w has all coordinates positive and satisfies, for
every vertex v,
log(1/w_v) = w(N(v)); (*)
in particular 0 < w_v <= 1;
(c) for every nonnegative vector q,
0 <= F_G(w) - F_G(q)
= sum_v ( q_v log(q_v/w_v) - q_v + w_v ) + M_G(q - w),
where a summand with q_v = 0 equals w_v.
PROOF. The function f(t) = t(1 - log t) is continuous on [0,infinity),
bounded above by 1, and tends to -infinity as t tends to infinity. For any
w >= 0, M_G(w) >= 0, so
F_G(w) <= f(m) + (n - 1), where m = max_v w_v,
because at most one coordinate equals m and the other coordinates each
contribute at most 1. Hence F_G(w) tends to -infinity as m tends to
infinity, and since F_G is continuous, a maximum exists on the compact
sublevel set where F_G is at least its value at, say, the all-ones vector.
This proves (a).
For (b), suppose a maximizer w had w_v = 0 for some v. Increase just this
coordinate from 0 to a small t > 0. The sum term sum_u f(w_u) changes by
f(t) - f(0) = t(1 - log t). The edge term M_G(w) changes by + t w(N(v)),
because each edge from v to a neighbor u now contributes t w_u. So F_G
changes by
t (1 - log t) - t w(N(v)) = t (1 - log t - w(N(v))),
which is positive for all sufficiently small t > 0 (as t -> 0, log t ->
-infinity). That contradicts maximality. Hence all w_v > 0.
Now w is an interior maximizer, so each partial derivative vanishes. The
derivative of f is f'(t) = 1 - log t - 1 = -log t, and the derivative of
M_G in w_v is w(N(v)). So -log w_v - w(N(v)) = 0, which is (*). Since
w(N(v)) >= 0, (*) gives log(1/w_v) >= 0, i.e. w_v <= 1.
For (c): write the identity directly. Expanding,
F_G(w) - F_G(q) = sum_v [ f(w_v) - f(q_v) ] - ( M_G(w) - M_G(q) ).
Using (*), one checks term by term that
f(w_v) - f(q_v) = ( q_v log(q_v/w_v) - q_v + w_v ) + (q_v - w_v) log w_v,
and that (q_v - w_v) log w_v = -(q_v - w_v) w(N(v)). Summing over v and
expanding M_G(q) - M_G(w) = M_G(q - w) + sum_v (q_v - w_v) w(N(v)) (a
direct second-order expansion of the quadratic form about w), the cross
terms cancel and we are left with the stated identity. Because w is a
maximizer, the left side is >= 0. This proves (c). []
For the empty graph on no vertices we set F_G^* = 0.
--------------------------------------------------------------------
2. THE CROSS-MASS BOUND VIA RANDOM MULTIPLIERS
--------------------------------------------------------------------
The whole proof of the theorem uses exactly ONE consequence of the
extremal weight w: that edges between two not-too-heavy vertex sets are
controlled. We first prove a tool about random rescaling of weights.
LEMMA 2.1 (random multipliers, small expected edge mass).
Let r >= 2, let G be a finite K_r-free graph with positive vertex weights w,
and put s = w(V(G)). For every 0 < eps <= 1/2 there are jointly
distributed random variables (m_v) such that
0 <= m_v <= b_r(eps) := 2^{ r(r-2) } eps^{-(r-2)},
expectation of m_v equals 1 for every v,
expectation of M_G( (w_v m_v)_v ) is at most eps s^2,
and the joint distribution has finite support.
PROOF (induction on r). The case r = 2: a K_2-free graph has no edges,
so M_G = 0 and taking all m_v = 1 works. Now assume r >= 3 and set
eta = eps/4.
Starting from the whole graph, repeatedly do the following: if some vertex
of the current remaining induced subgraph has open neighborhood of weight
more than eta s (weights are the fixed numbers w), remove that whole open
neighborhood and call it one of the sets V_i. The removed sets are
disjoint and each has weight s_i = w(V_i) > eta s. Each induced graph
G[V_i] is K_{r-1}-free: if V_i contained an (r-1)-clique, together with the
vertex whose neighborhood produced V_i it would form a K_r, contradiction.
When the process stops, the remaining vertex set R has the property that
every vertex of R has neighborhood weight <= eta s inside R, so
M_{G[R]}(w) = (1/2) sum_{v in R} w_v w(N(v) cap R)
<= (1/2) (eta s) w(R)
<= (1/2) eta s^2. (**)
If no set V_i was removed, then G = G[R] and by (**) M_G(w) <= (1/2) eta
s^2 <= eps s^2; take all m_v = 1.
Otherwise let b = sum_i s_i > 0 and set p_i = s_i / (2b). Define the
multipliers by choosing a random "part":
- with probability 1/2 choose R, and set m_v = 2 for v in R, m_v = 0 else;
- with probability p_i choose V_i, internally apply the induction
hypothesis to the K_{r-1}-free graph G[V_i] with parameter eps/4 (its
total weight is s_i), and multiply the resulting multipliers by 1/p_i;
- all multipliers outside the chosen part are set to 0.
Each vertex has expected multiplier 1. Indeed, if v is in R it is retained
only when R is chosen, with m_v = 2, and that happens with probability 1/2
(the V_i each have total probability 1/2 combined), so the mean is 1. If v
is in some V_i, it survives only when V_i is chosen (probability p_i) with
internal mean 1 scaled by 1/p_i, so the mean is again 1.
The upper bound: since s_i > eta s and b <= s, we have 1/p_i = 2b/s_i <
2s/(eta s) = 2/eta = 8/eps. Thus on V_i the multiplier is at most
(8/eps) b_{r-1}(eps/4), and on R it is 2. A direct computation gives
(8/eps) b_{r-1}(eps/4) = 2^{ r(r-2) } eps^{-(r-2)} = b_r(eps),
and 2 <= b_r(eps) for r >= 3. So every m_v <= b_r(eps).
The edge-mass estimate: only edges inside the chosen part contribute. When
R is chosen, the edge mass is 4 M_{G[R]}(w) and this happens with
probability 1/2, so its expected contribution is at most 2 * (1/2) eta s^2
= eta s^2. When V_i is chosen, by induction the expected edge mass inside
V_i is at most (eps/4) s_i^2, scaled by (1/p_i)^2 because all weights are
multiplied by 1/p_i, and weighted by probability p_i; the contribution is
p_i (1/p_i)^2 (eps/4) s_i^2 = (eps/(4 p_i)) s_i^2
= (eps/4) (2b/s_i) s_i^2 = (eps/2) b s_i.
Summing over i gives (eps/2) b sum_i s_i = (eps/2) b^2 <= (eps/2) s^2.
Adding the two contributions,
expected M_G((w_v m_v)) <= eta s^2 + (eps/2) s^2
= (eps/4) s^2 + (eps/2) s^2
= (3/4) eps s^2 <= eps s^2.
Finite support is inherited from the induction, so this completes the
proof. []
Now fix the auxiliary function used to state the cross-mass bound. For
x >= 1 and s >= 0 define
g_x(s) = 0 if s = 0,
g_x(s) = s ( x + log^+(1/s) ) if s > 0,
where log^+(a) = max(log a, 0). The function g_x is nondecreasing on
[0,infinity): on (0,1) its derivative is x + log(1/s) - 1 >= 0, and on
(1,infinity) it is x, and the pieces fit continuously at s = 0 and s = 1.
LEMMA 2.2 (cross-mass bound).
Let r >= 2 and let w maximize F_G on a nonempty finite K_r-free graph G.
For every x >= 1 and all vertex sets S, D with w(S) <= e^x and w(D) <= e^x,
e_w(S, D) <= C_r g_x(w(S)), where C_r = 16 r^2.
PROOF. Step 1: assume S and D are disjoint. Put s = w(S), t = w(D).
The case s = 0 is trivial. First assume e^{-x} <= s.
Let eps = e^{-8x} and k = e^{4x}. Apply Lemma 2.1 to the K_r-free graph
G[S] (total weight s) with this eps, to get multipliers m_v with mean 1,
0 <= m_v <= b_r(eps), and expected edge mass <= eps s^2 inside S. Define a
random nonnegative vector q by
q_v = (1 + k m_v) w_v for v in S,
q_v = 0 for v in D,
q_v = w_v for v not in S union D.
Plug q into the variational identity of Lemma 1.1(c) and take expectations.
We bound the two pieces.
Quadratic term. q - w equals k m_v w_v on S, -w_v on D, and 0 elsewhere.
Expand M_G(q-w) as a sum over edges.
- Edges inside S: contribution k^2 m_u m_v w_u w_v; in expectation this is
k^2 times the expected edge mass inside S, at most k^2 eps s^2 = s^2
because k^2 eps = e^{8x} e^{-8x} = 1.
- Edges inside D: contribution w_u w_v, total M_{G[D]}(w) <= (1/2) t^2.
- Edges between S and D: contribution (k m_u w_u)(-w_v); in expectation,
using mean 1, total -k e_w(S,D).
So the expected quadratic term is at most
s^2 + (1/2) t^2 - k e_w(S,D). (2.a)
Vertex term. A vertex in D contributes w_v (the q_v = 0 case). A vertex
in S contributes w_v [ (1 + k m_v) log(1 + k m_v) - k m_v ], using the
elementary inequality (1+y) log(1+y) - y <= y log(1+y) with y = k m_v.
Since m_v <= b_r(eps),
log(1 + k b_r(eps)) <= A_r x, where
A_r = 4 + 8(r-2) + (1 + r(r-2)) log 2.
Hence the expected S-part is at most k A_r x s (using mean 1). Adding the
D-part t, the expected vertex term is at most t + k A_r x s.
Combine. The variational identity gives, in expectation,
0 <= (t + k A_r x s) + (s^2 + (1/2) t^2 - k e_w(S,D)).
Solve for e_w(S,D) and divide by k (note 1/k = e^{-4x}):
e_w(S,D) <= A_r x s + e^{-4x}( s^2 + t + t^2/2 ).
Now use s, t <= e^x and s >= e^{-x}. The three error terms, divided by s,
are at most e^{-3x}, e^{-2x}, e^{-x}/2 respectively, each at most x since
x >= 1; their sum is at most 3x. Therefore
e_w(S,D) <= (A_r + 3) x s <= (A_r + 3) g_x(s),
since g_x(s) = s(x + log^+(1/s)) >= x s.
Step 2: still disjoint, but 0 < s < e^{-x}. Put x' = log(1/s) > x. Both
weights are at most e^{x'} and s = e^{-x'}. Step 1 with x' gives
e_w(S,D) <= (A_r + 3) x' s = (A_r + 3) g_x(s), because log^+(1/s) = x' > x.
So for all disjoint S, D the bound holds with constant A_r + 3.
Step 3: arbitrary S, D. Randomly color every vertex independently into
class 1 or class 2 with probability 1/2 each. Let S' = S intersect class 1
and D' = D intersect class 2; these are disjoint and satisfy the same
weight upper bounds. Since there are no loops, each directed edge from S
to D has its two distinct ends landing in the required classes with
probability 1/4, so the expectation of e_w(S',D') is (1/4) e_w(S,D). The
disjoint bound plus monotonicity of g_x give
(1/4) e_w(S,D) <= (A_r + 3) E g_x(w(S')) <= (A_r + 3) g_x(s),
so e_w(S,D) <= 4 (A_r + 3) g_x(s). Finally 4 (A_r + 3) <= 16 r^2 = C_r
for r >= 2. This proves the lemma. []
We record the single consequence we will need later: if w maximizes F_G on
a K_r-free G, then (G,w) satisfies the "cross-mass condition with constant
C_r = 16 r^2", meaning that for all x >= 1 and all sets A, B with
w(A), w(B) <= e^x we have e_w(A,B) <= C_r g_x(w(A)).
--------------------------------------------------------------------
3. SPLITTING VERTICES PRESERVES THE CROSS-MASS BOUND
--------------------------------------------------------------------
Stage B replaces vertices by several copies that share the original
weight. This can only increase total weight, so we need to know the
cross-mass bound survives. The guideline that makes it work: each
original edge is retained AT MOST ONCE.
LEMMA 3.1 (preservation under splitting).
Let (G,w) satisfy the cross-mass condition with constant C. Let H be a
finite simple graph and let pi : V(H) -> V(G) be a map such that
(i) every edge {a,b} of H maps to an edge {pi(a),pi(b)} of G;
(ii) the map (a,b) -> (pi(a),pi(b)) is injective on DIRECTED edges of H.
Give each a in V(H) the weight w~_a = w_{pi(a)}. Then (H, w~) satisfies
the cross-mass condition with the SAME constant C, and
M_H(w~) <= M_G(w), T_H(w~) <= T_G(w),
w~( N_H(a) ) <= w( N_G(pi(a)) ) for every a in V(H).
These conclusions are stable under composing such maps.
PROOF. Take sets A, B contained in V(H) and let A_0 = pi(A), B_0 = pi(B).
Because vertices may be duplicated, w(A_0) <= w~(A) and w(B_0) <= w~(B).
Each directed edge counted by e_{H,w~}(A,B) maps, by (i), to a directed
edge counted by e_{G,w}(A_0,B_0), and by (ii) this map is injective, with
weights unchanged. So if w~(A), w~(B) <= e^x then also w(A_0), w(B_0) <=
e^x, and
e_{H,w~}(A,B) <= e_{G,w}(A_0,B_0) <= C g_x(w(A_0)) <= C g_x(w~(A)).
The last step uses monotonicity of g_x and w(A_0) <= w~(A). This is the
cross-mass condition for (H,w~).
Edge mass and triangle mass. Condition (ii) makes the map on edges
injective: two distinct edges of H cannot have the same unordered image,
because otherwise they could be oriented to share a directed image. So
distinct edges of H give distinct edges of G with equal weights, whence
M_H(w~) <= M_G(w). Likewise every triangle of H maps to a triangle of G
(pi restricted to the vertices of a clique is injective because G is
simple), distinct triangles have distinct images (their three edges have
at most one preimage each), and weights are unchanged, so T_H(w~) <= T_G(w).
Neighborhood bound. Fix a in V(H). Two distinct neighbors b, b' of a
cannot have pi(b) = pi(b'), because then the directed edges (a,b) and
(a,b') would share the image (pi(a), pi(b)), violating (ii). So pi maps
N_H(a) injectively into N_G(pi(a)), giving w~(N_H(a)) <= w(N_G(pi(a))).
Composition preserves vertex weights, adjacency, and injectivity on
directed edges, so all conclusions survive iterated splitting. []
Two special cases we use: deleting edges or vertices is a splitting with pi
the inclusion map. The big operating case is replacing one vertex u by
several copies that split up its incident edges, each copy getting weight
w_u and each original edge placed between the chosen copies of its two
ends, at most once.
--------------------------------------------------------------------
4. TRIANGLE COUNTING AND PEELING THIN EDGES
--------------------------------------------------------------------
For a positive-weighted finite simple graph G and a vertex u put
s_u = w(N(u)), c_{uv} = w( N(u) intersect N(v) ), (uv an edge)
h_u = sum_{v in N(u)} w_v c_{uv}.
Note c_{uv} is the total weight of common neighbors of u and v, and h_u is
twice the edge mass inside N(u).
LEMMA 4.1 (triangle normalization and peeling).
With the notation above:
(a) sum over edges {u,v} of w_u w_v c_{uv} = 3 T_G(w),
sum over vertices u of w_u h_u = 6 T_G(w).
In particular, if every neighborhood has weight at most L, then
T_G(w) <= (L/3) M_G(w).
(b) For every tau > 0 there is a spanning subgraph G' obtained by
deleting edges, such that every edge of G' has common-neighbor
weight (computed in G') at least tau, and
T_{G'}(w) >= T_G(w) - tau M_G(w).
Every nonisolated vertex of G' has s_u >= tau and h_u >= tau s_u
(computed in G'). If G satisfies the cross-mass condition, so does
G', with the same constant.
PROOF (a). Each triangle {u,v,z} contributes its weight w_u w_v w_z once
for each of its three edges to the first sum (giving 3 T_G(w)), and once
for each of its six oriented edges to the second (giving 6 T_G(w)). These
are just two ways of counting triangle weight.
For the "terminal bound": since c_{uv} <= L always, the first identity
gives 3 T_G(w) = sum w_u w_v c_{uv} <= L sum w_u w_v = L M_G(w), hence
T_G(w) <= (L/3) M_G(w).
PROOF (b). Starting from G, repeatedly delete any edge whose current
common-neighbor weight is less than tau, and stop when none is left. The
process ends because the graph is finite. Let {u_i, v_i} be the i-th
deleted edge and c_i its common-neighbor weight just before deletion. The
triangle weight destroyed at that step is exactly w_{u_i} w_{v_i} c_i
(these are the triangles using that edge and two common neighbors, which
disappear when the edge goes). Each destroyed triangle is counted at its
first deleted edge, so
T_G(w) - T_{G'}(w) = sum_i w_{u_i} w_{v_i} c_i
<= tau sum_i w_{u_i} w_{v_i}
<= tau M_G(w).
The stopping rule gives c_{uv} >= tau on all remaining edges. If u is
nonisolated in G', pick a remaining neighbor v: then s_u >= c_{uv} >= tau.
Summing w_v c_{uv} >= tau w_v over the remaining neighbors gives h_u >=
tau s_u. Since G' is obtained from G by edge deletions, it is the image of
an inclusion map, so Lemma 3.1 gives the same cross-mass constant. []
--------------------------------------------------------------------
5. LOCAL RANDOM WALKS AND ENTROPY
--------------------------------------------------------------------
This section builds, for each vertex u, probability distributions on its
neighborhood N(u), one for each starting point v in N(u), such that rows
belonging to the two far corners of a triangle are on average close. The
closeness is measured in total variation and averaged with triangle weight.
The mechanism is a lazy weighted random walk; the key estimate is that its
row entropy grows slowly, so at some common time the rows are close.
Throughout this section G is a finite simple graph with positive weights
satisfying the cross-mass condition with constant C. Fix x >= 32, and
assume G has at least one edge and
s_u <= e^x for every vertex u, (neighborhoods not too heavy)
c_{uv} >= x^{-1} for every edge uv. (edges lie in real triangles)
Then every nonisolated u has s_u >= x^{-1} and h_u >= s_u / x. For such u
define the distribution and kernels on the finite set N(u):
pi_u(v) = w_v c_{uv} / h_u, v in N(u);
P_u(v,z) = w_z [vz is an edge] / c_{uv}, v, z in N(u);
Q_u = (I + P_u)/2; (one lazy step)
K_u^j = P_u Q_u^j, j >= 0.
So P_u is a weighted random walk on the induced graph G[N(u)]; Q_u adds a
probability 1/2 of staying put; the row K_u^j(v, .) is the law after one
P_u-step from v followed by j lazy steps. The first step alone satisfies
P_u(v,y) <= x w_y because c_{uv} >= 1/x; the next lemma shows later steps
keep this density bound.
Probability laws we use. Put Z = sum_u w_u h_u = 6 T_G(w) > 0 and define
the directed-edge law
mu(u,v) = w_u w_v c_{uv} / Z.
Given u, the conditional law of v is exactly pi_u. If we then sample z from
P_u(v, .), the triple (u,v,z) has law
probability of (u,v,z) = w_u w_v w_z / Z
on each ordered triangle. Indeed mu(u,v) P_u(v,z) = (w_u w_v c_{uv}/Z)
(w_z/c_{uv}) = w_u w_v w_z/Z, and the total over all ordered triples is
6 T_G(w)/Z = 1. We call this the ordered triangle law.
Weighted entropy. For a probability vector a supported on positive-weight
vertices put
H_w(a) = sum_{y : a(y) > 0} a(y) log( w_y / a(y) ),
and let H_j = expectation over (u,v) drawn from mu of H_w( K_u^j(v, .) ).
Total variation distance is ||a-b||_TV = (1/2) sum_y |a(y) - b(y)|.
LEMMA 5.1 (smoothing the local walks).
Under the above hypotheses, set
E_C = 42 C^2 + 2 C, A_C = 10 + E_C,
B_C = 2 sqrt(A_C + 1), R = ceil(x).
Then each K_u^j is reversible with stationary measure pi_u and
K_u^j(v,y) <= x w_y for all j >= 0, (5.a)
-log x <= H_0 <= H_1 <= ... <= H_R <= A_C log x. (5.b)
Moreover there exists an integer j with 0 <= j <= R-1 such that, under the
ordered triangle law,
expectation of || K_u^j(v, .) - K_u^j(z, .) ||_TV
<= B_C sqrt( log x / x ). (5.c)
PROOF. We check reversibility and the density bound first, then bound the
entropy, then find a small entropy increment and convert it to closeness.
Reversibility and density. Detailed balance:
pi_u(v) P_u(v,z) = (w_v c_{uv}/h_u)(w_z/c_{uv}) = w_v w_z / h_u,
which is symmetric in v,z. So P_u is reversible with stationary pi_u. Its
powers, Q_u, and K_u^j inherit this; no irreducibility is needed. Every row
of P_u satisfies P_u(v,y) <= x w_y (using c_{uv} >= 1/x). Since P_u and Q_u
are both functions of P_u they commute, so
K_u^j(v,y) = sum_z Q_u^j(v,z) P_u(z,y) <= x w_y sum_z Q_u^j(v,z) = x w_y,
giving (5.a). It follows that H_j >= -log x: each a(y) <= x w_y, so
w_y/a(y) >= 1/x and each logarithm is at least -log x.
Step 1: sets that contain most of the walk. Write L = e^x. Fix a
nonisolated starting vertex v and build nested sets inside the whole graph,
S_0(v) = N(v), and
S_{i+1}(v) = S_i(v) union { y : w(N(y) intersect S_i(v)) >= x^{-6}/L }.
We drop the argument v while it is fixed. Double counting gives
sum_y w_y w(N(y) intersect S_i) = sum_{z in S_i} w_z s_z <= L w(S_i),
because s_z <= L. Each vertex newly added to S_{i+1} has w(N(y) intersect
S_i) >= x^{-6}/L, so its own weight is at most (L/x^{-6}) w(N(y) intersect
S_i); summing the new weight and using the double count,
w(S_{i+1}) <= (1 + L^2 x^6) w(S_i).
Iterating and using w(S_0) = w(N(v)) <= L,
w(S_R) <= e^x (1 + e^{2x} x^6)^R <= e^{20 x^2},
where we used x >= 32 to get 6 log x <= x, log(1 + e^{2x} x^6) <= 4x, and
R <= 2x.
Step 2: leakage bound. Claim: for every edge uv and every 0 <= i <= R,
K_u^i( v, N(u) minus S_i(v) ) <= i x^{-4}. (5.d)
Proof by induction on i. For i = 0, K_u^0 = P_u has support inside N(v) =
S_0, so the mass outside is 0. For the step, mass already outside S_i
contributes at most i x^{-4}, and stays outside S_{i+1}. New mass reaching
a vertex y in N(u) but not in S_{i+1} comes from z in S_i with z != y (if
z = y then y in S_i which is inside S_{i+1}). For such y we have
w(N(y) intersect S_i) < x^{-6}/L, and by (5.a) the density bound gives, for
each source z,
K_u^i(v,z) Q_u(z,y) <= (x w_z)(x w_y) = x^2 w_z w_y.
Summing over z in N(u) intersect S_i intersect N(y):
sum_z ... <= x^2 w_y w(N(y) intersect S_i) <= x^2 w_y (x^{-6}/L)
= x^{-4} w_y / L.
Summing over y in N(u) gives at most x^{-4}/L times s_u <= x^{-4}. So the
new mass is <= x^{-4}, and the total outside S_{i+1} is at most (i+1)x^{-4},
proving (5.d).
Step 3: most neighborhoods meet S_R in small weight. S_R(v) has total
weight <= e^{20x^2}. For fixed v define
B_v = { u in N(v) : w(N(u) intersect S_R(v)) > x^8 }.
First use of the cross-mass condition with parameter 20 x^2 gives
x^8 w(B_v) <= e_w(N(v), S_R(v))
<= C s_v ( 20 x^2 + log^+(1/s_v) ) <= 21 C x^2 s_v,
using s_v >= x^{-1}; hence w(B_v) <= 21 C x^{-6} s_v.
We must convert this weight estimate into the conditional law of u given v
under mu, which is not normalized vertex weight. By symmetry of mu,
P_mu( u in B_v | v ) = ( sum_{u in B_v} w_u c_{uv} ) / h_v
= e_w(B_v, N(v)) / h_v.
Second use of the cross-mass condition, with parameter x (valid since
B_v is contained in N(v) and s_v <= e^x): since g_x(b) <= 2x max(b, e^{-x})
for b >= 0,
P_mu( u in B_v | v ) <= C * 2x * max( w(B_v), e^{-x} ) / h_v.
Using h_v >= s_v/x and s_v >= x^{-1},
P_mu( u in B_v | v ) <= 2C x^2 / s_v * ( w(B_v) + e^{-x} )
<= 42 C^2 x^{-4} + 2C x^3 e^{-x} <= E_C x^{-4},
where the last step uses e^{-x} <= x^{-7} for x >= 32. So B_v is a rare
event under mu, of probability at most E_C x^{-4}.
Step 4: bounding H_R. First, if a probability vector a is supported on a
set D of total weight m > 0, then H_w(a) <= log m: normalize the weights on
D and use nonnegativity of relative entropy.
If u is NOT in B_v, the set D = N(u) intersect S_R(v) has weight <= x^8, and
(5.d) says K_u^R(v, D) = 1 - delta with 0 <= delta <= R x^{-4} < 1.
Condition the row on D and on its complement. The support bound plus the
binary-entropy bound give
H_w( K_u^R(v, .) ) <= log 2 + 8 log x + delta x.
If u IS in B_v, use the coarse bound H_w(K_u^R(v,.)) <= log s_u <= x.
Averaging, and using that B_v has mu-probability at most E_C x^{-4},
H_R <= log 2 + 8 log x + R x^{-3} + E_C x^{-3} <= A_C log x,
using R <= 2x, x >= 32, and the definition of A_C. This is the right end
of (5.b); the left end H_0 >= -log x is already proved.
Step 5: a small entropy increment gives close rows. For probability
vectors a, b let D(a||b) = sum_{y: a(y)>0} a(y) log( a(y)/b(y) ) be the
relative entropy (interpreted as +infinity if needed).
Sample (u,v) from mu and then z from Q_u(v, .). Because Q_u K_u^j =
K_u^{j+1}, the mixture of the rows K_u^j(z, .) over z drawn from Q_u(v, .)
is exactly the row K_u^{j+1}(v, .). A standard entropy decomposition then
gives, for fixed u, v,
E_{z ~ Q_u(v,.)} D( K_u^j(z,.) || K_u^{j+1}(v,.) )
= H_w( K_u^{j+1}(v,.) )
- E_{z ~ Q_u(v,.)} H_w( K_u^j(z,.) ).
Now average over (u,v) from mu. Conditional on u, the law of v is pi_u,
which is stationary for Q_u, so the average of H_w(K_u^j(z,.)) over z~Q_u
and then v~pi_u equals the average of H_w(K_u^j(v,.)) over v~pi_u. Hence
H_{j+1} - H_j = E_{mu Q} D( K_u^j(z,.) || K_u^{j+1}(v,.) ) >= 0, (5.e)
so the sequence H_j is nondecreasing. Telescoping (5.b),
H_R - H_0 <= A_C log x + log x = (A_C + 1) log x,
so some j with 0 <= j <= R-1 satisfies
H_{j+1} - H_j <= (A_C + 1) log x / R <= (A_C + 1) log x / x.
Next, total variation is controlled by relative entropy: ||a-b||_TV <=
sqrt(D(a||b)). (This follows from D(a||b) >= -2 log sum_y sqrt(a(y)b(y))
>= sum_y ( sqrt(a(y)) - sqrt(b(y)) )^2 and Cauchy-Schwarz.) Combining with
(5.e) and Jensen's inequality,
E_{mu Q} || K_u^j(z,.) - K_u^{j+1}(v,.) ||_TV
<= sqrt( H_{j+1} - H_j ) <= sqrt( (A_C+1) log x / x ).
Step 6: pass to the ordered triangle law. Within a fixed neighborhood set
a_v = K_u^j(v, .) and b_v = K_u^{j+1}(v, .). The triangle inequality and
Q_u = (I + P_u)/2 give
E_{mu P} || a_v - a_z ||_TV
<= E_mu || a_v - b_v ||_TV + E_{mu P} || a_z - b_v ||_TV
= 2 E_{mu Q} || a_z - b_v ||_TV,
where mu P denotes the ordered triangle law. (The identity uses that the
Q_average is half "stay" and half "one P-step".) Therefore
E_{mu P} || K_u^j(v,.) - K_u^j(z,.) ||_TV
<= 2 sqrt( (A_C+1) log x / x ) = B_C sqrt( log x / x ),
which is (5.c). []
--------------------------------------------------------------------
6. COUPLING THE WALKS, SPLITTING BY LABELS, AND THE TRIANGLE THEOREM
--------------------------------------------------------------------
We now turn "close on average" into an actual splitting of vertices. The
tool is a joint sampling that keeps two rows equal as often as possible.
Subsection 6.1: shared rejection sampling.
LEMMA 6.1 (shared rejection).
Let I and J be finite nonempty sets and let (p_i)_{i in I} be probability
distributions on J. There are jointly distributed random variables
(Y_i)_{i in I} with Y_i having law p_i and, for all i, i',
P( Y_i != Y_{i'} ) <= 2 ||p_i - p_{i'}||_TV / (1 + ||p_i - p_{i'}||_TV)
<= 2 ||p_i - p_{i'}||_TV.
The joint law has finite support.
PROOF. Let m = |J|. Take independent trials (Z_t, U_t), t = 1,2,..., 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 at which U_t <= p_i(Z_t). A single trial is accepted by row
i with probability 1/m, and its accepted value has law p_i; explicitly
P(Y_i = y) = sum_{t>=1} (1 - 1/m)^{t-1} ( p_i(y)/m ) = p_i(y).
Every row stops almost surely, and since I is finite, all rows stop within
finitely many trials almost surely.
Now fix two rows p, q and let d = ||p-q||_TV. At the first trial accepted by
either row, the probability that both accept it equals
( sum_y min(p(y), q(y)) ) / ( sum_y max(p(y), q(y)) ) = (1 - d)/(1 + d).
On that event the two labels agree. They may also agree otherwise, so the
disagreement probability is at most 1 - (1-d)/(1+d) = 2d/(1+d). The label
vector lives in the finite set J^I, hence finite support; the infinite
trial sequence is only a device to construct that finite joint law. []
Subsection 6.2: admissibility and splitting.
Let H be a finite graph with positive weights satisfying the cross-mass
condition with constant C >= 1. Assume every edge uv has c_{uv} >= 1/x,
every neighborhood has weight at most e^x, x >= 32, and (since edges have
common neighbors) T_H(w) > 0. We may drop isolated vertices.
Use the index j supplied by Lemma 5.1 and write K_u = K_u^j on N_H(u). The
directed-edge law is mu(u,v) = w_u w_v c_{uv} / (6 T_H(w)); conditional on
u, v has law pi_u(v) = w_v c_{uv}/h_u, and K_u is reversible for pi_u. The
constants from Lemma 5.1 are A_C = 10 + 42 C^2 + 2 C and B_C = 2 sqrt(A_C+1).
So K_u(v,y) <= x w_y, the average row entropy is at most A_C log x, and the
average TV distance between the rows at the two far corners of a weighted
ordered triangle is at most B_C sqrt(log x / x).
For each nonisolated u, apply Lemma 6.1 to the rows of K_u and call the
label given to v in N_H(u) Y_{u,v}. These finite joint laws are sampled
independently over u. Call a label y at the incidence (u,v) ADMISSIBLE if
K_u(y, v) >= w_v e^{-sqrt x}. (6.a)
For a fixed label outcome define the group
A_{u,y} = { v in N_H(u) : Y_{u,v} = y and K_u(y,v) >= w_v e^{-sqrt x} }.
The reversal in (6.a) is deliberate: it lets every vertex of a group be
compared with one probability row. Since each member satisfies w_v <=
e^{sqrt x} K_u(y,v),
w(A_{u,y}) <= e^{sqrt x} sum_{v in A_{u,y}} K_u(y,v) <= e^{sqrt x}. (6.b)
This holds for EVERY label outcome.
LEMMA 6.2 (few inadmissible incidences).
The probability that Y_{u,v} is inadmissible, averaged over (u,v) drawn from
mu, is at most
delta_x := (A_C + 1) log x / ( sqrt x + log x ).
PROOF. Under (u,v)~mu and y~K_u(v,.), reversibility gives the equality in
law (u,v,y) = (u,y,v). On this support all probabilities are positive, so
reversibility pi_u(v) K_u(v,y) = pi_u(y) K_u(y,v) holds. Define
ell = log( w_v / K_u(y,v) ). Its mean is the row entropy, so E[ell] = H_j <=
A_C log x. The density bound applied to the reversed row gives K_u(y,v) <=
x w_v, i.e. ell >= -log x. Inadmissibility (6.a) is exactly the event
ell > sqrt x. Apply Markov to the nonnegative variable ell + log x:
P(ell > sqrt x) = P(ell + log x > sqrt x + log x)
<= ( E[ell] + log x ) / ( sqrt x + log x )
<= (A_C + 1) log x / ( sqrt x + log x ).
No per-row entropy bound is used. []
Now build a new graph H'. For each nonempty group make one vertex (u,y) of
weight w_u. For each edge uv of H whose two incidence labels are both
admissible, put an edge between (u, Y_{u,v}) and (v, Y_{v,u}). (So each old
edge produces at most one new edge.) The map (u,y) -> u is the projection.
LEMMA 6.3 (weighted splitting).
For at least one choice of the labels, the projection (u,y) -> u preserves
weights, maps directed edges injectively to directed edges of H, and
max_{a in V(H')} w( N_{H'}(a) ) <= e^{sqrt x}, (6.c)
T_{H'}(w) >= (1 - a_C log x / sqrt x) T_H(w), (6.d)
where a_C = 6 ( B_C + A_C + 1 ).
PROOF. Each old edge gives at most one new edge, so the projection is
injective on directed edges, and H' has no loops or multiple edges. At a
fixed vertex (u,y), different neighbors project to different vertices of H
(H is simple and each edge uv was used at most once), so by (6.b)
w( N_{H'}(u,y) ) <= w(A_{u,y}) <= e^{sqrt x},
which is (6.c). In particular, duplicating u does not duplicate any of its
incident edges at a fixed copy.
Triangle survival. An old triangle {u,v,z} survives in H' exactly when its
two labels agree at each of its three corners and all six incidence labels
are admissible. These conditions are also necessary for the three edges to
become a triangle of H'. A triangle of H' projects to three distinct old
vertices, hence to an old triangle; and there is at most one triangle over
each old triangle, because each old edge has at most one preimage. Weights
of a surviving triangle are unchanged.
Loss estimate. Sample an ordered triangle (u,v,z) with probability
w_u w_v w_z / (6 T_H(w)); its ordered-edge marginal is mu. At the corner u,
the shared coupling (Lemma 6.1) and the row-distance estimate give
E P( Y_{u,v} != Y_{u,z} ) <= 2 B_C sqrt( log x / x ).
The same bound holds at the other two corners by symmetry of the ordered
triangle law. Each of the six directed incidences has marginal mu, so
Lemma 6.2 bounds the average inadmissibility probability of each by delta_x.
A union bound (no independence needed) gives
E( T_H(w) - T_{H'}(w) ) / T_H(w)
<= 6 B_C sqrt(log x / x) + 6 delta_x
<= a_C log x / sqrt x,
using sqrt(log x / x) <= log x / sqrt x, delta_x <= (A_C+1) log x / sqrt x,
and log x >= 1. The label vectors have finite support, so at least one
deterministic choice of labels gives triangle mass at least its expectation,
proving (6.d). []
Subsection 6.3: reduction step and iteration.
Choose X = X(C) >= 32 so large that
2 a_C log X / sqrt X <= 1/2. (6.e)
Such X depends only on C.
PROPOSITION 6.4 (neighborhood reduction).
Let G be a finite positive-weighted graph satisfying the cross-mass
condition with constant C >= 1, and suppose max_v w(N_G(v)) <= e^x for some
x > X(C). Then there is a finite positive-weighted graph G' with a
weight-preserving map to G that is injective on directed edges, such that
max_v w( N_{G'}(v) ) <= e^{sqrt x}, (6.f)
T_{G'}(w) >= (1 - a_C log x / sqrt x) T_G(w) - M_G(w)/x, (6.g)
and (G',w) satisfies the same cross-mass condition with M_{G'}(w) <= M_G(w).
PROOF. First peel edges whose current common-neighbor weight is less
than 1/x. By Lemma 4.1(b) with tau = 1/x the remaining graph H satisfies
T_H(w) >= T_G(w) - M_G(w)/x.
Edge deletion does not increase any neighborhood weight and preserves the
cross-mass condition (Lemma 3.1). If H has no edges, take G' to be empty;
then T_H = 0, so T_G(w) <= M_G(w)/x, which implies (6.g). Otherwise apply
Lemma 6.3 to H. Since t -> log t / sqrt t is decreasing for t >= e^2,
(6.e) ensures 0 <= 1 - a_C log x / sqrt x <= 1, and therefore
T_{G'}(w) >= (1 - a_C log x / sqrt x)( T_G(w) - M_G(w)/x )
>= (1 - a_C log x / sqrt x) T_G(w) - M_G(w)/x.
The projection through H is still injective on directed edges, and the edge
mass bound and cross-mass condition follow from Lemma 3.1. []
THEOREM 6.5 (triangle mass from cross mass).
For every C >= 1 there is a constant C_tri(C), depending only on C, such
that every finite simple graph G with positive weights satisfying the
cross-mass condition with constant C satisfies T_G(w) <= C_tri(C) M_G(w).
PROOF. If G has no edges, both sides are zero. Otherwise choose x_0 >= 1
with every neighborhood weight at most e^{x_0}. While x_i > X, apply
Proposition 6.4 and set x_{i+1} = sqrt(x_i). Write G_i, T_i, M_i for the
successive graphs and masses (weights are inherited from vertex copies). The
procedure stops after finitely many steps k with x_k <= X; the case k = 0 is
allowed.
Two bounds, independent of x_0 and k. If k > 0, put y = x_{k-1} > X, so the
used parameters, read in reverse, are y, y^2, y^4, ..., y^{2^{k-1}}. For
f(t) = log t / sqrt t and t >= X >= 32,
f(t^2) / f(t) = (2 log t / t) / (log t / sqrt t) = 2 / sqrt t <= 1/2.
Since f is decreasing on [X, infinity), it follows that
sum_{i<k} a_C f(x_i) <= 2 a_C f(X) <= 1/2, (6.h)
sum_{i<k} 1/x_i <= (1/X)/(1 - 1/X) <= 1. (6.i)
Both inequalities are trivial for the empty sum when k = 0.
Let eps_i = a_C f(x_i). Iterate (6.g), using M_i <= M_0 and 0 <= 1 - eps_i
<= 1:
T_k >= ( product_{i<k} (1 - eps_i) ) T_0 - M_0 sum_{i<k} 1/x_i
>= (1/2) T_0 - M_0,
because product (1 - eps_i) >= 1 - sum eps_i >= 1/2 by (6.h), and the sum
of 1/x_i is <= 1 by (6.i).
Every neighborhood of G_k has weight at most e^X, so by Lemma 4.1(a),
3 T_k = sum_{edges {u,v} in G_k} w_u w_v w( N_{G_k}(u) intersect N_{G_k}(v) )
<= e^X M_k <= e^X M_0.
Combining the last two displays,
(1/2) T_0 - M_0 <= T_k <= e^X M_0 / 3,
so T_0 <= 2 (1 + e^X/3) M_0. Hence C_tri(C) = 2 (1 + e^{X(C)}/3) works.
All thresholds and constants depend only on C; neither the number of
vertices nor the initial neighborhood bound appears. []
We now connect back to graphs. Apply Theorem 6.5 to the cross-mass bound of
Lemma 2.2 (which holds with constant C_r = 16 r^2). For every maximizer w
of F_G on a finite K_r-free graph we obtain
T_G(w) <= B_r M_G(w), where B_r = C_tri(16 r^2). (6.j)
The constant B_r depends only on r. (The zero-vertex case has both masses
zero.) This is the triangle estimate that drives the final stage.
--------------------------------------------------------------------
7. FROM TRIANGLE MASS TO INDEPENDENT SETS
--------------------------------------------------------------------
Let B_r be the constant in (6.j) and set
D_r = 3 + (3/2) B_r.
Everything here depends on r only.
PROPOSITION 7.1 (maximum-degree bound).
For every integer r >= 4, every real Delta >= 3, and every finite K_r-free
graph G with n vertices and maximum degree at most Delta,
alpha(G) >= F_G^* / ( D_r log Delta ), and
alpha(G) >= n log Delta / ( 4 D_r Delta ).
PROOF. Fix Delta >= 3 and prove the first inequality by induction on n. For
the empty graph both sides are zero. Assume n > 0, let w maximize F_G, and
write W = w(V(G)) = sum_v w_v. By Lemma 1.1, 0 < w_v <= 1.
Deletion cost of one closed neighborhood. For a vertex v put A_v = {v} union
N(v) and let G - A_v be the induced graph on the remaining vertices. Define
q to be 0 on A_v and equal to w elsewhere. Then F_G(q) = F_{G-A_v}( w
restricted to V(G) minus A_v ), because q vanishes on A_v and equals w on the
rest. Substituting q into the variational identity of Lemma 1.1(c): each
vertex of A_v contributes w_v (the q_v = 0 case), each vertex outside
contributes 0; and q - w equals -w on A_v and 0 elsewhere, so
M_G(q - w) = M_{G[A_v]}(w). Hence
F_G(w) - F_{G-A_v}(w|) = w(A_v) + M_{G[A_v]}(w).
Since w restricts to a feasible weight on G - A_v and F_G(w) = F_G^*,
F_G^* - F_{G-A_v}^* <= w(A_v) + M_{G[A_v]}(w). (7.a)
Average over v chosen with probability w_v / W. The average of w(A_v) is
(1/W) sum_v w_v ( w_v + w(N(v)) )
= (1/W) ( sum_v w_v^2 + 2 M_G(w) ),
since sum_v w_v w(N(v)) = 2 M_G(w). The average of M_{G[A_v]}(w):
an edge inside A_v = {v} union N(v) is either an edge from v to a neighbor
(contributing sum_v w_v^2 w(N(v)) when summed against w_v) or an edge
between two neighbors of v. The latter sums to
sum_v w_v M_{G[N(v)]}(w)
= sum over edges {a,b} of w_a w_b w( N(a) intersect N(b) )
= sum over edges {a,b} of w_a w_b c_{ab}
= 3 T_G(w),
by Lemma 4.1(a). So the average deletion cost equals
(1/W) ( sum_v w_v^2 + 2 M_G(w) + sum_v w_v^2 w(N(v)) + 3 T_G(w) ).
Now bound each term. Since w_v <= 1, sum_v w_v^2 <= W and
sum_v w_v^2 w(N(v)) <= sum_v w_v w(N(v)) = 2 M_G(w). And 3 T_G(w) <=
3 B_r M_G(w) by (6.j). Therefore the average cost is at most
1 + (4 + 3 B_r) M_G(w) / W.
Bounding 2 M_G(w)/W by log Delta. By stationarity (Lemma 1.1) log(1/w_v) =
w(N(v)). Jensen's inequality for -log gives
log(n/W) <= (1/n) sum_v log(1/w_v)
= (1/n) sum_v w(N(v))
= (1/n) sum_v deg(v) w_v
<= (Delta/n) sum_v w_v = Delta W / n.
If W/n < 1/Delta then the left side exceeds log Delta > 1 while the right
side is less than 1, a contradiction; hence W >= n/Delta. Then by concavity
of log with the probabilities w_v/W,
2 M_G(w)/W = (1/W) sum_v w_v w(N(v))
= (1/W) sum_v w_v log(1/w_v)
= sum_v (w_v/W) log(1/w_v)
<= log( sum_v (w_v/W)(1/w_v) )
= log(n/W) <= log Delta,
where the final inequality uses W >= n/Delta. Hence (4+3B_r)M_G(w)/W <=
(2 + (3/2)B_r) log Delta, and since log Delta >= 1,
average cost <= 1 + (2 + (3/2) B_r) log Delta <= D_r log Delta.
So some vertex v has w(A_v) + M_{G[A_v]}(w) <= D_r log Delta. By (7.a),
F_{G - A_v}^* >= F_G^* - D_r log Delta.
The graph G - A_v is K_r-free with maximum degree at most Delta. By
induction its independent sets satisfy alpha(G - A_v) >= F_{G-A_v}^*/(D_r
log Delta), and adjoining v (which is nonadjacent to all of G - A_v) gives
alpha(G) >= 1 + alpha(G - A_v)
>= 1 + (F_G^* - D_r log Delta)/(D_r log Delta)
= F_G^*/(D_r log Delta).
This proves the first inequality.
Second inequality (a test weight). Take the constant vector with all
entries p = (log Delta)/Delta. Since |E(G)| <= n Delta/2,
F_G(p) = n p (1 - log p) - p^2 |E(G)|
>= n p (1 - log p) - p^2 (n Delta/2)
= n p ( 1 - log p - (Delta p)/2 ).
Now -log p = log Delta - log log Delta, so the bracket is
1 + (1/2) log Delta - log log Delta. The function 1 + t/4 - log t has
minimum 2 - log 4 > 0 at t = 4, which shows that 1 + t/2 - log t >= t/4 for
all t > 0. With t = log Delta,
F_G(p) >= n p (1/4) log Delta = n (log Delta)^2 / (4 Delta).
Combining with the first inequality,
alpha(G) >= F_G^*/(D_r log Delta)
>= n (log Delta)^2 / (4 Delta) / (D_r log Delta)
= n log Delta / (4 D_r Delta).
This proves the proposition. []
PROOF OF THE MAIN THEOREM. Let G have n vertices and average degree d >= 2
and be K_r-free. Delete the vertices whose degree in G exceeds 2d, and let
H be the induced graph on the vertices that remain. Fewer than n/2 vertices
are deleted: if at least n/2 vertices had degree more than 2d, the degree
sum would exceed 2d (n/2) = nd, contradicting that the degree sum equals
nd. So |V(H)| >= n/2. Also H is K_r-free with maximum degree at most the
real number Delta = 2d >= 4 >= 3. Proposition 7.1 gives
alpha(G) >= alpha(H)
>= |V(H)| log(2d) / (4 D_r (2d))
= |V(H)| log(2d) / (8 D_r d)
>= (n/2) log(2d) / (8 D_r d)
= n log(2d) / (16 D_r d)
>= n log d / (16 D_r d),
using log(2d) >= log d. Therefore c_r = 1/(16 D_r) works. Tracing the
constants, B_r depended only on r (through C_tri(16 r^2)), so D_r and c_r
depend only on r. This is the main theorem. []
====================================================================
END OF PROOF.
====================================================================