editors: nobody
The object is the correspondence chromatic number, also called the
DP-chromatic number. A correspondence assignment on a finite simple
graph G assigns each vertex v a finite set L(v) of entries and each
edge uv a matching M_uv between L(u) and L(v). A coloring chooses
c(v) in L(v) at each vertex so that no edge uv has (c(u), c(v)) in
M_uv. The correspondence chromatic number chi_DP(G) is the least k
such that every assignment with |L(v)| >= k admits a coloring. The
matchings need not agree around a cycle, so entries carry no global
color names, and this absence of names is the only obstacle beyond
list coloring. List coloring is the case where entries are copies of
named colors and M_uv forbids equal names; ordinary coloring is the
case of one common k-element list. Hence
chi(G) <= chi_list(G) <= chi_DP(G) <= Delta + 1,
with Delta the maximum degree and the last bound by greedy. The list
and correspondence refinements go back to Vizing, to Erdos, Rubin and
Taylor, and to Dvorak and Postle.
sources/erdos-rubin-taylor-1980.pdf
sources/erdos-lovasz-1975.pdf
sources/dvorak-postle.pdf
Theorem. For every integer r >= 4 there is a constant C_r such that
every K_r-free graph G of maximum degree Delta >= 3 satisfies
chi_DP(G) <= ceil( C_r Delta / log Delta ),
where log is natural and C_r depends only on r.
The greedy bound carries a factor log Delta. Triangle-free graphs
already obey chi <= (1+o(1)) Delta/log Delta (Johansson); the list and
K_r-free versions were given by Molloy and sharpened through local
occupancy by Davies, Kang, Pirot and Sereni; Bernshteyn carried the
Johansson-Molloy bound to correspondence coloring, at the cost of a
factor log log Delta. That factor is removed below for every
forbidden clique K_r with r >= 4.
sources/molloy-clique.pdf
sources/davies-kang-pirot-sereni.pdf
sources/bernshteyn-johansson-molloy.pdf
sources/bernshteyn-asymptotic.pdf
For other forbidden graphs the sharp order is known in families.
Alon, Krivelevich and Sudakov proved O(Delta/log f) coloring when each
neighborhood spans at most Delta^2/f edges, and Vu obtained the list
form. Anderson, Bernshteyn and Dhawan proved correspondence bounds
with explicit leading constants for bipartite and almost-bipartite
forbidden graphs, and Przybylo gave clique-excluded list bounds phrased
in the graph of forbidden pairs. Dhawan, Janzer and Methuku proved
O(Delta/log Delta) ordinary coloring of K_{t,t,t}-free graphs, hence of
every fixed three-colorable forbidden graph, with the independence
bound (1-o(1)) n log d / d. These are ordinary or list results; the
correspondence bound without log log Delta for every forbidden clique
is proved below.
sources/anderson-bd-bipartite.pdf
sources/anderson-bd-almost-bipartite.pdf
sources/przybylo-triangle-free.pdf
sources/dhawan-janzer-methuku.pdf
https://doi.org/10.1006/jctb.1999.1910
https://doi.org/10.1017/S0963548301004898
The order Delta/log Delta cannot be lowered. Triangle-free graphs of
maximum degree Delta and chromatic number of order Delta/log Delta
exist (Bollobas; Kim), and triangle-free graphs are K_4-free, so the
theorem is sharp up to the constant C_r.
https://doi.org/10.1002/rsa.3240070302
A coloring is built up by keeping a partial coloring and, at each still
uncolored vertex, only the entries compatible with the colors already
chosen on its neighbors. Weight every compatible entry by a
nonnegative real w_i, put w_i > 0 for usable entries, and let H be the
graph whose vertices are the positive-weight entries and whose edges
are the forbidden pairs. The sets L(v) partition V(H), and two facts
fix the structure. First, H is K_r-free: a clique of H projects to
pairwise adjacent vertices of G, since a forbidden pair lies on an edge
of G and entries in distinct parts sit at distinct vertices, so a K_r
in H would be a K_r in G. Second, every entry has at most one neighbor
in any one part, because the forbidden pairs along a single edge form
a matching. The coloring problem is therefore a problem about a
weighted K_r-free graph H split into parts, each vertex meeting each
part at most once.
For an uncolored v write W_v = sum_{i in L(v)} w_i, and for an entry i
write s_i = sum_{u in N_H(i)} w_u. The invariant is
K/2 <= W_v <= 2K (WIN)
at every uncolored vertex and
Delta^{-3} <= w_i <= Delta^{-0.99}, s_i <= Lambda (SMALL)
at every positive entry, where Lambda = 20 log Delta and K is a
constant fixed later. The individual ceiling Delta^{-0.99}, read
against W_v >= K/2, forces at least (K/2) Delta^{0.99} positive entries
around every survivor, more than its remaining degree at the end; this
is the final greedy step. The floor Delta^{-3} is bookkeeping, removed
by trimming.
Two functionals measure a round. The edge mass and the potential are
D_v = sum_{u in N_{G'}(v)} D_vu , D_vu = sum over forbidden
pairs (i,l), i in L(v), l in L(u), of w_i w_l ,
F_v = sum_{i in L(v)} w_* f(w_i/w_*) + gamma log Delta (K - W_v)
+ D_v ,
where G' is the uncolored graph, f(a) = a log a - a + 1 with f(0) = 1,
w_* = K/k, gamma = 0.003, and k is the final list size. The entropy
sum and the linear term keep W_v from drifting down; D_v falls when
neighbors are colored and pays for the round. The method is the
entropy-compression scheme of Johansson as presented by Bansal, Gupta
and Guruganesh.
sources/bansal-gupta-guruganesh.pdf
A round activates each entry with probability proportional to its
weight and promotes an activated entry to a color when none of its
neighbors in H activates; a chosen color deletes all entries forbidden
with it. Three difficulties shape the construction.
Triangles. Compensating individual weight losses to first order works
along edges but fails around triangles: three mutually adjacent entries
touched together create a positive second-order term, which at entry i
totals t_i = w_i sum_{j in N_H(i)} w_j sum_{z in N_H(i) cap N_H(j)} w_z,
twice the triangle mass through i. Distinct entries are hurt by
distinct amounts, so the fix must be per-entry: edits whose averaged
contribution offsets t_i at every entry at once, at a cost of a bounded
multiple B of the edge mass d_i = w_i s_i. A local adjustment lemma
supplies multipliers (scale nearby weights around 1) and drops (delete
one weight and charge its edges), packed as vectors g_i with rates a_j
so that
t_i + sum_j a_j g_i^{(j)} <= B d_i and
sum_{j : i in J_j} a_j <= Lambda^4
at every entry.
Participation. An edit of small radius in H can still touch many
entries of a single list L(v), which would make that list's weight a
sum of quantities moving together and spoil concentration. The
adjustment lemma therefore confines each edit to a ball of radius R_0
and to at most P_0 entries of any part; at Lambda = 20 log Delta this
gives R_0 = O(log log Delta) and P_0 = Delta^{o(1)}.
Concentration. After a round, entries of one list are dependent. A
read-k tail bound controls sums of bounded functions of independent
inputs when each input influences few summands, and the participation
bound makes each adjustment input influence few entries of a list. A
local lemma then makes all per-vertex estimates hold simultaneously.
The finish uses tau = Delta^{-0.10}. Each valid round cuts the
remaining degree by a factor (1 - tau) plus a small error, so after
T_* = ceil(2 tau^{-1} log Delta) rounds the remaining maximum degree is
at most Delta^{-1} + Delta^{0.96}, far below the (K/2) Delta^{0.99}
available entries. Each colored neighbor in the final greedy pass
forbids at most one entry, by the matching condition, so a choice
always survives and the coloring completes.
The core is a local statement about a weighted K_r-free graph carrying a
partition. Fix r >= 4, let H be a finite K_r-free graph, and let a
partition of V(H) be such that every vertex has at most one neighbor in
each part. Give every vertex i a positive weight w_i and set
s_i = sum_{u in N_H(i)} w_u , d_i = w_i s_i ,
t_i = w_i sum_{u in N_H(i)} w_u sum_{z in N_H(u) cap N_H(i)} w_z .
Thus d_i is the mass of edges out of i and t_i is twice the mass of
triangles through i. Assume s_i <= Lambda for every i, with Lambda >= 1,
and set
ell_0 = log(8 Lambda) , R_0 = ceil(4 ell_0) + 10 ,
U = exp(A ell_0^2) , P_0 = ceil(exp(40 ell_0^2)) ,
where A = A(r) > 0 is chosen later. A multiplier operation is a
nonempty listed support J lying in a ball of radius R_0 in H and
meeting each part in at most P_0 vertices, together with multipliers
m_i in [0, U] for i in J; extend m_i = 1 off J and set
g_i = w_i f(m_i) + sum_{u in N_H(i)} w_i w_u (m_i - 1)(m_u - 1) .
A drop operation at i has listed support {i} and vector
g_i = Lambda w_i - d_i , g_u = -w_i w_u (u in N_H(i)) ,
g_u = 0 (u not in N_H(i) union {i}) .
Adjustment lemma. For every integer r >= 4 there are constants A, B
and Lambda_r, depending only on r, such that whenever Lambda >= Lambda_r,
the graph H, its partition, and weights with s_i <= Lambda admit a
finite family of multiplier and drop operations with vectors g^{(j)},
listed supports J_j and rates a_j >= 0 so that for every vertex i
t_i + sum_j a_j g_i^{(j)} <= B d_i , (V)
sum_{j : i in J_j} a_j <= Lambda^4 . (R)
The first ineuality offsets the triangle cost to within a bounded
multiple of the edge mass; the second caps the total rate of edits
touching any vertex, which lets the participation bound take effect in
the coloring rounds. Taking every part a singleton makes the partition
condition automatic, so the lemma also covers an arbitrary positively
weighted K_r-free graph; the partition appears only because the
participation bound (R) speaks of parts.
The shape of the vectors is forced by a first-order computation. Fix
multipliers m_i, extended by 1 off a set J, and a small rho > 0; with
probability rho multiply every weight by m_i, otherwise multiply by
(1 - rho m_i)/(1 - rho), so that each weight keeps mean 1. The entropy
sum sum_i (w_i log w_i - w_i) then changes, to first order, by
rho w_i f(m_i) at i, and the edge sum sum_{iu} w_i w_u changes on edge
iu by rho w_i w_u (m_i - 1)(m_u - 1). So g_i is the coefficient of rho
in the change of "entropy at i plus edge mass out of i". The edit the
coloring actually wants is an activation of z with probability
proportional to w_z together with deletion of the weights on N_H(z) and
a mean-restoring compensation; to first order this changes the entropy
at i by rho d_i and the incident edge mass by rho t_i. The d_i part is
harmless, but the t_i part is a positive correlation that must be
removed, and the lemma says the multiplier and drop edits absorb it up
to B d_i, uniformly in i.
The lemma is proved in two moves: duality reduces it to one scalar
triangle estimate, and a vertex-splitting argument proves that estimate.
Begin with duality. Attach a nonnegative price x_i to each vertex
ineuality (V) and a price w_i y_i, with y_i >= 0, to each rate
ineuality (R). The target is the pair of statements that the point
(B d - t, Lambda^4 1) lies in the cone generated by the columns
(g^{(j)}, 1_{J_j}) together with the nonnegative orthant, the rates
being the coefficients. That cone is closed and convex. By separation,
the target holds if and only if every nonnegative price vector orthogonal
to the cone satisfies it, that is:
if sum_i x_i g_i + sum_{i in J} w_i y_i >= 0 for every allowed
operation (g, J), (DT)
then sum_i x_i t_i <= B sum_i x_i d_i + Lambda^4 sum_i w_i y_i . (DTG)
This is the dual form. Everything to follow assumes prices obeying the
dual test (DT) and aims to prove (DTG).
Apply (DT) to the drop at i. Its vector gives g_i = Lambda w_i - d_i
and g_u = -w_i w_u on N_H(i), so the first sum equals
Lambda w_i x_i - x_i d_i - w_i sum_{u in N_H(i)} x_u w_u, and the second
adds w_i y_i. Dividing by w_i > 0 and using d_i = w_i s_i yields the
drop test
sum_{u in N_H(i)} x_u w_u <= (Lambda - s_i) x_i + y_i
<= Lambda x_i + y_i . (DROP)
This is the only use of the drop operations.
Call a vertex good if x_i > y_i, and bad otherwise. A triangle
{i, u, z} contributes 2(x_i + x_u + x_z) w_i w_u w_z to the total
sum_v x_v t_v, because t_v weights each incident triangle by 2. For a
bad vertex i the contributions of triangles through i sum to at most
2 w_i ( x_i s_i^2 + s_i sum_{u in N_H(i)} x_u w_u )
<= O(Lambda^2) w_i y_i ,
using (DROP), x_i <= y_i, and s_i <= Lambda. Summing over bad vertices,
with overcounting allowed, gives
sum over triangles meeting a bad vertex of
2 (x_i + x_u + x_z) w_i w_u w_z <= O(Lambda^2) sum_i w_i y_i . (BAD)
The triangles left have only good vertices. Their budget is the priced
edge mass
M_x = sum_i x_i d_i = sum_{iu in E(H)} (x_i + x_u) w_i w_u ,
the edge sum being unordered.
The good-triangle sum is organized by dyadic price levels. Each good
vertex has its price x_i in a unique half-open interval [b, 2b) with b a
power of two; call that b the level of i. At a level b call a good
vertex low if x_i < b, middle if b <= x_i < 2b, and high if x_i >= 2b.
Build H_b from the good vertices by deleting every edge with two low
endpoints and every edge with two high endpoints, and rescale weights by
q_i = w_i x_i / b (i high) , q_i = w_i (i low or middle) .
All three classifications refer to the level under consideration.
A triangle of good vertices survives as a triangle of H_b at exactly one
level, the level of its median price. There it has at most one low and
at most one high vertex, hence at least one middle vertex. At every
other level two of its vertices are low or two are high, and the edge
between them is deleted. The rescaling pays the largest price even when
that price dwarfs the median: if x_i < b <= x_u < 2b <= x_z, then
b q_i q_u q_z = x_z w_i w_u w_z .
A retained triangle with no high vertex has all three prices below 2b,
and one with a high vertex carries that largest price divided by b; in
either case
2 (x_i + x_u + x_z) w_i w_u w_z <= 12 b q_i q_u q_z .
With
T_0 = sum_b b sum over triangles {i,u,z} of H_b of q_i q_u q_z ,
the surviving-triangle ineuality and (BAD) combine to
sum_i x_i t_i <= 12 T_0 + O(Lambda^2) sum_i w_i y_i .
Hence a bound T_0 = O_r(M_x) proves (DTG) once B and the lower
threshold on Lambda are chosen, and the duality move is reduced to that
triangle bound.
It remains to translate the prices into coefficients on the rescaled
weights at a fixed level b. For a good vertex i and an original edge
iu with both ends good, set
alpha_i = x_i w_i / (b q_i) ,
beta_i = y_i w_i / (b q_i) ,
kappa_iu = (x_i + x_u) w_i w_u / (b q_i q_u) .
These are the prices per unit of rescaled weight, and they obey
0 <= beta_i < alpha_i <= 2 , 0 < kappa_iu <= 4 ,
kappa_iu >= 1 for every edge iu of H_b . (KOEF)
The bound on alpha: a high vertex has alpha_i = 1, a low or middle
vertex has alpha_i = x_i/b, which is below 2 and, for a good vertex,
positive; and beta_i < alpha_i is just goodness. For kappa: if exactly
one endpoint is high, kappa is 1 plus the ratio of the other price to the
high price, between 1 and 2; if both are high, kappa = b/x_i + b/x_u <= 2;
if neither is high, kappa = (x_i + x_u)/b <= 4, and a retained edge of
this last type has a middle endpoint, giving kappa >= 1.
Apply (DT) to a multiplier operation supported on good vertices and
divide by b. Since (m_i - 1)(m_u - 1) = 0 unless both endpoints move,
this gives the normalized dual ineuality
0 <= sum_{i good} alpha_i q_i f(m_i)
+ sum_{iu in E(H), i,u good} kappa_iu q_i q_u
(m_i - 1)(m_u - 1)
+ sum_{i in J} beta_i q_i . (NDT)
It holds for every multiplier operation on good vertices. The edge sum
here runs over all original edges of H, including edges absent from H_b;
the deletions in H_b only reduce the triangle count, and the estimates
below account for the missing edges. Finally, the rescaling keeps a
uniform neighborhood bound: for every good vertex i,
sum_{u in N_{H_b}(i)} q_u <= e^{ell_0} = 8 Lambda . (NBHD)
A high vertex has every retained neighbor with q-weight at most its
original w-weight, so the sum is at most s_i <= Lambda. A non-high
vertex has high neighbors of total q-weight at most
(1/b) sum_{u in N_H(i)} x_u w_u <= (Lambda x_i + y_i)/b < 2(Lambda + 1)
by (DROP) and goodness, and non-high neighbors of total weight at most
Lambda.
The first tool is the weighted sparse-subgraph device of Ajtai, Erdos,
Komlos and Szemeredi. For weights q on a graph, write q(S) = sum_{i in
S} q_i and let sum_{iu} q_i q_u denote the unordered edge sum over
present edges.
Sparse multipliers. For every integer r >= 2 there is a constant
D_r >= 1 with the following property. Let F be a finite K_r-free graph
with positive vertex weights q_i of total mass s = sum_i q_i. For every
0 < epsilon <= 1/2 there are jointly distributed random multipliers n_i
with
0 <= n_i <= D_r epsilon^{-(r-2)} , E n_i = 1 ,
E [ sum_{iu in E(F)} q_i q_u n_i n_u ] <= epsilon s^2 . (SM)
Proof. If F is empty the claim is void; assume s > 0 and induct on r.
For r = 2, K_2-free means no edge, so the edge sum is 0 and n_i = 1
works. For r >= 3 keep s fixed. Repeatedly remove the open
neighborhood in the current remainder of a vertex whose neighborhood
mass exceeds epsilon s/4, until none remains. The removed sets are
disjoint, each induces a K_{r-1}-free graph (a K_{r-1} there together
with the removed vertex would be a K_r in F), and each has mass s_j >
epsilon s/4. In the final remainder every neighborhood has mass at most
epsilon s/4, so summing neighborhood masses over vertices and halving
bounds the remainder's edge mass by (1/2) s (epsilon s/4) = epsilon s^2/8.
If nothing was removed, n_i = 1 gives (SM).
Otherwise select the remainder with probability 1/2 and removed set j
with probability p_j = s_j/(2 sum_l s_l) > epsilon/8. Set the
multipliers to 0 off the selected set, use the constant 2 on the
remainder, and on a selected removed set use the inductive multipliers
for epsilon/4 divided by p_j. Every mean is 1: the remainder gives
(1/2) 2, a removed set gives p_j (1/p_j). On a removed set the bound is
D_{r-1} (epsilon/4)^{-(r-3)} / p_j <= 8 4^{r-3} D_{r-1}
epsilon^{-(r-2)}, so a constant D_r bounds all multipliers. Edges
between distinct sets contribute 0. The remainder contributes at most
4 epsilon s^2/8 = epsilon s^2/2 before selection, hence epsilon s^2/4 in
expectation; the removed sets contribute at most
sum_j (epsilon/4) s_j^2 / p_j = (epsilon/2)(sum_j s_j)^2 <= (epsilon/2) s^2.
Their sum is at most epsilon s^2, proving (SM).
https://doi.org/10.1007/BF02579451
For subsets S, D of a weighted graph, define the directed edge mass
e_q(S, D) = sum_{i in S} sum_{u in D cap N(i)} q_i q_u .
An edge with both ends in S cap D is counted twice. A subscript names
the graph when several are in play.
The sparse multipliers give the key local estimate under the dual
condition.
Local cross estimate. Assume the prices satisfy (DT) and fix a level b.
Let S, D be subsets of V(H_b) such that S union D lies in a ball of
radius R_0 in H and meets every part in at most P_0 vertices. Suppose
32 <= h <= 20 ell_0^2 , q(S) <= e^h , q(D) <= e^h ,
0 <= eta <= 2 , and alpha_i <= eta, beta_i <= eta for i in S .
If A is large enough depending only on r, then
e_{q,H_b}(S, D) <= C_1 ( eta h q(S) + e^{-3h} ) , (CROSS)
with C_1 = C_1(r).
Proof. First take S and D disjoint and nonempty. Apply the sparse
multipliers to the induced graph H[S] with its q-weights and
epsilon = e^{-16h}, obtaining mean-one n_i on S with
E [ sum over edges iu inside S of q_i q_u n_i n_u ] <= e^{-16h} q(S)^2 .
Set k' = e^{8h} and consider the multiplier operation with support S
union D and multipliers m_i = 1 + k' n_i on S, m_i = 0 on D. By the
hypotheses on S union D this is an allowed operation provided every
multiplier is at most U. On S, log m_i = log(1 + k' n_i) <=
log(1 + k' D_r e^{16h(r-2)}) <= C'_r h, and since h <= 20 ell_0^2 a
choice of A >= 20 C'_r gives log m_i <= A ell_0^2 = log U. Hence every
realization is allowed. Write s = q(S) and d = q(D).
For every realization (NDT) holds, so it holds after expectation. On S,
using f(1 + a) <= a log(1 + a),
E sum_{i in S} alpha_i q_i f(m_i)
<= eta sum_{i in S} q_i E[ k' n_i log(1 + k' n_i) ]
<= C'_r eta h k' s .
On D, m_i = 0, so f(m_i) = 1 and the entropy coordinate alpha_i q_i and
the support coordinate beta_i q_i are both at most 2 q_i, giving at most
4d; the support on S is at most eta s. The expected quadratic term is
at most
4 (k')^2 e^{-16h} s^2 + 2 d^2 - k' e_{q}(S, D) ,
the four pieces being: edges inside S, of total 4 (k')^2 e^{-16h} s^2 by
the sparse multipliers and kappa <= 4; edges inside D, bounded by
2 d^2 since the unordered edge mass inside D is at most d^2/2 and
kappa <= 4; retained edges between S and D, whose product is
(k' n_i)(-1) and whose expected contribution is -k' e_q(S, D) up to
sign; and deleted cross edges plus edges leaving S union D, which
contribute at most 0. Since the tested ineuality holds for every
realization,
k' e_q(S, D) <= C'_r eta h k' s + eta s + 4d
+ 4 (k')^2 e^{-16h} s^2 + 2 d^2 .
Divide by k' = e^{8h}. As (k')^2 e^{-16h}/k' = e^{-8h}, and s, d <= e^h
with eta <= 2, the non-leading terms are at most
6 e^{-7h} + 6 e^{-6h}, so
e_q(S, D) <= C'_r eta h s + O(e^{-6h}) ,
which is (CROSS) for disjoint S and D. If either set is empty, both
sides are 0 or the bound is immediate.
For overlapping S and D, assign each vertex of S union D independently
to a left or a right class with probability 1/2, and apply the disjoint
estimate to the left part of S and the right part of D. Each directed
edge of e_q(S, D) survives with probability 1/4, and the expected mass
of the left part of S is q(S)/2. Thus (1/4) e_q(S, D) <=
C_1 ( eta h q(S)/2 + e^{-3h} ), and raising C_1 gives (CROSS) in
general.
The local estimate is used on graphs obtained from the H_b by splitting
vertices, so it must survive a homomorphism. A homomorphism p from a
graph F into H_b is injective on directed edges if the map
(u, v) -> (p(u), p(v)) is injective on ordered adjacent pairs. Vertices
of F may then have several preimages, which become the copies, but each
directed edge of H_b has at most one preimage. Give every vertex of F
the weight, price, coefficients and part of its image.
Transfer. Let p: F -> H_b be injective on directed edges, with
inherited data. Then every vertex of F has at most one neighbor in
each inherited part, and (CROSS) holds in F for any S, D obeying the
mass and coefficient hypotheses, provided S union D lies in a ball of
radius R_0 in F and meets each inherited part in at most P_0 vertices.
Proof. Directed-edge injectivity gives
e_{q,F}(S, D) <= e_{q,H_b}(p(S), p(D)) ,
q(p(S)) <= q(S) , q(p(D)) <= q(D) ,
since distinct directed edges of F have distinct images. The projected
union lies in a ball of radius R_0 in H and meets each part in at most
P_0 vertices, and the coefficient bounds pass to images, so the local
cross estimate (which allows overlap) gives (CROSS) in F. For the part
condition, two distinct neighbors of a vertex x of F have distinct
images, since otherwise two directed edges would agree; those images lie
in the neighborhood of p(x) in H_b, and at most one lies in any one part.
Hence at most one neighbor of x lies in any inherited part.
Triangle bound. T_0 = O_r(M_x).
The triangle mass is driven down by splitting vertices until every
neighborhood weight is small, while almost all triangle mass is kept.
Throughout, a graph at level b carries a homomorphism into H_b that is
injective on directed edges, and its vertices inherit weight q, prices,
parts, and low/middle/high labels. Deleting vertices or edges preserves
this, and the splitting is built to preserve it as well. Let F_b be the
current graph at level b, initially H_b, and set
T = sum_b b sum over triangles {a,u,v} of F_b of q_a q_u q_v .
Initially T = T_0, and T falls as the F_b are edited.
Middle-vertex charge. At every stage,
sum_b b sum_{a middle in F_b} q_a q(N_{F_b}(a)) <= 2 M_x . (MID)
An original edge au contributes b q_a q_u to the left exactly when a is
middle at that level, and b q_a q_u is at most its contribution to M_x,
since kappa >= 1 on the image edge. An original vertex is middle at
exactly one level, and a directed edge at a level has at most one
preimage, so each original edge is charged at most once from each end.
By (NBHD) every neighborhood weight is at most e^{ell_0} to begin with,
and 32 <= ell <= ell_0 is a running parameter. A first clean-up removes
cheap vertices. Delete, at every level, each vertex whose price is
below ell^{-4} b. Fix a middle vertex a before the deletion, put
D = N_{F_b}(a), and let S be the vertices of D being deleted. Then
S union D = D lies in a ball of radius one and meets each part at most
once, with q(S), q(D) <= e^ell and alpha, beta <= ell^{-4} on S, so the
local cross estimate with h = ell gives
e_q(S, D) <= C_1 ( ell^{-3} q(D) + e^{-3ell} ) .
When q(D) > ell^{-2} the exponential is absorbed by q(D)/ell^2, and when
q(D) <= ell^{-2} one uses e_q(S, D) <= q(D)^2 <= q(D)/ell^2; in both
cases e_q(S, D) = O_r(q(D)/ell^2). A deleted triangle has a middle
vertex a, which is not deleted because its price exceeds b, and an edge
from S to D inside N(a); multiplying by b q_a and summing over middle a
bounds the triangle mass lost by
(1/ell^2) sum_b b sum_{a middle} q_a q(N(a)) = O_r(M_x / ell^2)
by (MID). After deleting also any edge whose two endpoints fail to
keep a common neighborhood of weight at least ell^{-1}, which removes no
middle-vertex charge and costs O_r(M_x/ell^2) more, each retained edge
iu has c_{uv} = q(N(u) cap N(v)) >= ell^{-1} for its image vertices.
A graph F is prepared at level b with parameter ell when 32 <= ell <=
ell_0, it carries a homomorphism into H_b injective on directed edges,
every vertex weight is at most e^ell, every neighborhood weight lies in
[ell^{-1}, e^ell], every retained edge has both endpoints' shared
neighborhood of weight at least ell^{-1}, and every vertex has at most
one neighbor in each part. Deleting vertices or edges keeps all of this
except possibly the lower bounds, which the clean-up has secured; the
splitting below keeps them as well.
Splitting lemma. There is C_2 = C_2(r) with the following property.
Let F be prepared at level b with parameter ell and triangle mass t.
Then there is a prepared graph F'' at the same level b, with a
homomorphism into F injective on directed edges, in which every vertex is
a copy of a vertex of F of the same weight q, such that
every neighborhood weight in F'' is at most e^{sqrt ell} , (SP1)
the triangle mass t'' of F'' satisfies
t'' >= t (1 - C_2 log ell / sqrt ell) . (SP2)
The splitting is proved by choosing, inside each neighborhood, random
labels whose laws are guided by a short random walk. Throughout F is
prepared at level b with parameter ell, and t is its triangle mass.
Inside N(u) define the transition kernels
P_u(v, z) = 1_{vz in E(F)} q_z / c_{uv} ,
Q_u = (I + P_u)/2 , K_u^{(j)} = P_u Q_u^{j} (j >= 0) ,
where c_{uv} = q(N(u) cap N(v)) >= ell^{-1}. The kernel P_u is
reversible with stationary law pi_u, since
pi_u(v) P_u(v, z) = q_v q_z 1_{vz in E(F)} / h_u is symmetric in v, z;
the same holds for Q_u and K_u^{(j)}. Writing K_u^{(j)} = Q_u^{j} P_u
and using c_{uv} >= ell^{-1} gives the density bound
K_u^{(j)}(v, z) <= ell q_z . (DENS)
Because N(u) can have very many vertices even when its total weight is
small, entropy is measured relative to q: for a probability row p on a
finite set with positive weights q, put
H_q(p) = sum_{z : p(z) > 0} p(z) log( q_z / p(z) ) .
Jensen gives H_q(p) <= log q(support of p). Set
H_j = E_{(u,v) ~ mu} H_q( K_u^{(j)}(v, .) ) , R = ceil(ell) .
The density bound gives H_j >= -log ell.
Walk-entropy lemma. With these definitions,
H_0 >= -log ell , and H_R <= O_r(log ell) . (ENT)
The proof splits the row K_u^{(R)}(v, .) according to membership in the
set D_j of vertices reachable within j steps. For every u in N(v) and
0 <= j <= R,
K_u^{(j)}(v, N(u) ∖ D_j) <= j ell^{-4} . (LEAK)
At j = 0 the row is supported on N(u) cap N(v) = D_0. For the step, a
vertex z outside D_{j+1} is reached from D_j only through an
off-diagonal step of Q_u, of size at most ell q_y ell q_z; since every
admitted vertex carries a prescribed positive neighbor weight theta,
summing over such z gives at most ell^2 q_z theta = q_z ell^{-4}
e^{-ell}, and q(N(u)) <= e^ell turns this into at most ell^{-4}. The
mass arriving from outside D_j is at most the previous leakage, giving
(LEAK).
Define the exceptional set J_v = { u in N(v) : q(N(u) cap D_R) > ell^8 }.
Applying the local cross estimate to N(v) and D_R with h = 20 ell^2 and
eta = 2, admissible because both lie in a ball of radius R + 1 <= R_0
and meet each part once, and using S_v = q(N(v)) >= ell^{-1}, absorbs
the exponential and gives
q(J_v) <= O_r(ell^{-6} S_v) .
A second use, on J_v and N(v) with h = ell, converts this into the
conditional law of the triangle measure, which weights u by c_{uv}:
P_mu(u in J_v | v) = e_q(J_v, N(v)) / h_v <= O_r(ell^{-4}) . (EXC)
For u not in J_v the row K_u^{(R)}(v, .) splits into a part inside D_R,
of support weight at most ell^8, and a part outside, of mass at most
R ell^{-4} by (LEAK) and support weight at most e^ell; the entropy of
this mixture is at most log 2 + 8 log ell + (R ell^{-4}) ell. For
u in J_v the crude bound ell suffices, and (EXC) shows these u carry
probability O_r(ell^{-4}). Averaging over u then v gives (ENT).
Since K_u^{(j+1)} = Q_u K_u^{(j)}, its row at v is the mixture of the
rows K_u^{(j)}(z, .) with z distributed as Q_u(v, .). The entropy of a
mixture minus the average entropy of its constituents is the average of
their divergences from the mixture, and the log q_z terms cancel;
averaging over mu and using that pi_u is stationary for Q_u to identify
the average constituent entropy as H_j gives
H_{j+1} - H_j
= E KL( K_u^{(j)}(z, .) || K_u^{(j+1)}(v, .) ) >= 0 ,
the expectation over (u,v) ~ mu and z ~ Q_u(v, .). With (ENT),
telescoping over the R steps yields some 0 <= j < R with
H_{j+1} - H_j <= O_r(log ell / ell). Fix such j and write
K_u = K_u^{(j)}. Using K_u^{(j+1)}(v, .) as an intermediary in the
triangle ineuality for total variation,
E_{mu, z ~ P_u(v, .)} TV( K_u(v, .), K_u(z, .) )
<= 2 sqrt( H_{j+1} - H_j ) <= O_r( sqrt( log ell / ell ) ) . (ROW)
The factor two: the two expected distances to the intermediary sum to
twice the expected distance from the z-row taken under
Q_u = (I + P_u)/2, after which KL >= TV^2 and Cauchy-Schwarz apply.
A simultaneous coupling assigns to all incidences at u labels with the
prescribed marginals while keeping nearby labels close. Take one shared
sequence of independent proposals, each a uniformly chosen label with an
independent uniform mark, and let each law accept the first proposal
whose mark is below its probability of that label. Two laws at total
variation distance d then produce the same label except with probability
at most 2d/(1+d) <= 2d. Applying this to the rows of K_u and using (ROW)
bounds the average probability that the labels disagree at a triangle
corner by the right side of (ROW).
sources/angel-spinka.pdf
Call an incidence (u, v) with label y = Y_uv qualified when
K_u(y, v) >= q_v e^{-sqrt ell}. To bound failures, sample (u, v) ~ mu
and y ~ K_u(v, .); the joint law of (v, y) is pi_u(v) K_u(v, y), which
is symmetric by reversibility, and after exchanging v and y the reverse
entry is positive almost surely. Hence
E log( q_v / K_u(y, v) ) = E log( q_y / K_u(v, y) ) = H_j <= H_R .
Each logarithm is at least -log ell by (DENS), and Markov applied to
log ell + log(q_v / K_u(y, v)) gives
P( (u,v) unqualified ) <= (H_j + log ell)/(sqrt ell + log ell)
<= O_r( log ell / sqrt ell ) . (FAILQ)
For each u create one copy (u, y) for each y in N(u), of weight q_u.
Join (u, Y_uv) to (v, Y_vu) exactly when both incidences are qualified;
each old edge yields at most one new edge, endpoints project to distinct
vertices, and the result is a simple graph. A copy (u, y) has
neighborhood weight at most
sum_{v in N(u), Y_uv = y, uv kept} q_v
<= e^{sqrt ell} sum_{v in N(u)} K_u(y, v) = e^{sqrt ell} ,
the row summing to 1. This is (SP1).
An old triangle {u, v, z} survives with its mass q_u q_v q_z exactly
when all six incidences are qualified and the two labels agree at each
of its three corners. In the ordered triangle law each incidence has
law mu and each corner has the law used above, so a union bound over six
incidences, each unqualified with probability O_r(log ell/sqrt ell), and
three corners, each disagreeing with average probability
O_r(sqrt(log ell/ell)), bounds the expected fraction of triangle mass
lost by
O_r( log ell/sqrt ell + sqrt(log ell/ell) )
= O_r( log ell / sqrt ell ) . (SP2)
Choose the couplings to lose at most this expectation. The projection
to F is a homomorphism injective on directed edges, and composing with
the map to H_b keeps that property; all weights and inherited data are
unchanged. This proves the splitting lemma.
The splitting is iterated. One application replaces the parameter ell by
sqrt ell and keeps a fraction 1 - C_2 log ell / sqrt ell of the triangle
mass. Starting from ell_0 and repeating, the parameter reaches 32 in
finitely many steps, and because the ell values form a geometric
sequence in the exponent (each is the square of the next), the sum of
log ell / sqrt ell over the steps is bounded by a constant depending only
on r, namely the last few terms log 32 / sqrt 32 and log 1024 / 32 plus
smaller ones. The product of the retention factors is therefore at
least a constant 1/C_3, and the triangle mass T is carried to a graph in
which every neighborhood weight is at most e^{32}.
At that final stage every triangle still has a middle vertex: a triangle
of F_b projects to a triangle of H_b with distinct vertices, which has a
middle vertex, and the label is inherited. The mass of triangles through
a middle vertex a at level b is at most (1/2) q_a q(N(a))^2, so with
every neighborhood weight at most e^{ell} it is at most
(1/2) e^{ell} q_a q(N(a)). Hence
T_final <= (1/2) e^{ell} sum_b b sum_{a middle} q_a q(N(a))
<= e^{ell} M_x <= e^{32} M_x
by (MID). Since T_final >= (1/C_3) T_0, this gives T_0 <= C_3 e^{32}
M_x = O_r(M_x). The triangle bound holds.
Completing the adjustment lemma: by the triangle bound the contribution
to sum_i x_i t_i from triangles with only good vertices is O_r(M_x), and
by (BAD) the contribution from triangles meeting a bad vertex is at most
O(Lambda^2) sum_i w_i y_i. Choosing B = B(r) large and then raising the
threshold Lambda_r so that Lambda^2 is swallowed by Lambda^4, the dual
target becomes
sum_i x_i t_i <= B sum_i x_i d_i + Lambda^4 sum_i w_i y_i ,
which is (DTG). The separation argument now supplies the finite family
of multiplier and drop operations with rates obeying (V) and (R). The
constants are chosen in order: first A and C_1 from the local estimate,
then the reduction constants and C_2, then B, and finally the threshold
Lambda_r so that the O(Lambda^2) bad-vertex term lies under Lambda^4.
Each depends only on r.
The adjustment lemma converts entry weights into a controlled random
update. A partial correspondence coloring is extended in small
randomized rounds; the scheme is Johansson's entropy compression, adapted
so that the participation bound (R) supplies the concentration that
independence would supply in list coloring.
sources/bansal-gupta-guruganesh.pdf
Fix
K = 16(B+2) , gamma = 0.003 , C = 100K/gamma ,
k = ceil( C Delta / log Delta ) ,
with B from the adjustment lemma; restrict each list to exactly k entries
and keep the notation L(v). For large Delta, k <= Delta. Set
w_* = K/k , Lambda = 20 log Delta , tau = Delta^{-0.10} ,
xi = Delta^{-0.14} , zeta = Delta^{-0.15} .
The parameter tau sets activation and adjustment rates, xi is the
permitted error per round, and zeta is a smaller tolerance.
A round starts from entry weights obeying
Delta^{-3} <= w_i <= Delta^{-0.99} , s_i <= Lambda , (WB)
and, at each uncolored v, K/2 <= W_v <= 2K. The potentials F_v, W_v,
D_v are those defined above on the uncolored graph G'.
The update uses two independent families of Bernoulli flags. Each entry
z has an activation flag, set with probability tau w_z, which touches
every neighbor of z in H and pins its multiplier to 0. Each operation j
has an operation flag, set with probability tau a_j, which touches J_j; a
multiplier operation applies m_i^{(j)} on J_j, and a drop applies 0 on
its singleton support. The probabilities are valid because every rate
a_j <= Lambda^4.
For each i put bar w_i = w_i Y_i. If exactly one set flag touches i,
Y_i is its designated multiplier; if at least two touch i, Y_i = 0; if
none touches i,
Y_i = 1 + tau ( s_i + sum_{j in M} a_j (1 - m_i^{(j)}) ) , (NOFLAG)
where M indexes the multiplier operations, with multipliers extended by
1 off their supports, and zero-weight entries stay zero. The coefficient
of tau in (NOFLAG) has absolute value at most Lambda + Lambda^4 (1+U), so
Y_i is positive and equals 1 + O(tau Delta^{o(1)}). The compensation in
(NOFLAG) cancels the first-order mean loss from activations and
multipliers.
Expected change. For the random update,
E bar W_v <= W_v + o(xi) ,
E bar F_v <= F_v + tau (B+1) D_v + o(xi) ,
E bar D_vu >= (1/2) D_vu for every vu in E(G') . (EXP)
Proof. Let a_i^- be the total rate of the drop operations at i.
Expanding over the set flags touching one entry or two entries, with il
an edge of H in the last line,
E(Y_i - 1) = -tau a_i^- + O(tau^2 Delta^{o(1)}) , (M1)
E f(Y_i) = tau ( s_i + a_i^- + sum_{j in M} a_j f(m_i^{(j)}) )
+ O(tau^2 Delta^{o(1)}) , (M2)
E[(Y_i - 1)(Y_l - 1)]
= tau sum_{z in N_H(i) cap N_H(l)} w_z
+ tau sum_{j in M} a_j (m_i^{(j)} - 1)(m_l^{(j)} - 1)
+ O(tau^2 Delta^{o(1)}) . (M3)
The total probability that some flag touches either of two fixed entries
is at most 2 tau (Lambda + Lambda^4), and independence bounds both the
probability of two or more such flags and the accumulated error by
O(tau^2 Delta^{o(1)}), all multipliers and their f-values being
Delta^{o(1)}. For (M1): the single flags touching i contribute
-s_i - a_i^- + sum_j a_j (m_i^{(j)} - 1), while the no-flag value
(NOFLAG) contributes +s_i + sum_j a_j (1 - m_i^{(j)}); these cancel to
-a_i^-. For (M2): f(0) = 1 at the entries pinned to 0, and f(1+h) =
O(h^2) at the no-flag value 1 + O(tau Delta^{o(1)}). For (M3): to first
order only flags touching both entries matter, namely activations at a
common neighbor z, which pin both to 0 and give (Y_i - 1)(Y_l - 1) = 1,
and shared multiplier flags; a singleton drop touches one end only, and a
flag touching one end picks up an extra factor O(tau Delta^{o(1)}).
The entropy identity, valid for every i including Y_i = 0, is
w_*[ f(w_i Y_i/w_*) - f(w_i/w_*) ]
= w_i log(w_i/w_*) (Y_i - 1) + w_i f(Y_i) .
Thus the contribution of i in L(v) to the change of F_v is
w_i[ (log(w_i/w_*) - gamma log Delta)(Y_i - 1) + f(Y_i) ]
+ sum_{l in N_H(i)} w_i w_l (Y_i Y_l - 1) , (ENTRY)
with expectation at most
tau ( d_i + t_i + sum_j a_j g_i^{(j)} )
+ O((w_i + d_i) tau^2 Delta^{o(1)}) . (EENTRY)
For a multiplier operation the compensated linear terms and the log
terms cancel, leaving w_i f(m_i^{(j)}) and the quadratic edge term,
which together are tau g_i^{(j)}. A drop at i contributes
w_i(1 - log(w_i/w_*) + gamma log Delta) <= Lambda w_i to the non-edge
part and -d_i to the edge part, matching the drop vector, and a drop at a
neighbor l contributes -w_i w_l. Finally |log(w_i/w_*)| = O(log Delta)
by (WB), which gives the error in (EENTRY).
Summing (EENTRY) over i in L(v) and using (V) gives
E bar F_v <= F_v + tau (B+1) D_v + o(xi), because D_v <= Lambda W_v and
W_v <= 2K make the error o(xi). The mass bound follows from (M1):
E bar W_v - W_v = -tau sum_{i in L(v)} w_i a_i^- + O(k tau^2 Delta^{o(1)})
<= o(xi), as a_i^- >= 0 and k <= Delta. For the edge bound, fix an edge
il in the sum defining D_vu: with probability 1 - O(tau Delta^{o(1)})
neither endpoint is touched, and then Y_i Y_l = 1 + O(tau Delta^{o(1)}),
while otherwise w_i w_l Y_i Y_l >= 0; hence E(w_i w_l Y_i Y_l) >=
w_i w_l/2, and summing over i in L(v), l in L(u) gives
E bar D_vu >= (1/2) D_vu.
The random flags make different entry weights dependent, so a tail bound
for sums of functions of independent inputs, each input reaching few
summands, replaces the sum of independent variables.
Concentration lemma. Let X_1, ..., X_m be bounded real functions of
finitely many independent inputs. Suppose each X_j has range of length
at most b_j, and each input is used by at most p of the functions, with
p >= 1. If sum_j b_j^2 > 0, then for every a > 0,
P( sum_j (X_j - E X_j) >= a ) and
P( sum_j (X_j - E X_j) <= -a ) <= exp( -2 a^2 / (p sum_j b_j^2) ) .
(CONC)
If sum_j b_j^2 = 0, both probabilities are 0.
sources/gavinsky-readk.pdf
Proof. For nonnegative bounded functions Z_j with these dependence
sets, the generalized Holder ineuality
E prod_j Z_j <= prod_j ( E Z_j^p )^{1/p} (HOLD)
follows by induction on the number of inputs. Condition on all inputs
but the last, and let I index the at most p functions that use the last
input. Apply Holder's ineuality with exponent p to the factors in I,
and the induction hypothesis elsewhere. If a random variable X has
range of length b, then
log E e^{s (X - E X)} <= s^2 b^2 / 8 for all real s , (HOEV)
since the second derivative of the logarithm is the variance under the
exponentially tilted law, at most b^2/4, and the logarithm and its
derivative vanish at 0. Applying (HOLD) to Z_j = e^{s(X_j - E X_j)}
and then (HOEV) with parameter p s gives
E exp( s sum_j (X_j - E X_j) ) <= exp( p s^2 sum_j b_j^2 / 8 ) .
Exponential Markov's ineuality with s = 4a/(p sum_j b_j^2) proves the
upper tail, and replacing X_j by -X_j proves the lower tail.
https://doi.org/10.1214/aop/1176989534
https://doi.org/10.1080/01621459.1963.10500830
Apply the concentration lemma to bar W_v and to the non-edge part
bar F_v - bar D_v of the potential. Apart from an additive constant,
each is a sum of at most k <= Delta functions, one for each entry of
L(v), and each single function has range length at most
Delta^{-0.99+o(1)}. This follows from (WB), (NOFLAG), and
U = Delta^{o(1)}; the logarithmic factors in the entropy term are
absorbed in Delta^{o(1)}. It also covers arbitrarily small positive
provisional weights, because with 0 log 0 = 0 one has
sup over 0 <= z <= b of |z log z| = b log(1/b), small when b is small.
Now count how many of these functions each input influences. A
multiplier flag occurs in at most P_0 of them, by its support bound
within a single part; a drop flag occurs in at most one, and an
activation flag occurs in at most one, because its activating entry has
at most one neighbor in L(v), by the matching condition. Thus p = P_0
is valid. Hence each requirement
bar W_v <= E bar W_v + zeta ,
bar F_v - bar D_v <= E( bar F_v - bar D_v ) + zeta (VERT)
fails with probability at most exp(-Delta^{0.5}) for large Delta: the
exponent in (CONC) is at least Delta^{0.68-o(1)}, since a single range
length is at most Delta^{-0.99+o(1)} and there are at most Delta of them
with participation P_0 = Delta^{o(1)}.
For each edge vu of G' the edge term bar D_vu is concentrated on its
own. Index the forbidden pairs (i, l) by i in L(v); each i has at most
one partner l in L(u), so bar D_vu is a sum of at most k products
w_i w_l Y_i Y_l, each of range length O(Delta^{-1.98+o(1)}) because
w_i, w_l <= Delta^{-0.99} and every multiplier is Delta^{o(1)}. A
multiplier flag j touches only products indexed by i in J_j or whose
partner lies in J_j, at most 2 P_0 of them, since J_j meets each part in
at most P_0 entries; activation and drop flags touch at most one
product. Thus p = 2 P_0 is valid, and (CONC) with a = zeta fails with
probability at most exp(-Delta^{2.5-o(1)}).
Combining (EXP), (VERT), and these matching bounds, outside an event of
probability at most exp(-Delta^{0.5}) the provisional weights obey
bar W_v <= W_v + o(xi) ,
bar F_v <= F_v + tau (B+1) D_v + o(xi) ,
bar D_vu >= (1/2) D_vu for every vu in E(G') . (PROV)
To pay for the potential increase tau(B+1) D_v, enough neighbors must
receive colors, measured both by D_vu and by 1/Delta. Fix v in G' and
choose one of the two coefficient families
b_u = D_vu (u in N_{G'}(v)) , or b_u = 1/Delta . (COEF)
Both obey 0 <= b_u <= 2K Delta^{-0.99}: the first because the matching
condition gives D_vu <= Delta^{-0.99} W_v, the second immediately.
Let A_u indicate that some entry at u activates. The A_u are
independent over distinct hosts, and P(A_u = 1) >= 1 - e^{-tau W_u} >=
tau K/4 since K/2 <= W_u <= 2K. Applying (CONC) with p = 1 and
sum_u b_u^2 <= 4K^2 Delta^{-0.98},
sum_{u in N_{G'}(v)} b_u A_u
>= (tau K/4) sum_{u in N_{G'}(v)} b_u - zeta (ACTMASS)
except with probability at most exp(-Delta^{0.5}).
The loss comes from collisions: a host with an activating entry but no
successful entry receives no color. Let E_v be the set of edges of H
with an endpoint hosted at a neighbor of v, and let X_v count the edges
of E_v whose two endpoints both activate.
Collision bound.
P( 4K Delta^{-0.99} X_v > zeta )
<= O(Delta^3) e^{e-1-Delta^{0.01}} + e^{-Delta^{0.8}} . (COLLTAIL)
For either family in (COEF), the sum of b_u over hosts u counted by A_u
that receive no color is at most 4K Delta^{-0.99} X_v.
Proof. A host with an activating entry but no successful entry contains
an endpoint of an edge counted by X_v: its activating entry has an
activating neighbor, and that neighbor is joined to it by an edge of E_v.
Each edge of E_v has at most two hosts and each coefficient is at most
2K Delta^{-0.99}, giving the last assertion. For the tail, first
mu_v := E X_v <= tau^2 sum_{u in N_{G'}(v)} sum_{i in L(u)} w_i s_i
<= 2K Delta tau^2 Lambda = Delta^{0.80+o(1)} , (MUV)
since sum_i w_i s_i <= Lambda W_u <= 2K Lambda and there are at most
Delta neighbors. For a possible endpoint i, the number of its
activating neighbors is a sum of independent indicators of mean
tau s_i <= tau Lambda <= 1, whose exponential moment at 1 is at most
exp(e-1), so it exceeds Delta^{0.01} with probability at most
exp(e-1-Delta^{0.01}). A union bound over O(Delta^3) endpoints shows
that, apart from the first term of (COLLTAIL), the edges counted by X_v
form a graph of maximum degree at most Delta^{0.01}.
When 4K Delta^{-0.99} X_v > zeta holds, X_v > Delta^{0.84}/(4K), and a
maximal matching in a graph of maximum degree Delta^{0.01} has at least
X_v/(2 Delta^{0.01}) >= m = ceil(Delta^{0.82}) edges. With
q_e = tau^2 w_i w_l for e = il in E_v, the events that both endpoints of
an edge activate are independent along a matching, so
P( some size-m matching in E_v has all endpoints activating )
<= sum_{M matching, |M| = m} prod_{e in M} q_e
<= ( sum_{e in E_v} q_e )^m / m!
= mu_v^m / m! <= ( e mu_v / m )^m <= e^{-Delta^{0.8}} . (MATCHTAIL)
The second ineuality expands the m-th power, in which each matching
appears m! times and all other terms are nonnegative. Together with the
first term this proves (COLLTAIL).