THE SHARP TERMINAL LEAVE IN RANDOM TRIANGLE REMOVAL
a complete proof, written for a curious high school student
ABSTRACT
Start with the complete graph on n vertices. Repeatedly pick a triangle
uniformly at random among all triangles whose three sides are still
present, and delete its three sides. Stop when no triangle remains.
The remaining edges form a graph called the leave; let F_n be its
number of edges.
Main theorem. As n -> infinity,
E[(F_n / n^(3/2) - 1/(2 sqrt 2))^2] -> 0.
In particular, F_n / n^(3/2) -> 1/(2 sqrt 2) in probability, and
E[F_n] / n^(3/2) -> 1/(2 sqrt 2).
This is the triangle case of a sharp-constant conjecture of Joos and
Kuhn (2025). The proof below is self-contained except for one input:
a standard "early prefix" estimate from their paper, which is stated
and specialized in Step 1.
CONTENTS
0. How to read this proof
1. What we are proving, and where 1/(2 sqrt 2) comes from
2. The whole proof at a glance
3. Notation and conventions
4. Step 1: a clean early prefix
5. Step 2: priorities turn removal into a scan
6. Step 3: exact survival tests
7. Step 4: independent occurrences (the unfolding)
8. Step 5: solving the recursion for survival probabilities
9. Step 6: stability, or why every edge type behaves alike
10. Step 7: coupling finite and independent scans
11. Step 8: repeated triangle types (witnesses)
12. Step 9: from survival probabilities to moments
13. Conclusion: the sharp constant, proved
0. HOW TO READ THIS PROOF
Mathematics proofs are read like a detective story: some parts you
follow closely, others you skim once and revisit when needed. The
parts of this proof have unequal difficulty.
If you want just the shape of the argument, read sections 1 and 2.
That is eleven pages of intuition distilled into eleven paragraphs,
and every later section only adds precision.
If you want the ordinary mathematics, read sections 4-8 and 12-13,
skipping the "stability" section 9 on a first pass. That is 95 percent
of the intellectual content; section 9 is a technical lemma that makes
one nearby estimate uniform, and its only job is to justify a "~"
sign that would otherwise be unjustified.
If you want everything, read it all. There are no local shortcuts; each
section states exactly what it uses from the sections before, and the
final theorem depends on the sum of all previous steps.
One warning about notation. Random variables are written F_n, D, m,
N_u, etc. Probabilities are written P(...) or P_this(...); expectations
are written E[...]. Every random variable, when sampled, gets a
lowercase "realised" value only if we forget that it is allowed to be
random; but for readability we treat the process as already run, once,
and describe what we see. "With high probability" (often abbreviated
w.h.p.) means: the failure event has probability at most n^(-C) for
every fixed C > 0, once n is large enough.
The proof strategy is "the priority scan", introduced in section 5.
Every later step transforms the survival probability of one edge under
the priority scan and eventually obtains it in closed form. The final
paragraph of section 12 turns those per-edge probabilities into moments
of F_n.
1. WHAT WE ARE PROVING, AND WHERE 1/(2 sqrt 2) COMES FROM
1.1 The process.
Start with the complete graph K_n : n vertices, every pair joined by
an edge, giving n(n-1)/2 edges.
A triangle is three edges among three vertices, forming a cycle. The
removal process runs like this:
(i) list every triangle whose three edges are all still present;
(ii) choose one uniformly at random;
(iii) delete its three edges.
Repeat until no triangle remains. At every step, we use a fresh uniform
choice among whatever triangles survive at that moment.
When the process stops, no triangle is left. The surviving edges lie
in a triangle-free graph called the terminal graph or the leave. Let
F_n be the number of its edges. F_n is a random integer between 0 and
n(n-1)/2, and the theorem pins down F_n / n^(3/2).
1.2 Why the size of the leave is around n^(3/2).
Each removed triangle kills exactly three edges. Early on every edge
is in n-2 triangles, and almost any sampled triangle is available. In
the first few steps, edges disappear with density still near 1.
Near the end, "density" is a fragile concept. A triangle needs three
mutually adjacent edges; the surviving edges are like a sparse random
graph with m edges. Random graph theory says the expected number of
triangles in a truly random m-edge graph is about (2m/n)^3 * n^3 / 6,
which is zero once m is far below n^(4/3). But that is only a heuristic:
greedy removal keeps the surviving edges strongly correlated, so the
real leave is much larger than the random-graph guess.
Solid theory pinned the scale. Spencer (1995) and Rodl--Thoma (1996)
showed the leave is o(n^2); Grable (1997) refined this to n^(7/4+eps);
Bohman--Frieze--Lubetzky (2015) proved F_n = n^(3/2+o(1)). The present
proof upgrades that "o(1)" to the exact constant 1/(2 sqrt 2).
1.3 Why the constant is 1/(2 sqrt 2).
Suppose the graph currently has m edges and density p = 2m / n^2. An
edge e shares a triangle with one edge for each common neighbor of
its two endpoints. On average, that count is
D = n p^2.
D is the number of triangles through any given edge.
Introduce a random ordering of the triangles. Give every triangle T
an independent uniform priority U_T in [0,1]. Scan priorities in
increasing order, accepting T exactly when its three edges are still
present. This is exactly the same as random greedy removal -- we will
prove that carefully in Section 5. Say an edge e is "untouched before
t" if no accepted triangle of priority below t contains e.
Let q(t) be the probability (in a certain approximation to the greedy
process) that a given edge e is untouched before t. Here is the
heuristic that finds q in closed form. Through e there are D triangles.
For one specific triangle T with priority v < t, the other two edges of
T must both survive up to time v; each of those has probability about
q(v). So the probability that e is killed by some triangle before t
behaves like
(chance T has priority in [v, v+dv]) x q(v)^2 x (number of T's)
= D x (dv) x q(v)^2.
Accumulating from 0 to t,
q(t) = 1 - D x int_0^t q(v)^2 dv,
q'(t) = - D q(t)^3, q(0) = 1.
Solve:
q(t) = (1 + 2 D t)^(-1/2).
At t = 1 (all triangles examined) the surviving fraction is
q(1) = (1 + 2 D)^(-1/2).
The number of surviving edges at the terminal moment is therefore
about
m x q(1) = (n^2 p / 2) x (1 + 2 D)^(-1/2).
On the scale p = n^(-1/2 + eps) with D = n p^2 = n^(2 eps), we have
D -> infinity slowly, so q(1) is asymptotic to (2 D)^(-1/2), and
m q(1) ~ (n^2 p / 2) x (2 n p^2)^(-1/2)
= n^(3/2) / (2 sqrt 2).
That is the claimed constant. All the work that follows makes the
"~" signs rigorous. The final section upgrades a single-edge convergence
in probability into an L^2 statement, which controls both the probability
and the expectation of F_n / n^(3/2).
2. THE WHOLE PROOF AT A GLANCE
The removal process runs from K_n all the way down to a triangle-free
graph. That is too big a range for one set of estimates. So we split
it in two.
The first half is a prefix: run the process down to edge density
p = n^(-1/2 + eps), where eps > 0 is a small fixed number. On that
range, a battery of concentration estimates from Joos--Kuhn (2025) gives
strong pseudorandom properties: uniform degrees, uniform codegrees,
uniform small-subgraph counts, and clean link structures. This is the
only input we use from outside; we restate the properties and specialize
them in section 4.
The second half is the continuation: from a graph G that satisfies
those properties, all the way down to the terminal leave. Our argument
lives entirely here. Its seven pieces, one per section, produce the
sharp constant.
Step 1 (section 4). State the pseudorandom properties of G. The
essential one: about D = n p^2 triangles through every edge, uniformly.
Also uniform degrees, uniform codegrees, and clean counts for small
rooted subgraphs.
Step 2 (section 5). Priorities. Give each triangle of G an independent
uniform priority in [0,1]. Scan priorities in increasing order,
accepting a triangle exactly when its three edges are still present.
This scan has the same law as random greedy removal. (The "priority
lemma" is a one-line exchange argument.)
Step 3 (section 6). Exact survival test. Whether an edge e survives
the entire scan is a well-defined event. It can be decided recursively.
An edge e survives at threshold t iff no accepted triangle through e
has priority below t. A triangle S with priority U_S < t is accepted
precisely when its two other edges both survive at threshold U_S. This
gives us a boolean recursion; it terminates because priorities strictly
decrease along each branch.
Step 4 (section 7). Independence. The finite graph G repeats triangle
types. A chain of recursive calls can pass through the same triangle
type many times, which would make the priorities artificially tied.
We fix this by "unfolding": give each *occurrence* of a triangle in the
recursion its own independent priority. Occurrences in different
ancestor chains become independent. The auxiliary model is a tree of
occurrences, and its survival probabilities satisfy exact product
identities:
q_e(t) = prod over triangles S through e of (1 - I_{e,S}(t)),
q_{e,T}(t) = prod over triangles S through e, S not equal to T,
of (1 - I_{e,S}(t)),
I_{e,S}(t) = int_0^t q_{f,S}(v) q_{g,S}(v) dv,
where f and g are the other two edges of S, and q_{.,T} means "with T
omitted from the candidate list at the root".
Step 5 (section 8). Solving the recursion. The scalar comparison
q(t) = (1 + 2 D t)^(-1/2) solves q'(t) = - D q(t)^3. Define
z_e(s) = log(q_e(t(s))/q(t(s))) with s = (1/2) log(1+2 D t).
The recursion becomes
z'(s) = - (A/D) z(s) + O( n^(-2 a) + n^(-c) + log(n)/D ),
where A is the edge-adjacency matrix of G (A_ef = 1 iff e, f share a
triangle) and a > 0 is a fixed small number. Uniform control of z(s)
for s in [0, log n] then gives q_e(t) = (1 + o(1)) q(t).
Step 6 (section 9). Stability. The matrix A has huge operator norm on
R^E, so the naive estimate ||e^(-sA/D)||_inf <= e^(s ||A/D||_inf) is
useless. But e^(-sA/D) is much better behaved than its eigenvalues
suggest, because the graph G's links are expanders. Decompose A/D into
a sum of averaging operators (one per vertex) plus a tiny error R. The
averaging part has an explicit decay of order 1 + 2s in max-norm, and a
finite perturbation expansion absorbs R. Result:
|| e^(-sA/D) ||_inf <= C (1 + log n)^J, for 0 <= s <= log n,
with constants C and J independent of n and G.
Step 7 (section 10). Coupling finite and independent. Up to a "collision"
event, the finite scan and the independent unfolding produce identical
outputs. The collision event is: some triangle type is exposed at two
distinct calls. Then
|P_fin(all roots survive) - P_ind(all roots survive)|
<= P_ind(collision).
Step 8 (section 11). Collision bound. A collision forces an "extra
edge" in the union of at most two ancestral call paths: two formal
vertices a, b are non-adjacent in the formal graph but their labels in
G are adjacent. Bounding such a configuration by (a) counting patterns,
(b) counting embeddings of the union of two paths, (c) bounding the
probability that the required priorities decrease appropriately, gives
P_ind(collision) <= O(D^(-35)) + O(1/n) = o(1/D).
Step 9 (section 12). Moments. Let Y_n = F_n / (m q(1)). The survival
probability identity, averaged over the sampled root edge, gives
E[Y_n | good prefix] = 1 + o(1),
E[Y_n^2 | good prefix] = 1 + o(1),
uniformly over the good prefix. Subtracting, E[(Y_n - 1)^2 | prefix] =
o(1). Meanwhile a_n = m q(1) / n^(3/2) = 1 / (2 sqrt(2 + 1/D)) which
converges to 1/(2 sqrt 2), and the bad-prefix contribution is bounded
by O(n * (failure probability)) = o(1). Combine: E[(F_n/n^(3/2) -
1/(2 sqrt 2))^2] -> 0, which is the main theorem.
That is the shape of the proof. Each of the next sections expands one
step. Do not worry if the notation seems heavy at first: almost every
section is really just two or three lemmas, and the surrounding prose
is there to explain what they mean.
3. NOTATION AND CONVENTIONS
All graphs below are finite and simple (at most one edge between any
two vertices, no loops).
An embedding of a small graph H into a large graph G is an injective
map psi : V(H) -> V(G) that sends every edge of H to an edge of G.
It need not preserve non-edges: two vertices of H that are not adjacent
may be sent to adjacent vertices of G. Embedding counts are ordered: the
labels of H matter. So a labeled copy of a cycle C_j on j vertices has
(v)_j ordered embeddings if G were complete, where (v)_j denotes
v (v-1) (v-2) ... (v-j+1).
Shorthand. "(1 +/- a) b" means any real number x with
(1-a) b <= x <= (1+a) b. We use this to keep growth factors compact.
Density. If G has m edges on n vertices, we write p = 2m / n^2. The
edge-triangle count is D = n p^2, which is the average number of
triangles through an edge.
High probability. "The statement holds C-high" (or "with high
probability") means its failure probability is at most n^(-C) for every
fixed C > 0 once n is large enough. We also write o(1) for any quantity
tending to zero as n -> infinity, at any rate. A "superpolylogarithmic
factor" is (log n)^J for some fixed J.
The two models. "The finite scan" means the priority-driven random
greedy removal process, run on the graph G that we fix in section 4.
"The independent unfolding" means the auxiliary model that gives each
occurrence its own fresh priority; it is constructed in section 7.
Every q_e(t), q_{e,T}(t), I_{e,T}(t) refers to the independent unfolding
unless stated otherwise.
Fixed constants. The proof uses five fixed numerical parameters,
introduced in section 4:
epsilon = 1/2000,
r0 = 8000,
L = 100,
B = 50,
H0 = max(r0 + 1, 3 L + 2) = 8001.
None of these depend on n. Their role:
epsilon selects the prefix density p = n^(-1/2+eps), hence also
D = n p^2 ~ n^(2 eps) -> infinity slowly.
r0 limits the iterated link-cycle lengths used in the
stability estimate (section 9).
L, B control the collision-witness count (section 11).
H0 caps the number of vertices of tracked templates.
Each is used where it enters. We never rely on its numerical value;
only on "sufficiently large" or "sufficiently small".
Asymptotics. f(n) ~ g(n) means f/g -> 1. f = o(g) means f/g -> 0.
f = O(g) means |f| <= C g for a fixed C. Every such symbol refers to
n -> infinity.
Constants. Every constant in the proof may depend on
epsilon, r0, L, B, H0 and the various exponents introduced below. None
may depend on n or on which good prefix we have fixed.
4. STEP 1: A CLEAN EARLY PREFIX
4.1 What this section does.
We pick a deterministic stopping index i0 for the removal process.
The graph G = G_{i0} will be the starting point for the whole
continuation argument. On a "good event" G_n of probability
1 - n^(-omega(1)), G has the following pseudorandom properties:
(i) Uniform degrees and codegrees.
(ii) Uniform link-cycle counts up to length r0.
(iii) Uniform rooted-template counts, in two useful regimes.
(i) says D = n p^2 is essentially the same at every edge. (ii) is the
input to the spectral estimate (section 9). (iii) is the input to the
collision count (section 11).
The statement and its proof take the rest of this section. The proof
is a specialization of stopping estimates from Joos--Kuhn (2025);
we track their parameters so the constants are explicit.
4.2 The stopping time.
Fix a small constant eta > 0 with
eta < epsilon/2, eta^(-4) >= H0,
and small enough that all the auxiliary parameter choices in
Joos--Kuhn (their eta, delta) make their hierarchy valid. All of this
can be arranged because they only need eta and delta sufficiently small.
The density trajectory. Write p_i = 1 - 1/n - 6 i / n^2. Then by
elementary algebra G_i (the graph after i triangle removals, if it
is reached) has expected edge density p_i, because each step removes
three edges.
Set
i0 = floor( (n^2/6) (1 - 1/n - n^(-1/2 + eps)) ).
This is a deterministic integer. At i0:
p_i0 = n^(-1/2 + eps) + O(n^(-2)),
D = n p_i0^2 ~ n^(2 eps),
m = n^2 p_i0 / 2.
The roles: D is the number of triangles through a typical edge. It is
a slowly increasing power of n (in fact D ~ n^(1/1000) with
epsilon = 1/2000), large enough to dominate every polylog but small
enough that log D is bounded by O(log n) with room to spare.
4.3 Templates and scalings.
A template is a pair (H, I) where H is a small graph and I <= V(H) is
an independent set (no edges of H have both endpoints in I). Vertices
in I are "distinguished", the rest are "free".
For an injection psi : I -> [n], the template count
X_{H,I,psi}(G)
is the number of injective edge-preserving extensions of psi to all of
V(H). Equivalently, the number of embeddings of H into G that agree
with psi on I.
The scaling is
S(H,I) = n^(v(H) - |I|) p^(e(H)).
This is what the count would be (up to a factor (1 + O(p n))) if G were
Erdos--Renyi random with edge density p. It is our benchmark.
A "same-root subtemplate" is a subgraph H' of H with I <= V(H'); its
distinguished set is still I.
A template is "balanced" if, for every same-root H', the density of H'
is at most the density of H:
e(H') / (v(H') - |I|) <= e(H) / (v(H) - |I|).
The point: for balanced H, X ~ S to polylog accuracy. The templates we
care about are all balanced. For the few templates that are not, we
use the "general extension bound" in (iii)(B) below.
4.4 The good-prefix proposition.
Proposition 4.1 (Good prefix). There is a constant c > 0 and an event
G_n, measurable from the process up to step i0, with
P(G_n^c) <= exp( -(log n)^(4/3) ) = n^(-omega(1)) (n -> inf).
On G_n, i0 is reached, G = G_{i0} has m edges, and:
(i) Uniform degrees. Every vertex has degree (1 +/- n^(-c)) n p,
and every two distinct vertices have (1 +/- n^(-c)) D common
neighbors.
(ii) Uniform link cycles. For every vertex u and every 3 <= j <= r0,
the number of ordered embeddings of the labeled cycle C_j into
the link graph G[N_G(u)] equals (1 +/- n^(-c)) D^j.
(iii) Uniform template counts. For every template (H, I) with
v(H) <= H0 and every injection psi : I -> [n]:
(A) If S(H', I) >= 1 for every same-root subtemplate H', then
X_{H,I,psi}(G) <= (1 + log n)^(C0) * S(H, I).
(B) If n^(v(H) - |J|) p^(e(H) - e(H[J])) <= 1 holds for every
I <= J <= V(H), then
X_{H,I,psi}(G) <= (1 + log n)^(C0).
Here C0 = 2^(H0 + 1) - 2 is a fixed constant depending only on H0.
Remark. Distinguishing I in the template does not require I to be an
independent set in G; it only requires I to be an independent set in
the template H. That is a formal convenience: it lets us talk about
"prescribed root images" whether or not they have extra edges in G.
4.5 Proof of Proposition 4.1 (specialization of Joos--Kuhn 2025).
The Joos--Kuhn removal process handles a strictly 2-balanced hypergraph
with uniformity parameter k = 2. Triangles are 3-uniform; their
2-density is (3-1)/(3-2) = 2, so they are strictly 2-balanced. All
their hypotheses apply.
Parameters. We already chose eta with eta < epsilon/2 and
eta^(-4) >= H0. Now choose their delta > 0 small enough in terms of
eta, with delta < 1/2. This is a fixed numeric choice; the hierarchy
they require is compatible with taking delta arbitrarily small once
eta is fixed.
K_n is a good start. Their hypotheses (P1)-(P4) demand a specific
level of initial pseudorandomness relative to their error parameters.
For a template with r distinguished vertices, a free vertices, and b
edges not internal to the distinguished set, an injection psi has
exactly (n-r)_a ordered extensions in K_n. Comparing to n^a theta^b
with theta = 1 - 1/n:
(n-r)_a / (n^a theta^b) = 1 + O_eta(n^(-1)).
Their initial relative error parameter is zeta_init = n^delta / (sqrt n
theta). The displayed error is far smaller than both zeta_init and
zeta_init^delta, verifying (P1) and (P2) at t = 0. Their small-scaling
bounds (P3) and (P4) only apply when a >= 1 and the scaling n^a is at
most n^{1/2}; but for a >= 1 the scaling is n^a asymptotically, so
those bounds are vacuous. For a = 0 the counts are 1. Hence K_n is an
(eta^4, delta, 2)-pseudorandom starting graph.
Density trajectory and horizon. In their normalization, the density
at their step i is p_i. Their main horizon is n^{-1/2 + eta}, strictly
below p_{i0} once n is large (because eta < epsilon/2). So we never
exceed their horizon, and every bound in their paper is available.
Balanced-template controls. In their Section 7 they prove: for every
balanced template (H, I) and every injection psi, subject to X being
in the "tracked" regime,
X_{H,I,psi}(G_i) = 1 + O( zeta_i^delta )
times its expectation, where the dynamic error is
zeta_i = n^(eta^2) / (sqrt n p_i)
= n^(eta^2) x_i^(-1/2), x_i := n p_i^2.
"Tracked" means the scaling is at least zeta_i^(-sqrt delta). For a
balanced template with density d <= 2 and a free vertices, the scaling
is at least x_i^a. Throughout i <= i0,
x_i >= n^(2 eps),
x_i^a / zeta_i^(-sqrt delta)
= n^(eta^2 sqrt delta) x_i^(a - sqrt delta/2)
-> infinity.
So none of the templates we track reaches its stopping threshold before
i0. The balanced-template controls are all valid throughout the prefix.
The specific templates. The link-cycle count uses a wheel template
W_j: a distinguished center u and a labeled cycle C_j on the rim,
with a spoke from the center to each rim vertex. It has j free vertices
(rim) and 2j edges total. Any subset of s >= 1 free vertices meets at
most s spokes and s rim edges, so W_j has rooted density at most 2,
matching overall density 2j/j = 2. Thus W_j is balanced. Its extensions
are exactly the labeled C_j link embeddings (walk around the rim, use
spokes to know that each rim vertex is a neighbor of u). The scaling
is D^j. The largest such wheel has r0 + 1 vertices; because
eta^(-4) >= H0 >= r0 + 1, we are within the public size cap.
Degrees come from the rooted edge template (two distinguished
endpoints, no free vertices; density 2, scaling n p). Codegrees come
from the rooted path of length 2 with the two endpoints distinguished
and the middle vertex free (density 2, scaling D).
All three templates are balanced and their scalings are within
tracking range throughout [0, i0]. So on the (public) stopping event,
degree counts are (1 +/- zeta_{i0}^delta) * E[degree],
codegree counts are (1 +/- zeta_{i0}^delta) * E[codegree],
link-cycle counts are (1 +/- zeta_{i0}^delta) * D^j.
At i0, zeta_{i0} <= n^(-(eps - eta^2)). Choose c > 0 with
0 < c < delta * (epsilon - eta^2).
Then all the relative errors above are at most n^(-c) with slack for
the polylog factors. So (i) and (ii) hold on the same event.
General extensions. Joos--Kuhn's general extension bound (their
Lemma 7.15) applies to any template up to their size cap, without
requiring balance. Case (A): if all same-root subtemplate scalings are
bigger than 1, then
X_{H,I,psi}(G) <= (1 + log n)^(alpha_{H,I}) S(H,I),
with alpha_{H,I} = 2^(v(H) - |I| + 1) - 2. Case (B): if every
completion scaling after enlarging the distinguished set is at most 1,
then
X_{H,I,psi}(G) <= (1 + log n)^(alpha_{H,I}).
That is exactly (A) and (B) above with C0 = 2^(H0+1) - 2.
Probability. Joos--Kuhn's Lemma 10.1 (their stopping-time control)
gives that the failure probability of all the above along the prefix
(up to the public horizon) is at most exp(-(log n)^(4/3)). That
establishes the probability claim in Proposition 4.1.
Reaching i0. On the same event, the triangle count stays tightly
concentrated around n^3 p_i^3 / 6 with relative error zeta_i^delta,
along the whole prefix. This quantity is positive at i0, so the
process cannot terminate at or before i0 (termination means zero
triangles). Hence i0 is reached.
Measurability. G_n is defined in terms of the process up to step i0,
which is a finite-information event.
4.6 What we will use from G.
Throughout sections 5-11 we fix an arbitrary G satisfying the
conclusions of Proposition 4.1. All bounds are uniform over such G.
We use the notation:
E the edge set of G, |E| = m,
T the set of triangles of G, each a 3-edge subset of E,
d_e the number of triangles through e, equal to the
common-neighbour count of the endpoints of e,
= (1 +/- n^(-c)) D.
Two distinct triangles of G share at most one edge (simple graph).
That is the one structural fact used everywhere below.
The task now: analyze the random greedy removal process started at G,
and compute E F_n / n^(3/2) and its second moment.
5. STEP 2: PRIORITIES TURN REMOVAL INTO A SCAN
5.1 The idea.
Uniform random greedy removal can be resampled as a deterministic scan
of random priorities. This matters because a scan is "local in time":
the effect of removing triangles can be checked edge-by-edge, using
only the priorities of a small set of triangles. All the later
calculations use that locality.
5.2 The scan.
Give every triangle T of T an independent uniform priority U_T in
[0,1]. Sort the triangles by priority and process them one by one. For
each T, in priority order:
if all three edges of T are still present, accept T and delete
all three; otherwise skip T.
These are the only rules. At the end, no triangle is present: every
accepted triangle has had its edges deleted, and every rejected
triangle had a deleted edge at the moment it was scanned, so it can
never become present again.
We work on the probability-one event that all U_T are distinct.
5.3 "Untouched" edges.
An edge e is "untouched before t" if no accepted triangle with priority
strictly below t contains e.
An edge e survives the whole scan iff e is untouched before t = 1.
(The "strictly below t" convention is needed because we will apply the
notion with t being the priority of a triangle that we know has not yet
been processed.)
5.4 The priority lemma.
Lemma 5.1 (Priority representation). For any finite simple graph G,
the sequence of accepted triangles in the priority scan has the same
distribution as the sequence of chosen triangles in uniform random
greedy removal.
Proof. The priority order is a uniformly random permutation of T.
Conditional on any scanned prefix, the unscanned triangles have uniform
relative order among themselves.
Moreover, every triangle that is currently present is unscanned:
accepted triangles have had their edges deleted, and rejected triangles
are triangles that had a deleted edge at their scan time and can never
be present again. So the set of currently present triangles is a
subset of the unscanned triangles.
Therefore, at the next step, the first currently present triangle in
the remaining order is uniformly distributed among the currently
present triangles. That is exactly the greedy choice of uniform
random triangle removal. QED.
5.5 Applying the lemma at the prefix.
Suppose we stop at i0 with graph G satisfying Proposition 4.1. From
i0 on, the process continues exactly as if we restarted the priority
scan on G with fresh independent priorities U_T, T in T. That is
because the next step of the greedy algorithm depends on the present
graph G, not on how it arose.
So all further analysis (sections 6-13) works on G alone.
6. STEP 3: EXACT SURVIVAL TESTS
6.1 What a call is.
To decide whether an edge is untouched before t, we use a recursive
procedure called a "call". A call has three ingredients:
(i) A focus: one or two edges of G that we want to check are
untouched before the threshold.
(ii) A threshold t in [0, 1].
(iii) A parent triangle (only when the focus has two edges) that
is the triangle through which we reached this call.
There are two kinds:
Root call: focus = { e }, threshold t in [0,1], no parent.
Candidates: all triangles of G that contain e.
Non-root call: focus = { f, g }, contained in a parent triangle T,
threshold t = U_T.
Candidates: all triangles of G that meet the focus, except T.
Between any two edges there is at most one triangle containing both
(simple graph). Between a focus edge e and any triangle S meeting it,
S contains exactly one focus edge. Call that distinguished edge e(S).
(For a two-edge focus {f,g} contained in T, a triangle S containing
both f and g is exactly T, which is excluded from the candidate list.)
6.2 How a call runs.
At a call, do the following.
1. Expose the priorities of all candidates S, in a fixed,
deterministic order of triangle types.
2. Sort the candidates by priority. Consider those with U_S < t,
one by one in increasing priority order. Call them the
"live" candidates.
3. For each live candidate S, compute its child call: focus
S \ { e(S) }, parent S, threshold U_S. Evaluate that child
call.
4. Stop at the first live candidate S whose child returns true
and return false.
5. If every live candidate's child returns false, return true.
Two facts about this test:
(a) It has no side effects. Exposing a priority does not delete
any edge; it only reads the priority.
(b) All calls use the same priority family (U_T)_{T in T}.
Note that "live" candidates are exactly those with priority below the
threshold. All candidates are exposed, live or not, but only live ones
have their children visited. Children of non-live candidates are
ignored.
6.3 The exact-test lemma.
Lemma 6.1 (Exact paired test). For any finite simple graph G with
distinct triangle priorities, the recursive test terminates. Let e be
an edge of G and t in [0,1]. Then:
Root call at (e, t) returns true iff e is untouched before t.
Two-edge call at focus { f, g } in T, threshold U_T, returns
true iff both f and g are untouched before U_T.
(The "if and only if" convention includes the fact that the call
"returns false" exactly when at least one edge of its focus has been
deleted by an accepted triangle of priority strictly below the
threshold.)
Proof.
Termination. Along any recursion path, the threshold strictly
decreases: a child of the call with threshold t has threshold U_S for
some candidate S with U_S < t. Priorities are distinct, so no
triangle type can occur twice along a path (if T appears twice, its
priorities would have to strictly decrease twice, which is impossible).
Hence each path has length at most |T|. Branching is finite (each call
has at most |T| candidates). So the recursion is finite.
Correctness. We prove by induction on the number of triangle priorities
strictly below the call's threshold. All child calls have a strictly
smaller threshold, so the induction hypothesis applies to each of them.
Claim. Some edge of the focus is deleted before t iff some live
candidate S has both edges of S \ { e(S) } untouched before U_S.
Forward direction. Let A be an accepted triangle with U_A < t that
deletes some edge of the focus. A is a candidate at this call (because
it contains a focus edge), and U_A < t, so A is live. Just before U_A
all three edges of A are present, hence the two edges of A \ { e(A) }
are untouched before U_A. (The parent, if any, is at priority t and is
not A, because U_A < t.) So this live candidate satisfies the
condition.
Converse direction. Suppose S is a live candidate with both edges of
S \ { e(S) } untouched before U_S. Then at time U_S every edge of S
is still present: e(S) is a focus edge and we are assuming all focus
edges are untouched before t > U_S. So the scan accepts S, which
deletes e(S) -- a focus edge. Hence some focus edge is deleted before
U_S < t.
Combining the two directions, by induction, the child call for
candidate S returns true exactly when S deletes a focus edge (through
this inductive hypothesis, applied to S's subtree). The test as a
whole therefore returns false exactly when some live candidate has a
successful child, i.e., exactly when some focus edge is deleted before
t. Hence the test returns true iff no focus edge is deleted before t,
which is the survival claim. QED.
6.4 One subtlety: parent omission.
The parent triangle T is omitted from the candidate list of a two-edge
call. Why? Because T's priority is exactly equal to the threshold t.
So T is not "live" (we require U_S < t, strict inequality). Therefore
T would never be processed even if we included it in the candidate
list. Including it would only expose a priority that cannot change the
answer.
The omission is local: it applies only to this call's candidate list,
not to descendant call lists. A descendant may still traverse T
through its descendants (if the parent rule allows it there).
6.5 Summary.
* The finite random greedy removal is a priority scan (Lemma 5.1).
* Whether an edge survives the scan is decided by a bounded-depth
recursion (Lemma 6.1).
* The recursion depends only on the priority family (U_T).
This is the object we now study. Sections 7-11 will compute the
recursion exactly (Section 7) and then estimate its solution (Sections
8-11).
7. STEP 4: INDEPENDENT OCCURRENCES (THE UNFOLDING)
7.1 Why we need a new model.
The finite scan uses the same priority U_T for every call that touches
type T. If T appears many times in a chain of recursion, that same U_T
piles up in many places, making the recursive tests non-independent in
a bad way.
To get clean probability calculations, we build an auxiliary model in
which every occurrence of a triangle has its OWN priority, drawn
independently. Different branches get independent copies. We call this
the "independent unfolding".
The result (Proposition 7.2 below) is a set of exact product equations
for survival probabilities in this unfolding. Sections 8-9 solve those
equations; section 10 relates them back to the finite scan.
7.2 Call trees.
Fix a root type: either a singleton edge e, or a two-edge focus { f, g }
contained in a triangle T. Build the deterministic tree of all possible
calls downstream of this root:
a node has ingredients: focus (1 or 2 edges), threshold, parent
triangle (only for non-root nodes);
the children of a node are the candidates S in its list, one per
triangle of G that meets the focus;
the child corresponding to S has focus S \ { e(S) }, parent S,
threshold equal to its own priority variable.
This tree is countable and finitely branching. Each node has at most
2 d_max candidates, where d_max = max_e d_e <= 4 D.
7.3 The independent unfolding.
Assign each child-occurrence an independent uniform variable in [0,1].
This variable serves double duty: it is the candidate's priority in its
parent's list, and (if the child is visited) it is the threshold of the
child's subtree.
Apply the same scan-and-stop rule on the tree:
at a call, sort the children by their priority; visit the live
ones (priority below threshold) in increasing order; stop at the
first child whose subtree returns true and return false; return
true if none do.
The only structural difference from the finite scan is that different
occurrences of the same triangle type now have independent priorities.
Different root queries (root at e1 and root at e2) use disjoint trees
with independent variables.
Singleton root omitting T. We also use a shadow root of the form
focus { e }, T removed from the candidate list at the root,
threshold t.
This only changes the root's own list; descendants still see T like any
other triangle, if their own parent rule allows it.
Two-edge root omitting T. Similarly a root with focus { f, g } in T,
parent T, threshold t; candidates are those meeting {f,g} except T.
These shadow roots are needed for the product equations below.
7.4 Finiteness lemma.
Lemma 7.1 (finite evaluation). For a fixed good graph G, independent
unfoldings can be constructed so that, almost surely, every possible
call at every threshold t in [0,1] has a finite evaluation, and the
outputs are jointly measurable in t and in the occurrence priorities.
Proof. Put M = 2 d_max, so every candidate list has size at most M.
Fix a node of the tree; from that node there are at most M^j descendant
paths of length j.
On a fixed path of length j, the j occurrence priorities are i.i.d.
uniform in [0,1]. The probability that they strictly decrease is
1 / j! (choose j ordered values; only one order of the j! possible
orders is decreasing).
By a union bound, then,
P(a decreasing path of length j from the node) <= M^j / j! -> 0.
The events are decreasing in j. So, almost surely, the depth of any
strictly decreasing path from the node is bounded. Finite branching
then gives a finite evaluation: a visited node's subtree can only
"reach down" through strictly decreasing priorities.
The argument works with threshold 1 and therefore for every smaller
threshold t <= 1. There are only countably many nodes total across all
root types; a countable intersection over all root types gives a
single probability-one set on which every root has a finite evaluation.
Measurability: truncate the recursion at depth j, giving a measurable
function of threshold and finitely many priorities. On the probability-
one event above, these outputs stabilize as j -> infinity for every
threshold. Define arbitrary values on the null exception to complete the
measurability claim. QED.
Remark. We may therefore evaluate any child's subtree hypothetically,
even if the scan chronologically never reaches it. This is used in the
next section to make the joint independence one-to-one.
7.5 The three families of probabilities.
Define, for t in [0,1] and T = { e, f, g } in T:
q_e(t) = P(full singleton root at e, threshold t, returns
true).
q_{e,T}(t) = P(singleton root at e omitting T, threshold t,
returns true).
I_{e,T}(t) = int_0^t q_{f,T}(v) q_{g,T}(v) dv.
The integral is defined by the finiteness lemma (the integrand is
measurable and bounded between 0 and 1). The subscripts will become
clearer in the product identities below.
7.6 Product identities.
Proposition 7.2 (Product identities). For every triangle T = {e, f, g}
in T and every t in [0,1]:
(pair) P(two-edge root at focus {f, g} in T, omitted parent T,
threshold t, returns true)
= q_{f,T}(t) q_{g,T}(t).
(products) q_e(t) = prod_{S in T : e in S} (1 - I_{e,S}(t)),
q_{e,T}(t) = prod_{S in T : e in S, S != T}
(1 - I_{e,S}(t)).
In both products, empty products equal 1. Also:
q_e(0) = q_{e,T}(0) = 1, I_{e,T}(0) = 0,
and the functions q_e, q_{e,T}, I_{e,T} all lie in C^1([0,1]) with
one-sided derivatives at the endpoints.
Proof.
Pair identity. After omitting T, the candidate lists of f and g are
disjoint. Indeed, a triangle containing both f and g would have to be
T itself, and T is omitted.
The occurrence variables in the two lists, and all their descendant
variables, are all independent (the two lists live in disjoint branches
of the tree). So the pair returns true iff every candidate in the
"f"-list fails AND every candidate in the "g"-list fails, independently.
Each side of the split, "every candidate in the list fails to give a
true child below t", has exactly the law of a singleton root with T
omitted. Hence the joint probability factors as q_{f,T}(t) q_{g,T}(t).
(A caution about the chronological order. The pair test scans candidates
in increasing priority order and can be "cut short" if a live child
returns true. But the event "the pair returns true" is precisely "all
children, live or not, fail to return true below t"; that is, every
child on the sorted list whose priority is below t returns false. The
ordering of the scan is irrelevant to this event; only the joint truth
values matter. So we may think of it as the joint event of all children
failing.)
Singleton identity. Consider the singleton root at e, with no parent.
Its candidates are all S in T with e in S. Write e(S) = e for the focus
edge distinguished at the root.
For a candidate S, condition on its own occurrence priority U_S = v.
If v >= t, this candidate is not live and contributes nothing. If
v < t, the child at S is a two-edge call at focus S \ { e } (say
{ f, g }), threshold v, parent (or "omitted") S. By the pair identity
just proved, the probability this child returns true is exactly
q_{f,S}(v) q_{g,S}(v).
Averaging over v uniform on [0,t], the probability S contributes a
true child is
int_0^t q_{f,S}(v) q_{g,S}(v) dv = I_{e,S}(t).
Different candidates S at this root have disjoint occurrence variables
(the branches beneath different S are disjoint in the tree). So the
events "S contributes a true child" are simultaneously independent
across S.
The root returns true iff NO candidate contributes a true child.
Taking the probability:
q_e(t) = prod_{S : e in S} (1 - I_{e,S}(t)).
The q_{e,T} identity is identical, except the candidate S = T is
omitted from the product.
Smoothness. Base case t = 0: nothing can be killed "before t = 0"
(strict inequality is empty), so every q_e(0), q_{e,T}(0) equals 1 and
every I_{e,T}(0) equals 0.
Measurability and continuity: each I_{e,T} is an integral of a bounded
measurable function, hence continuous. Each q is a finite product of
(1 - I), hence continuous. Substituting back, the integrand is
continuous, so each I is C^1. Substituting once more, each q is C^1.
One-sided derivatives at 0 and 1 make sense from the one-sided
integrals. QED.
7.7 What these identities mean, and what they do not mean.
The product identities describe the auxiliary independent unfolding
exactly. They are NOT identities for the finite priority scan on G. In
the finite scan, the same U_T appears in many places, so the
factorization across different branches breaks down. Section 10
(coupling) will bound the error.
The four functions above -- q_e, q_{e,T}, I_{e,T}, and the scalar
comparison q(t) to be introduced next -- are the objects we study for
the rest of the proof.
7.8 One extra observation.
For fixed priorities, the child call at S returns true iff no live
child of S returns true. So for a fixed priority family, "S returns
true" is monotone in S's threshold: making the threshold larger only
makes it harder for the call to be "true" (since more candidates become
live). This monotonicity is useful to see q_e(t) is nonincreasing in t;
we will not use it directly but it is worth remembering.
8. STEP 5: SOLVING THE RECURSION
8.1 What we want to show.
Uniformly over the good graph G, over t in [0,1], and over every edge
e:
q_e(t) = (1 + o(1)) q(t),
q_{e,T}(t) = (1 + o(1)) q(t),
I_{e,T}(t) = O(log n / D),
where q(t) = (1 + 2 D t)^(-1/2) is the scalar comparison introduced in
section 1.
The tactic is: define the ratio q_e/q via a logarithm, derive an
exact ODE for it, linearize around zero, and prove a bootstrap estimate
using section 9's semigroup bound on e^{-sA/D}.
8.2 The scalar comparison.
Define, on [0, 1],
q(t) = (1 + 2 D t)^(-1/2).
Then q(0) = 1, and direct differentiation gives
q'(t) = - D q(t)^3, q'(0) = -D.
We will show q_e and q_{e,T} track q uniformly.
8.3 The time change.
Set
s = (1/2) log(1 + 2 D t), S = (1/2) log(1 + 2 D).
t(s) = (e^{2s} - 1) / (2 D).
Then q(t(s)) = e^{-s}, so s = -log q. And
dt/ds = e^{2s} / D = (1 + 2 D t) / D = 1 / (D q(t)^2).
The variable s is essentially "log-time": 0 corresponds to t = 0,
s = S to t = 1, and S <= log n once n is large (since D <= n^{1/500}).
The advantage: q becomes exactly e^{-s} in the s variable, which makes
products and sums of q's much simpler to bound.
8.4 The z-variable.
Define for each edge e of G:
z_e(s) = log( q_e(t(s)) / q(t(s)) ), s in [0, S].
Then z_e(0) = log(1/1) = 0. If |z_e(s)| is small, then q_e(t(s)) is
close to q(t(s)). So we want to prove ||z(s)||_inf -> 0.
8.5 The adjacency matrix.
Let A be the m-by-m symmetric real matrix with entries
A_{ef} = 1 if e != f and e, f lie in a common triangle of G,
A_{ef} = 0 otherwise.
Each row sum is 2 d_e = (1 +/- n^{-c}) 2 D, by the good-prefix codegree
estimate. In particular ||A||_inf = 2 D (1 + n^{-c}).
The matrix A is the edge-adjacency matrix of the triangle hypergraph.
8.6 Differentiating the products.
Fix an edge e and t = t(s). Take log of the product identity:
log q_e(t) = sum_{S : e in S} log(1 - I_{e,S}(t)).
Differentiating in t:
(q_e'/q_e)(t) = - sum_{S : e in S} I'_{e,S}(t) / (1 - I_{e,S}(t)).
Now I'_{e,S}(t) = q_{f,S}(t) q_{g,S}(t) where S = {e, f, g}. And for
the same triangle S, the singleton root at f omits S from its product,
so
q_{f,S}(t) = q_f(t) / (1 - I_{f,S}(t)),
q_{g,S}(t) = q_g(t) / (1 - I_{g,S}(t)).
So
I'_{e,S}(t) = q_f(t) q_g(t) / [ (1 - I_{f,S}(t)) (1 - I_{g,S}(t)) ].
Substituting back,
(q_e'/q_e)(t) = - sum_{S : e in S}
q_f(t) q_g(t) / [ (1 - I_{e,S}) (1 - I_{f,S}) (1 - I_{g,S}) ](t).
Now translate to s. Since q_e(t(s)) = q(t(s)) e^{z_e(s)}, we have
d/ds log q_e(t(s)) = -1 + z_e'(s),
d/ds log q_e(t(s)) = (dt/ds) * (q_e'/q_e)(t(s))
= (1/(D q(t(s))^2)) * (q_e'/q_e)(t(s)).
Putting these together,
z_e'(s) = 1 - (1/D) sum_{S : e in S}
e^{z_f(s) + z_g(s)} / [ (1 - I_{e,S}) (1 - I_{f,S}) (1 - I_{g,S}) ],
where t = t(s) in each I factor. This is the exact ODE identity.
8.7 Linearization.
Bootstrap assumptions. Suppose on some interval [0, s_0) with s_0 <= S:
(B1) ||z(s)||_inf <= delta_n := n^{-a},
(B2) I_{e,T}(t(s)) <= 1/2 for every incident pair e in T,
where a > 0 is fixed with a < min(c, 2 eps).
Bound the I's from (B1) and (B2). Since q_f(t(s)) = q e^{z_f} and
q_f = q_{f,T} (1 - I_{f,T}), we have
q_{f,T}(t) = q(t) e^{z_f(s)} / (1 - I_{f,T}(t))
<= q(t) e^{delta_n} / (1 - 1/2)
<= 2 e^{delta_n} q(t).
So q_{f,T}(t) q_{g,T}(t) <= 4 e^{2 delta_n} q(t)^2. Integrate:
I_{e,T}(t) = int_0^t q_{f,T}(v) q_{g,T}(v) dv
<= 4 e^{2 delta_n} int_0^t q(v)^2 dv.
And int_0^t q(v)^2 dv = int_0^{s(t)} q^2 * (1/(D q^2)) ds
= s(t) / D <= S/D <= (log n)/D.
So
I_{e,T}(t) = O( log n / D ). (*)
For large n this is far below 1/2, so (B2) is improvable.
Bound each summand in the ODE. Write a_s = e^{z_f(s) + z_g(s)} and
b_s = (1 - I_{e,S})(1 - I_{f,S})(1 - I_{g,S}). With (B1)-(B2),
|z_f|, |z_g| <= delta_n and each I factor is O(log n/D), so
a_s / b_s = (1 + z_f + z_g + O(delta_n^2)) (1 + O(log n / D))
= 1 + z_f + z_g + O(delta_n^2 + log n / D).
Summing over S : e in S, d_e = (1 +/- n^{-c}) D terms:
sum_S a_s / b_s
= d_e + (Az)_e + d_e * O(delta_n^2 + log n / D)
= d_e + (Az)_e + O(D delta_n^2 + log n).
Dividing by D:
(1/D) sum_S a_s / b_s = (1 + O(n^{-c})) + (1/D)(Az)_e
+ O(delta_n^2 + log n / D).
So in the ODE,
z_e'(s) = 1 - [1 + (Az)_e/D + O(n^{-c} + delta_n^2 + log n/D)]
= - (Az)_e / D + O( n^{-c} + n^{-2a} + log n / D ).
That is, in vector form,
z'(s) + (A/D) z(s) = h(s),
||h(s)||_inf <= C ( n^{-c} + n^{-2a} + log n / D ), (**)
for a fixed constant C, uniformly in s and in the chosen G.
8.8 Bootstrap conclusion.
Variation of constants for the linear ODE with z(0) = 0:
z(s) = int_0^s e^{-(s - v) A/D} h(v) dv.
Take the max norm:
||z(s)||_inf <= int_0^s ||e^{-(s-v)A/D}||_inf * ||h(v)||_inf dv
<= C ( n^{-c} + n^{-2a} + log n / D )
* int_0^s ||e^{-(s-v)A/D}||_inf dv.
Using the semigroup bound of section 9 (to be proved there),
||e^{-uA/D}||_inf <= C_1 (1 + log n)^J for 0 <= u <= log n,
and since s <= S <= log n, we get
||z(s)||_inf <= C' (log n)^{J+1}
( n^{-c} + n^{-2a} + log n / D ).
Now D ~ n^{2 eps} with 2 eps = 1/1000, so
log n / D = o(n^{-a}) for any fixed a < min(c, 2 eps) and any J. Also
n^{-c}, n^{-2a} each equal o(n^{-a}) times any polylog. So
||z(s)||_inf <= C'' * n^{-a} / 2 = delta_n / 2
for large n, uniformly in s in [0, S] and in G.
Bootstrap: if the first time at which (B1) is about to be violated
happened before s = S, the bound above would be strict (delta_n/2 <
delta_n), contradicting that being the first time. Similarly (B2) is
comfortably true. Hence (B1) and (B2) hold throughout [0, S].
It follows that z_e(s) = o(1) uniformly, hence
q_e(t) = q(t) exp(z_e(s)) = (1 + o(1)) q(t),
q_{e,T}(t) = q_e(t) / (1 - I_{e,T}(t)) = (1 + o(1)) q(t),
I_{e,T}(t) = O(log n / D).
That proves Proposition 8.1 below.
8.9 The proposition.
Proposition 8.1 (uniform survival approximation). For every graph G
satisfying Proposition 4.1,
q_e(t) = (1 + o(1)) q(t),
q_{e,T}(t) = (1 + o(1)) q(t),
I_{e,T}(t) = O( log n / D ),
where the o(1) and the O() constant are uniform over G, over
0 <= t <= 1, and over every incident pair e in T. The estimates for
q_e also hold uniformly over all e in E.
All that remains is Proposition 8.8's input: the semigroup bound
||e^{-sA/D}||_inf <= C_1 (1 + log n)^J. That is the subject of the
next section.
9. STEP 6: STABILITY, OR WHY EVERY EDGE TYPE BEHAVES ALIKE
9.1 The problem.
Section 8 needs, for 0 <= s <= log n,
|| e^{-s A/D} ||_inf <= C_1 (1 + log n)^J, (SB)
with C_1 and J independent of n and G.
The naive bound, ||e^{-sA/D}||_inf <= e^{s||A/D||_inf} ~ e^{2s}, is
useless at s ~ log n (it grows like n^2).
What saves us: the matrix A/D is close to a sum of "averaging"
operators on each vertex link, and the averaging part has explicit
max-norm control via the random walk on G. So we do not need any
eigenvalue estimate on A itself; we just need expansion of links.
9.2 The link decomposition.
For each vertex u in [n], let
N_u = deg(u) = (1 +/- n^{-c}) n p,
E_u = set of edges of G incident to u,
M_u = adjacency matrix of the link graph G[N_G(u)] on the index
set E_u.
Identify uv in E_u with v in N_G(u). Then M_u is an N_u x N_u
symmetric matrix with entries 0/1, and every row sum of M_u is the
number of common neighbors of u and v = codegree(u,v) = (1 +/- n^{-c}) D
by Proposition 4.1(i).
Every two distinct edges e, f of G share a triangle iff they share a
unique endpoint u and are both in E_u. So A restricted to the block
E_u x E_u equals (M_u extended by zero outside E_u), and
A = sum_{u in [n]} M_u^(ext), (sum of extended-to-full matrices).
Now, each edge is incident to exactly two vertices, so summing over u
counts each off-diagonal pair (e, f) exactly once (at their common
endpoint) -- no double counting.
9.3 Closed walks in a link.
Fix u and a fixed even integer r = r0 = 8000. Then
tr( M_u^r ) = number of closed walks of length r in the link.
Split according to how many distinct vertices the walk visits.
Case A: all r positions distinct. Such a walk is exactly an embedding of
the labeled cycle C_r into the link. By Proposition 4.1(ii) (the
link-cycle hypothesis), the count is (1 +/- n^{-c}) D^r.
Case B: walk has some repeated position. The support of the walk is a
connected simple graph on <= r - 1 vertices. There are only finitely
many "patterns" of identifications, since r is fixed. For each such
pattern, we bound the number of realizations.
B1: support is a tree.
Every support edge is crossed at least twice by a closed walk (a
walk entering a subtree through that edge must also leave).
So the support has at most r/2 edges. Choose the image of one
vertex (N_u <= 2 np choices) then expose the rest along the tree;
each step has at most maxdeg(link) <= 2D choices. Bound:
<= 2 np * (2D)^{r/2}.
B2: support has a cycle.
Let the support have j < r vertices. Choose a simple cycle in the
support of length b >= 3; by Proposition 4.1(ii) there are
O(D^b) choices for a labeled C_b. Attach the remaining j - b
vertices as a forest rooted at the cycle: at most (2D)^{j - b}
choices. Total: O(D^b * D^{j-b}) = O(D^j) = O(D^{r-1}).
Dividing by D^r, the non-injective walks contribute
O( np D^{-r/2} + D^{-1} ).
Together with the pattern-count factor (finite), the total is
tr( (M_u/D)^r ) = 1 + O( n^{-c} + D^{-1} + np D^{-r/2} ). (tr)
Substituting D = n^{1/1000} and r = 8000: np D^{-r/2} ~ n^{-6999/2000},
utterly negligible. Set
c_* = min(c, 1/1000).
Then tr( (M_u/D)^r ) = 1 + O(n^{-c_*}).
9.4 Eigenvalue separation.
Let B_u = M_u / D. Its row sums are 1 +/- n^{-c}, so:
lambda_1 <= 1 + n^{-c} (row-sum bound), lambda_1 >= 1 - n^{-c}
(Rayleigh quotient with the all-ones vector).
Since r is even,
0 <= sum_{j >= 2} lambda_j^r = tr(B_u^r) - lambda_1^r
= O(n^{-c_*}).
So every nonzero lambda_j with j >= 2 has |lambda_j| <= n^{-c_*/r}
= n^{-gamma}, where
gamma = c_* / r > 0 is a fixed positive constant.
In particular, lambda_1 is simple for large n. And the
spectral projectors onto the leading direction and the all-ones
direction are almost the same.
9.5 Approximating M_u/D by its averaging operator.
Let j_u = (1/sqrt(N_u)) * all-ones in R^{N_u}, and v_u = unit eigenvector
of lambda_1 in B_u.
Step 1: (B_u - Id) j_u. Direct computation: (B_u j_u)_v = (1/sqrt(N_u))
sum_{w in N(u)} [M_u/D]_{v,w} = (1/sqrt(N_u)) * row sum / D = (1 +/-
n^{-c}) * (1/sqrt(N_u)). So B_u j_u differs from j_u by at most n^{-c}
in Euclidean norm.
Step 2: write j_u = alpha v_u + w with w perp v_u. Since B_u - Id has
eigenvalues >= 1 - n^{-c_*/r} >= 1/2 on v_u^perp (for large n), the
inverse of (B_u - Id) on that subspace has norm <= 2, giving
||w||_2 <= 2 ||(B_u - Id) j_u||_2 <= 2 n^{-c}.
Step 3: the orthogonal projections onto span(v_u) and span(j_u) differ
in operator norm by at most 2 ||w||_2 <= 4 n^{-c}.
Combining the eigenvalue estimate and projector approximation,
|| M_u/D - (1/N_u) J_u ||_2 = O(n^{-gamma}), (star)
where J_u = (all-ones) (all-ones)^T is the N_u x N_u matrix.
9.6 The averaging part P and the error R.
Extend every (1/N_u) J_u by zero to the full edge space R^E, and let
P = sum_u (1/N_u) J_u^(ext), R = A/D - P.
Euclidean bound on R. For x in R^E:
|x^T R x| <= sum_u |x|_u^T (M_u/D - J_u/N_u) |x|_u
<= C n^{-gamma} sum_u ||x|_u||_2^2
= 2 C n^{-gamma} ||x||_2^2.
The final equality: each edge lies in exactly two links (its two
endpoints). So sum_u ||x|_u||_2^2 = 2 ||x||_2^2 (Euclidean, off-diagonal
counts twice, each edge contributed by 2 vertices, giving 2x).
So ||R||_2 = O(n^{-gamma}).
Infinity norm on R. Row sum of A/D is 2 d_e / D = 2 (1 +/- n^{-c}).
Row sum of P at edge e=(a,b) is (1/N_a) + (1/N_b) = 2 (1 +/-
n^{-c}). Both matrices have nonnegative entries, so their max-norm
difference is bounded by the max of absolute row sums, i.e. O(1):
||R||_inf = O(1).
9.7 The averaging semigroup e^{-sP} in max norm.
The special form of P makes e^{-sP} small in max norm. Write
U : R^n -> R^E, (Uy)_{uv} = y_u + y_v,
V : R^E -> R^n, (Vx)_u = (1/N_u) sum_{e in E_u} x_e.
Then P = UV. Also VU = Id + W, where W is the nearest-neighbor
random-walk matrix on G: (Wy)_u = (1/N_u) sum_{v in N(u)} y_v.
Since W has nonnegative entries and row sums 1, ||W||_inf = 1.
For j >= 1, (UV)^j = U (VU)^{j-1} V = U T^{j-1} V with T = Id + W.
Summing the exponential power series,
e^{-sP} = Id - U ( int_0^s e^{-v T} dv ) V.
Sanity check: differentiating under the integral gives
d/ds [Id - U int_0^s e^{-vT} dv V] = -U e^{-sT} V, and using
T int_0^s e^{-vT} dv = Id - e^{-sT}, this equals -P e^{-sP}. Good.
Bound: e^{-vT} = e^{-v} e^{-vW}, so ||e^{-vT}||_inf <= e^{-v} e^{v||W||_inf}
= e^{-v} * e^v = 1. Hence
||int_0^s e^{-vT} dv||_inf <= int_0^s e^{-v} dv <= 1.
Also ||U||_inf = 2 (each row of U has two 1's) and ||V||_inf = 1 (each
row of V is a 1/N_u-weighted sum of entries, entries nonnegative with
total weight 1). So
|| e^{-sP} ||_inf <= 1 + 2 * 1 * 1 = 3. (P-semigroup)
(Any bound of the form (1 + 2s) or 3 will do; we will need only a
factor that stays bounded.)
9.8 The perturbation expansion.
Decompose A/D = P + R. Iterate the variation-of-constants identity
e^{-s(A/D)} = e^{-sP} - int_0^s e^{-(s-v)P} R e^{-v A/D} dv
K - 1 times to obtain a finite expansion in powers of R:
e^{-sA/D} = sum_{j=0}^{K-1} (term_j) + R_K(s),
where:
term_j is a j-fold iterated integral over an ordered simplex of
volume s^j/j!, with j copies of R, bounded in max norm by
(1 + 2 s)^{j+1} ||R||_inf^j s^j / j!;
R_K(s) is a K-fold remainder:
R_K(s) = (-1)^K int_{0 <= t_K <= ... <= t_1 <= s}
e^{-(s-t_1)P} R e^{-(t_1-t_2)P} R ... R e^{-t_K A/D}
dt_K ... dt_1,
whose Euclidean norm is bounded by
||R_K(s)||_2 <= ||R||_2^K e^{s ||R||_2} s^K / K!.
Pick an integer K with K gamma > 2. Then the remainder is tiny:
||R_K(s)||_inf <= sqrt(m) ||R_K(s)||_2
<= n * (C n^{-gamma})^K * e^{s * C n^{-gamma}}
* (s^K / K!)
= O( n^{1 - K gamma} (log n)^K )
= o(1),
since s <= log n, e^{s * C n^{-gamma}} -> 1, and 1 - K gamma <= -1.
The j < K initial terms are bounded in max norm by (log n)^{something}.
Each has ||R||_inf = O(1) and length j <= K, so its max norm is at most
a fixed power of (1 + log n). Adding up finitely many such terms, there
are constants C_1 and J depending only on K (hence only on r0 and c):
|| e^{-sA/D} ||_inf <= C_1 (1 + log n)^J,
uniformly in 0 <= s <= log n and in G.
That is (SB). QED.
9.9 Proposition 9.1 (the semigroup bound).
There exist constants C_1, J < infinity depending only on r0 and on the
constant c of Proposition 4.1 such that for every graph G satisfying
Proposition 4.1,
sup_{0 <= s <= log n} || e^{-s A/D} ||_inf <= C_1 (1 + log n)^J.
This theorem, combined with Proposition 8.1, completes the analysis of
the independent unfolding. From here we compare the independent model
to the finite boundary process, in sections 10-11.