A LINEAR CYCLE-AND-EDGE DECOMPOSITION OF EVERY GRAPH
A complete, readable proof for high-school readers
0. THE RESULT IN ONE BREATH
A graph has vertices and edges. An edge joins two vertices. We only
look at finite simple undirected graphs: no loops, no repeated edges,
and edges have no direction.
A cycle is a closed walk that visits no vertex twice except the start
and end, and has length at least three. A single edge is exactly what
it sounds like.
An edge partition of a graph G is a way to write every edge of G in
exactly one part. Different parts may share vertices. They may not
share edges.
THEOREM (main theorem).
There is an absolute constant C > 0 with the following property.
Every finite simple undirected graph G on n vertices has an edge
partition into at most C n parts, where every part is either a simple
cycle or a single edge.
"Absolute constant" means C does not depend on n, on the graph, or on
anything else. This theorem proves the Erdos-Gallai cycle
decomposition conjecture.
Strategy in one paragraph. Induct on n. At a carefully chosen
scale, most edges live in expanding pieces. Small-residue
processing turns each piece into many cycles and single edges,
leaving residuals of tiny total order. Pair folding shrinks a
sparse leftover graph to a quotient of much smaller order, and
routing lifts cycles from the quotient back to simple cycles in
the original graph. The savings from folding pay for the
non-recursive work, and the tiny residuals are handled by
induction.
The bound is best possible up to the value of C. A tree on n vertices
has n-1 edges and no cycles at all, so every edge of a tree must be a
single-edge part. Thus no universal bound smaller than n-1 can work
for trees. Complete bipartite graphs give a sharper lower bound of
about (3/2)n, but that is not needed for the main idea.
There are two corollaries.
COROLLARY 1 (Eulerian graphs).
Every finite simple Eulerian graph on n vertices has an edge partition
into at most C n cycles. A graph is Eulerian when every vertex has
even degree. It need not be connected.
COROLLARY 2 (quasirandom Eulerian graphs).
Fix delta > 0 and p > 0. Then there are eps > 0 and n0 such that every
Eulerian graph G on n >= n0 vertices has an edge partition into at most
Delta(G)/2 + delta n
cycles, provided that every partition V(G) = A union B with
|A|,|B| >= eps n has at least p |A| |B| edges between A and B.
Here Delta(G) is the maximum degree of G.
The term Delta(G)/2 cannot be improved: a cycle uses at most two edges
at any one vertex.
1. THE WORDS WE NEED
Graph: a finite set V of vertices and a set E of unordered pairs of
distinct vertices. The order of a graph is |V|, including isolated
vertices if we choose to keep them.
Edge-disjoint: no edge is used twice.
Spanning subgraph: a subgraph on the same vertex set as the original
graph.
Cut: a split of the vertex set into two parts A and V minus A. The
edges crossing the cut are the edges with one endpoint in A and one
endpoint outside A.
Cut expansion: suppose a graph H has r vertices. We say H has cut
expansion at least h if for every vertex set A, the number of edges
crossing the cut (A, V(H) minus A) is at least
h * min(|A|, r - |A|).
If h is large, then H has no narrow bottleneck. Every small group of
vertices has many edges leaving it. This is the engine that lets us
find cycles and route paths.
Box: a small vertex set Y used to hold a piece of the graph at one
scale.
Piece: an expanding graph R inside a box. In this paper, a piece has
order between D^0.90 and D^1.02 and cut expansion at least D^0.90,
where D is the current scale.
Batch: a group W of tiny descendant boxes, with |W| at most B0. We
will fold vertices inside batches.
Folding set: a set X of vertices that we will pair up. Identifying a
pair means gluing its two vertices into one new vertex.
Quotient graph: the graph obtained after folding. The quotient has
fewer vertices than the original graph, so we can apply induction to
it.
Router: an expanding piece P_R whose edges are reserved for joining
things. A router supplies paths between pairs of vertices that need
to be connected.
Residual graph: a graph holding the edges that have not yet been put
into a cycle or a single-edge part. We will apply induction to
residual graphs later.
2. WHY THE PROOF IS NOT A ONE-LINE ARGUMENT
A greedy approach fails. If we repeatedly remove long cycles, the
remaining graph can become a forest with many edges. If we remove
short cycles, there can be too many of them. We need a global way to
remove many edges at once, leave a sparse remainder, and pay for the
whole process.
The paper uses induction on the number of vertices. At each step, it
looks at a sequence of scales:
D_j = n^(theta^j), theta = 0.95, j = 0,1,2,...
At scale D_j, it removes a few long cycles. Then it splits the graph
into boxes of order at most D_j^1.02. Inside each box it extracts
expanding pieces of order at least D_j^0.90. The leftover graph in
each box has average degree at most D_j^0.95, which is the scale of
the next step.
If we processed every piece at every scale directly, the cost would
multiply by the number of scales. The main idea is to choose one
layer whose total piece order S is large enough to pay for a whole
prefix of earlier scales, plus a fixed number K of extra scales. The
pieces in that layer have two jobs:
(a) small-residue processing: turn most of their edges into cycles
and single edges, leaving residual graphs of tiny total order;
(b) routing: keep some edges in reserve so that cycles in the
quotient graph can be lifted back to simple cycles in the
original graph.
The folding step reduces the vertex count. That reduction is the
"savings" that pays for the work outside the recursive calls.
3. THE STRONG INDUCTIVE STATEMENT
All logarithms in this paper are base two unless we say ln. Define a
function phi by
phi(1) = 1/2,
phi(n) = max { 1/2, 1 - 1/sqrt(log n) } for n > 1.
This function is at most 1, and it is slightly smaller than 1 when n is
large. That tiny saving will absorb the overlap created when we split
boxes.
PROPOSITION (inductive bound).
There is an absolute constant C such that every finite simple graph on
n >= 1 vertices has an edge partition into at most
C * phi(n) * n
simple cycles and single edges.
Since phi(n) <= 1, this proposition proves the main theorem.
We prove the proposition by strong induction on n. We first choose an
absolute lower cutoff D_*. For graphs with 1 <= n < D_*, we put every
edge in its own single-edge part. This uses n-1 parts, which is at most
D_* n <= C n, and phi(n) >= 1/2. So the base case is safe once C is at
least D_*.
Now suppose n >= D_* and the proposition is known for every smaller
positive order. Put
D_j = n^(theta^j), theta = 0.95,
m = min { j >= 0 : D_j < D_* }.
Take D_* > 2. Then m is finite and positive, and all scales
D_0, ..., D_(m-1) are at least D_*.
4. SPLITTING AT ONE SCALE
We need two operations at a scale D.
LEMMA (splitting at a scale).
There are absolute constants D_sp and C0 such that, for every real
D >= D_sp, every graph G on a nonempty vertex set of order N and with
average degree at most D admits the following two operations.
(i) Remove a family C of edge-disjoint cycles, each of length at least
D^1.01, with
|C| <= N / (2 D^0.01).
Partition the remaining edges into graphs G_Y on an indexed family Y of
vertex sets, called boxes. These satisfy
union of all Y = V(G),
1 <= |Y| <= D^1.02,
sum over Y of |Y| <= (1 + C0/log D) * N.
The graphs G_Y contain only their assigned edges. Their vertex sets
may overlap.
(ii) Put sigma = D^0.90. For each box Y, partition E(G_Y) into the
edge sets of a family R_Y of graphs R and a graph H_Y. The vertex sets
of the graphs in R_Y are pairwise disjoint subsets of Y. Each R has
cut expansion at least sigma and order
sigma <= |V(R)| <= D^1.02.
The residual graph H_Y is taken on all of Y, including isolated
vertices, and satisfies
2 |E(H_Y)| / |Y| <= D^0.95.
Thus the cycles in C, the pieces R, and the residual graphs H_Y
together partition E(G).
We may take C0 = 2.
WHY (i) IS TRUE.
Choose a maximal family of edge-disjoint cycles of length at least
D^1.01. Since G has at most N D / 2 edges, the number of chosen cycles
is at most N / (2 D^0.01). Delete those cycle edges. By maximality,
the remaining graph has no cycle of length at least D^1.01.
Now put T = D^1.02. We split any current graph H of order u > T. Let
eps = 1/32. There is a nonempty vertex set U with
|U| <= u/2,
|N_H(U) minus U| < eps |U| / log^2 u.
If not, expansion lets us find a long cycle, as follows. Put
alpha = eps / log^2 u and suppose every vertex set W with
0 < |W| <= u/2 has at least alpha |W| external neighbors. Run
depth-first search. The counts (unexplored minus finished) go
from u-1 to -u, decreasing by exactly 1 at each step, so at some
moment they are equal, say to t; the stack path then has
L = u - 2t vertices with 0 <= t < u/2. All external neighbors
of the unexplored set lie on the stack path, so expansion gives
L >= alpha t, hence L >= alpha u / 3 in either case (t >= u/3,
or t < u/3 with L > u/3). Put j = floor(q) and split the stack
path into three consecutive segments X, J, Z with |J| = j and
|X|, |Z| >= L/4. If H - J has a path from X to Z, its union
with the X-Z subpath of the stack path is a simple cycle of
length at least j + 2 > q. If no such path exists, the
component of H - J containing X has all its external neighbors
in J, so expansion gives j >= alpha (L/4) >= alpha^2 u / 12 > q,
contradicting j = floor(q). Either way, H has a cycle longer
than q.
For u > T, this q(u) is larger than D^1.01 once D is large. That
contradicts the absence of long cycles. So the sparse set U exists.
Let B = N_H(U) minus U. Split H into two children on vertex sets
V1 = U union B,
V2 = V(H) minus U.
Give the first child every edge with both endpoints in V1. Give the
second child every other edge. Every edge incident with U has both
endpoints in U union B, so every edge given to the second child has
both endpoints in V2. This is an edge partition. The two child vertex
sets cover the parent. Their intersection is exactly B.
We have |U| = s <= u/2 and |B| = b < eps s / log^2 u. For large D,
1 <= u1 = s+b <= 3u/4,
1 <= u2 = u-s < u,
u1 + u2 = u+b <= u + eps u1 / log^2 u.
Repeat until every box has order at most T. The splitting tree is
finite because both child orders are smaller than the parent order.
The leaves are the boxes. Their vertex sets cover V(G), and the edge
assignments show that the leaf graphs partition the remaining edges.
The sum of the child orders can exceed the parent order by b. To pay
for this overlap, define for x >= 1
f(x) = 1 + 1/log(T/2) - 1/log(max{x, T/2}).
This f is nondecreasing, and 1 <= f(x) <= 2. At a split of a graph of
order u > T, put M = max{u1, T/2}. Then M <= 3u/4, so
f(u) - f(u1) = 1/log M - 1/log u
>= log(4/3) / log^2 u.
Monotonicity gives f(u2) <= f(u). Therefore
u1 f(u1) + u2 f(u2)
<= (u1+u2) f(u) - u1 log(4/3)/log^2 u
<= u f(u) + (u1/log^2 u)(eps f(u) - log(4/3))
<= u f(u),
because eps f(u) <= 1/16 < log(4/3). Apply this inequality down the
finite splitting tree. Since f >= 1 on the leaves,
sum over boxes Y of |Y|
<= sum over Y of |Y| f(|Y|)
<= N f(N)
<= N (1 + 1/log(T/2)).
Since T = D^1.02 and D >= 4,
1/log(T/2) = 1/(1.02 log D - 1) <= 2/log D.
This gives the box order bound with C0 = 2.
WHY (ii) IS TRUE.
Fix a box Y of order y. Start with its assigned graph G_Y. Whenever a
current graph on a vertex set A of order at least two fails to have cut
expansion sigma, choose a split A = A1 union A2 with
cut(A1,A2) < sigma * min(|A1|, |A2|).
Put those cut edges into the residual graph H_Y. Continue separately
with the edges inside A1 and the edges inside A2. Both child orders
strictly decrease, so the process stops. The terminal vertex sets
partition Y. The nonsingleton terminal graphs form R_Y. By the
stopping rule, each has cut expansion at least sigma. If such a graph
has order r, its singleton cuts show that its minimum degree is at
least sigma. Since the graph is simple, r-1 >= sigma. So its order is
at least sigma. It is also at most D^1.02 because it lies inside Y.
To bound the number of edges put into H_Y, charge each cut edge equally
to the vertices on the smaller side of the split. A charged vertex
receives less than sigma at that split. Whenever a vertex is charged,
the current set containing it at least halves in size. So any one
vertex is charged at most log y times. Thus
|E(H_Y)| <= sigma y log y.
For y <= D^1.02 and large D,
2 |E(H_Y)| / y
<= 2 sigma log y
<= 2.04 D^0.90 log D
<= D^0.95.
The terminal graphs and H_Y partition E(G_Y), so (ii) is proved.
5. THREE TOOLS FROM OUTSIDE
We need three standard tools. We state them in the exact forms used
later.
TOOL 1 (Lovasz path-and-cycle decomposition).
The edges of a finite simple graph on n vertices can be partitioned
into at most floor(n/2) paths and cycles.
A path here is simple and has at least one edge. A cycle is simple and
has length at least three.
We need a corollary about endpoints.
COROLLARY (bounded endpoint load).
Every finite simple graph on n vertices has an edge partition into
paths such that each vertex is an endpoint of at most two paths. In
particular, the partition has at most n paths.
PROOF.
If n = 0 there is nothing to prove. Otherwise add one new vertex v0.
Join v0 to exactly the even-degree vertices of the original graph,
including isolated vertices. Every old vertex now has odd degree. In
any path-and-cycle partition, an old vertex must therefore occur as a
path endpoint an odd positive number of times.
Apply the Lovasz theorem to the augmented graph, and let p be the
number of path parts. The old vertices force 2p >= n. The theorem
gives
ceil(n/2) <= p <= number of parts <= floor((n+1)/2) = ceil(n/2).
So every part is a path, and each old vertex is an endpoint exactly
once.
Delete v0 from all these paths. Discard any edgeless remnants. Every
old vertex was incident to at most one deleted edge, so it gains at
most one new endpoint occurrence. The remaining paths partition the
original edge set and have endpoint load at most two. Each
positive-length path has two endpoints, so there are at most n paths.
This proves the corollary.
TOOL 2 (Aharoni-Haxell hypergraph Hall theorem).
A hypergraph is a finite family of nonempty subsets of a finite ground
set. A matching is a subfamily of pairwise disjoint hyperedges.
Let s be a positive integer. Let (H_i) be a finite indexed family of
hypergraphs on a common ground set. Suppose every hyperedge is
nonempty and has size at most s. If for every nonempty set I of
indices, the union of the hypergraphs H_i with i in I has a matching of
size strictly greater than s(|I|-1), then there are hyperedges E_i in
H_i, one for each index i, that are pairwise disjoint.
We use the bounded-rank form. If the hypergraphs have edges of
different sizes, pad each edge occurrence with private fresh vertices
until every edge has size exactly s. Matchings stay matchings, and
disjoint padded representatives project to disjoint original
representatives. The hypergraphs need not be distinct.
TOOL 3 (Chernoff estimates).
If X is binomial with mean mu, then
Pr(X <= mu/2) <= exp(-mu/8),
Pr(X >= 2 mu) <= exp(-mu/3).
We use linearity of expectation, Markov's inequality, the union bound,
and these two estimates. The constants are not important; what matters
is that the tails are exponentially small.
6. PREFIX SELECTION AND THE LAYER LEDGER
Fix the absolute parameters
theta = 0.95,
K = 200,
P0 = 4(K+1),
eta = 1/(100 P0).
Then
1.02 theta^K < 0.001,
theta^(K+1) < 0.001,
because theta^K <= exp(-10).
LEMMA (selection of a prefix).
Let (S_j) for j >= 0 be a nonnegative, finitely supported sequence
which is not identically zero. There is an index i with S_i > 0 such
that
sum from j=0 to i+K of S_j <= P0 S_i.
PROOF.
Start at the first positive term and maintain the invariant
sum from j=0 to i of S_j <= 2(K+1) S_i.
If the desired inequality fails, then the sum of the next K terms is
greater than 2(K+1)S_i. Their largest value M is therefore greater
than 2S_i. Move to an index i' in that window with S_i' = M. Then
sum from j=0 to i' of S_j
<= 2(K+1)S_i + K M
< (2K+1)M
<= 2(K+1)S_{i'}.
The invariant persists. Each move increases the index and lands at a
positive term. Finite support forces the procedure to stop. At that
point the desired inequality holds.
NOW BUILD THE PROSPECTIVE LAYERS.
Start with the given graph G. Perform both operations of the
scale-splitting lemma at each successive scale
D_0, D_1, ..., D_{m-1}.
The input at stage j has average degree at most D_j. This holds first
because the average degree of G is at most n-1 < D_0 = n. It holds
later because the residual graph in each new box has average degree at
most D_j^0.95 = D_{j+1}.
Let Y_j be the indexed family of level-j boxes. Let R_j be the
indexed family of pieces removed inside them. The residual graph
passed to the next stage keeps the entire vertex set of its box,
including isolated vertices. Every box has a unique indexed parent,
and its vertex set is contained in its parent's vertex set.
Descendants of a box cover that box's vertex set. Distinct indices
are kept even when their vertex sets overlap or coincide.
These operations define prospective layers. We will later keep only a
prefix of them. At the end of every prefix, the long cycles removed so
far, the pieces removed so far, and the remaining input graphs
partition E(G). Discarding prospective operations beyond a chosen
prefix means keeping their input graphs, with all assigned edges, at
that prefix's boundary.
Write
N_{-1} = n,
N_j = sum over Y in Y_j of |Y|,
S_j = sum over R in R_j of |V(R)|,
and set S_j = 0 for j >= m.
Increase the absolute constant C0 in the scale-splitting lemma if
necessary so that C0 >= 1. Put
C2 = 40 C0.
For 0 <= j < m,
sum from l=0 to j of 1/log D_l
= (1/log D_j) sum from t=0 to j of theta^t
<= 20/log D_j.
Provided log D_* >= C2, the product of the order increases is bounded
by
n <= N_j
<= n * product from l=0 to j of (1 + C0/log D_l)
<= n (1 + C2/log D_j)
<= 2n.
Here we used 1+x <= exp(x) and exp(x) <= 1+2x for 0 <= x <= 1/2.
The lower bound comes from keeping the vertex cover at every split.
The same product calculation, using the relevant subproduct, shows
that the orders of all level-j descendants of a box of order y sum to
at most
(1 + C2/log D_j) y.
Their union still covers the full vertex set.
We also require
D^(-0.01) <= 1/log D
for every D >= D_*. If L_j is the family of long cycles removed
through level j, then
|L_j|
<= sum from l=0 to j of N_{l-1}/(2 D_l^0.01)
<= n * sum from l=0 to j of 1/log D_l
<= 20n/log D_j.
These bounds do not depend on the number of layers. Piece
disjointness inside each box gives
S_j <= N_j <= 2n.
At the end of a prefix through level t, the assigned edge sets give
the disjoint union
E(G) =
disjoint union over L in L_t of E(L)
disjoint union
disjoint union over j=0 to t of
disjoint union over R in R_j of E(R)
disjoint union
the remaining boundary graphs.
This ledger is the bookkeeping spine of the whole proof. Every later
operation must put every edge into exactly one of these categories, or
move it to a later category without duplicating it.
7. ROUTING WITH TEAM CONSTRAINTS
A demand asks for a path between two distinct vertices. Demands are
indexed, so several demands may ask for the same pair. We need three
things at once:
(1) each route is short;
(2) all routes are edge-disjoint;
(3) routes in the same team are internally vertex-disjoint.
Different teams may share internal vertices. They compete only for
edges. This is exactly what the cycle-lifting step needs.
LEMMA (routing).
Let P be a graph of order r >= 2 with cut expansion h > 0. Put
g = ceil(8(r/h) log(2r)),
l = 2g(1 + ceil(log r)).
Let D be a finite set of demands. Demand p has distinct endpoints
x_p and y_p in V(P). Suppose each vertex occurs as an endpoint in at
most k demands, where k >= 1. Partition D into teams of size at most
b, where b >= 1. Give each demand p a forbidden set Z_p subset of
V(P) of size at most z, where z >= 0.
If
h >= 64 (l^2 (k+b) + z),
then there are simple x_p-y_p paths Q_p in P, one for each demand p,
with these properties:
(i) each Q_p has length at most l and no internal vertex in Z_p;
(ii) the paths Q_p are pairwise edge-disjoint;
(iii) the internal vertex sets of paths in the same team are
pairwise disjoint.
The forbidden set Z_p may contain x_p or y_p. The restriction is only
on internal vertices. If a route must avoid another demand's
endpoints internally, put those vertices into its Z_p.
We also use the uniform bound
l <= 108 (r/h) (log r)^2.
Indeed, h < r and r >= 2 imply
g <= 9(r/h) log(2r),
log(2r) <= 2 log r,
1 + ceil(log r) <= 3 log r.
PROOF.
If D is empty, there is nothing to do. Assume D is nonempty. Write
c(p) for the team of demand p.
Make a resource set which is the tagged disjoint union of E(P) and the
tokens (v,c), where v is a vertex and c is a team.
For each demand p, form a hypergraph H_p on this resource set. Its
hyperedges correspond to all simple x_p-y_p paths of length at most l
whose internal vertices avoid Z_p. A candidate path contributes its
graph edges and the token (v,c(p)) for each internal vertex v. A path
of length t >= 1 contributes
2t - 1 <= 2l
resources. So every hyperedge is nonempty and has size at most 2l.
A choice of pairwise disjoint representatives from the hypergraphs H_p
gives exactly the three required properties. We verify the sufficient
condition of the Aharoni-Haxell theorem with
s = 2l.
Suppose, for a contradiction, that the condition fails for some
nonempty set I of demands. Let M be a maximum matching in the union
of the hypergraphs H_p with p in I. Then
|M| <= 2l (|I| - 1).
Let F be the set of graph edges used by M. For each team c, let Y_c be
the set of vertices v such that the token (v,c) is used by M. Each
matching member uses at most l graph edges and at most l tokens, so
|F| <= 2l^2 |I|,
sum over c of |Y_c| <= 2l^2 |I|.
These estimates allow several matching members to come from one
demand. We are not restricting demand indices.
For each team c, let
m_c = number of demands p in I with c(p) = c.
Then m_c <= b. Hence
sum over p in I of |Y_{c(p)}|
= sum over c of m_c |Y_c|
<= 2b l^2 |I|.
Therefore the set
I1 = { p in I : |Y_{c(p)}| <= 4b l^2 }
has size at least |I|/2.
Choose an inclusion-maximal set I2 subset of I1 whose endpoint pairs
{x_p,y_p} are pairwise vertex-disjoint. Every demand in I1 meets one
of these selected pairs. The two vertices of any selected pair occur
in at most 2k demands in total. So
|I2| >= |I1|/(2k) >= |I|/(4k).
We also use the global endpoint count
2|I| <= k r.
Now fix p in I2. Define
W_p = (Z_p union Y_{c(p)}) minus {x_p,y_p},
P_p = (P - F) - W_p.
The first deletion removes edges; the second removes vertices. Both
endpoints remain in P_p. By the routing condition,
|W_p| <= z + 4b l^2
<= 4(z + (k+b)l^2)
<= h/16
<= h/4.
Set
T = l/2 = g(1 + ceil(log r)).
This is an integer.
If the balls of radius T about both x_p and y_p in P_p had size
greater than r/2, they would intersect. Joining their paths to an
intersection vertex gives an x_p-y_p walk of length at most 2T = l.
Deleting closed subwalks gives a simple path of no greater length.
It uses no edge of F and no vertex of W_p. Its internal vertices avoid
both Z_p and Y_{c(p)}. Therefore its hyperedge in H_p is disjoint from
M, contradicting the maximality of M.
Consequently, for every p in I2, we may choose an endpoint s_p whose
radius-T ball in P_p has size at most r/2. Let
S = { s_p : p in I2 }.
These roots are distinct because the selected endpoint pairs are
disjoint. Each root keeps its demand label: write p(s) for the unique
p in I2 with s_p = s. Then
|{ v : dist_{P_{p(s)}}(s,v) <= T }| <= r/2
for every s in S.
The deleted-edge budget may be too large to grow a ball from one root.
We first grow unions of balls, keeping each root's graph. Then we
alternate halving the root set with further growth until one root
remains.
For a nonempty A subset of S and an integer t >= 0, put
B_t(A) = union over s in A of
{ v in V(P_{p(s)}) : dist_{P_{p(s)}}(s,v) <= t }.
These are unions of balls in their respective graphs. The forbidden
set stays with its root throughout.
We claim that
|B_{t+1}(A)| >= (1 + h/(2r)) |B_t(A)|
whenever
0 < |B_t(A)| <= r/2,
|F| <= h |B_t(A)|/4.
To prove this, let B = B_t(A). Assign to each v in B one root s(v) in
A that reaches v within t steps in P_{p(s(v))}. Consider a boundary
edge vw of B, with v in B and w outside B. It extends this particular
root's path whenever
vw is not in F,
w is not in W_{p(s(v))}.
In that event, w is in B_{t+1}(A) minus B. Because P is simple, at most
|W_{p(s(v))}| <= h/4 boundary edges at v fail the second condition.
Cut expansion and the edge-deletion threshold therefore leave at least
h|B| - (h/4)|B| - |F| >= (h/2)|B|
usable boundary edges. Each new vertex receives at most r such edges.
Thus at least h|B|/(2r) new vertices are reached, proving the growth
claim.
It follows that, for every integer t >= 0,
if |B_t(A)| >= 1 and |F| <= h|B_t(A)|/4,
then |B_{t+g}(A)| > r/2.
Indeed, the conclusion is immediate by monotonicity if the starting
union already has size greater than r/2. Otherwise, if it still had
size at most r/2 after g more steps, all intervening unions would have
size at most r/2, and monotonicity would preserve the edge-deletion
threshold. We could apply the growth claim at all g steps. Since
0 < h <= r-1 < r,
log(1 + h/(2r)) >= h/(4r),
so
|B_{t+g}(A)|
>= (1 + h/(2r))^g |B_t(A)|
>= 2^(g h/(4r)) |B_t(A)|
>= (2r)^2 |B_t(A)|
> r/2,
a contradiction. This also verifies the growth time with the ceiling
in the definition of g.
Initially B_0(S) = S. By the matching bounds, the pair count, and the
routing condition,
|F| <= 2l^2 |I| <= 8k l^2 |S| <= h|S|/4.
So the growth block gives |B_g(S)| > r/2.
Now suppose a nonempty root set A has |B_t(A)| > r/2 and |A| >= 2.
Partition A into two nonempty sets whose sizes differ by at most one.
Their radius-t ball unions together cover B_t(A), so one of them, say
A', satisfies
|A'| <= ceil(|A|/2),
|B_t(A')| > r/4.
The original matching has a bound independent of the number of
retained roots:
|F| <= 2l^2 |I| <= l^2 k r <= h r/64 < h|B_t(A')|/4.
Thus another growth block gives |B_{t+g}(A')| > r/2.
Start with A = S at radius g and repeat this operation until only one
root remains. After j halvings the number of roots is at most
ceil(|S|/2^j). So at most ceil(log |S|) halvings are needed,
including zero when |S| = 1. At termination, a single root has a ball
larger than r/2 at an integer radius at most
g(1 + ceil(log |S|))
<= g(1 + ceil(log r))
= T.
This contradicts the small-ball property of that root. Therefore no
set I can make the Aharoni-Haxell condition fail. Applying the
theorem gives disjoint representatives, and their paths prove the
lemma.
8. EXPANSION IN SMALL RESERVOIRS
This section turns an expanding graph into many cycles and single edges,
leaving only a tiny residual graph. The tiny residual will be handled
by induction later. The key idea is to keep three disjoint reservoirs
of vertices. Every edge misses at least one reservoir, so every edge
can be closed through a reservoir that does not contain it.
At scale D put
sigma = D^0.90,
tau = D^0.74.
Throughout this section the order r satisfies
sigma <= r <= D^1.02.
All assertions for sufficiently large D are uniform over this range.
8.1 SPLITTING AN EXPANDER INTO SEVERAL EXPANDERS
LEMMA (edge splitting).
Fix c > 0 and a positive integer l. For all sufficiently large D, if
an r-vertex graph P has cut expansion at least
h0 >= c D^0.90
and D^0.90 <= r <= D^1.02, then E(P) can be partitioned into l spanning
subgraphs, each with cut expansion at least h0/(2l).
PROOF.
Assign each edge independently and uniformly to one of l classes.
Fix a cut whose smaller side has size u >= 1, and let e be the number
of edges of P crossing that cut. In any fixed class the number of
crossing edges is binomial with mean e/l >= h0 u/l. By the Chernoff
estimate, the probability that this class has fewer than h0 u/(2l)
crossing edges is at most
exp(-h0 u/(8l)).
There are at most
2 binom(r,u) <= 2 r^u
choices of a cut with smaller side of size u. Thus the probability of
any failure is at most
2l * sum from u=1 to floor(r/2)
( r exp(-h0/(8l)) )^u = o(1).
Indeed, h0 >= cD^0.90 while log r <= 1.02 log D, so the base of this
geometric sum tends to zero uniformly. A successful assignment gives
the required edge partition. Each class is taken on the full vertex
set of P.
8.2 SAMPLING VERTICES AND KEEPING EXPANSION
The next lemma says that a random vertex sample of an expander is still
an expander, with a smaller but still polynomial expansion.
LEMMA (vertex sampling).
Fix c' > 0 and p in (0,1). Let P have order
D^0.90 <= r <= D^1.02
and cut expansion at least h = c'D^0.90. Select each vertex
independently with probability p to form V'. With probability
1 - o(1) as D tends to infinity, all of the following hold:
|V'| <= 2pr,
|N_P(v) intersect V'| >= ph/2 for every v in V(P),
P[V'] has cut expansion at least tau = D^0.74.
The error term is uniform over the stated graphs and orders, with c'
and p fixed.
PROOF.
The minimum degree of P is at least h. The order bound and the sampled
degree bounds fail with total probability at most
exp(-pr/3) + r exp(-ph/8) = o(1)
by the Chernoff estimates.
It remains to prove the expansion assertion. We control a
deterministic family of cuts, and then approximate any hypothetical
failing sampled cut by a member of that family.
A DETERMINISTIC WITNESS FAMILY.
In a failing sampled cut, the sampled degree bound forces most vertices
on the smaller side to have many neighbors on that side. A small
selection from that side can hit their neighborhoods while exposing
few vertices across the cut. This is why we enumerate unions of a
small number of original neighborhoods.
Set
M = C_p log r, C_p = 16/p,
s = ceil(4rM/h).
For sufficiently large D, we have M/h < 1 and s <= r.
Before sampling V', form the family
U = { union over v in S of N_P(v) :
S subset of V(P), |S| <= s }.
Its members are unions of open neighborhoods in the original graph.
Its size satisfies
|U| <= sum from t=0 to s of binom(r,t)
<= (s+1) r^s
= exp( O((1 + rM/h) log r) ).
Repeated neighborhood unions only decrease this count.
We claim that, with probability 1 - o(1), simultaneously for every U in
the family satisfying
min(|U|, r-|U|) >= ph/8,
one has
e_P(U intersect V', V' minus U)
>= (p^2/4) |boundary_P U|.
Fix such a U, and put e = |boundary_P U|. Expansion gives
e >= ph^2/8. Partition its cut edges into at most 2r matchings:
greedily color the cut edges, observing that an edge has fewer than 2r
other edges incident with its endpoints. Fix one such coloring for
each cut before sampling.
The matching classes of size less than e/(4r) contain fewer than e/2
edges in total. In a remaining matching of size m, the indicators that
both endpoints of an edge belong to V' are independent, since its edges
have disjoint endpoints. Its retained size is therefore binomial with
mean p^2 m. The probability of retaining fewer than p^2 m/2 edges is at
most
exp(-p^2 m/8)
<= exp(-p^2 e/(32r))
<= exp(-p^3 h^2/(256r)).
When none of these matching events fails, the large classes retain at
least (p^2/2)(e/2) = p^2 e/4 edges. Independence between different
matching classes or between different cuts is unnecessary: a union
bound bounds the probability of any failure by
2r |U| exp(-p^3 h^2/(256r)) = o(1).
To verify this uniformly, note that
h^2/r >= (c')^2 D^0.78,
r/h <= (c')^(-1) D^0.12,
M = O_p(log D).
So the positive term coming from |U| is
O_{p,c'}(D^0.12 (log D)^2), while the negative term in the exponent has
magnitude at least a fixed positive multiple of D^0.78.
APPROXIMATING A FAILING CUT.
Fix an outcome satisfying the size and degree bounds and all the
witness-cut inequalities. Suppose, for a contradiction, that some
A subset of V' satisfies
0 < a = |A| <= |V'|/2,
e_P(A, V' minus A) < tau a.
We may assume D is large enough that tau < ph/4.
If a <= ph/4, every vertex of A has more than ph/4 neighbors in
V' minus A, because its sampled degree is at least ph/2 and it has at
most a-1 neighbors in A. This contradicts the displayed inequality.
Thus
a > ph/4.
Let
A_good = { v in A : |N_P(v) intersect A| >= ph/4 }.
Each vertex in A minus A_good has more than ph/4 neighbors across the
sampled cut. Hence
|A minus A_good| <= 4 tau a/(ph).
Now make a separate auxiliary random choice solely to prove the
existence of a suitable set S subset of A. Include each vertex of A
independently with probability q = M/h. For every v in A_good, the
probability that S misses all its neighbors in A is at most
(1-q)^(ph/4) <= exp(-pM/4).
Thus the probability of any required miss is at most
r exp(-pM/4) <= r^(-3) < 1/4.
Here the chosen value of C_p is more than sufficient, since all
logarithms are base two.
Also E|S| = aM/h. Let T(S) be the number of vertices of V' minus A
with a neighbor in S. Then a union bound for each such vertex gives
E T(S)
<= (M/h) sum over v in V' minus A of |N_P(v) intersect A|
= (M/h) e_P(A, V' minus A)
< tau M a/h.
Markov's inequality shows that each of the events
|S| > 4aM/h,
T(S) > 4 tau M a/h
has probability at most 1/4. The sum of these three failure
probabilities is less than one. We can therefore choose S satisfying
all three desired properties:
|S| <= 4aM/h,
T(S) <= 4 tau M a/h,
S intersect N_P(v) is nonempty for every v in A_good.
The auxiliary choice is made after V' and A have been fixed. The
uniform witness-cut event was already established for every possible
resulting neighborhood union.
Put
U = union over v in S of N_P(v).
Since |S| <= 4aM/h <= 4rM/h, we have U in the family. The vertices of
A absent from U are all exceptional, and the vertices of U intersect V'
outside A are counted by T(S). Consequently
delta = |(U intersect V') symmetric difference A|
<= 4 tau a/(ph) + 4 tau M a/h
= O_p( tau M a/h )
= o(a).
In the last step we used
tau M/h = O_{p,c'}(D^(-0.16) log D) = o(1).
Both sides of the cut in the original graph are large:
|U| >= |A| - delta = a - delta,
r - |U| >= |V' minus U| >= |V' minus A| - delta >= a - delta.
For sufficiently large D, these are at least a/2 > ph/8. Applying the
witness-cut inequality and the expansion of P therefore gives
e_P(U intersect V', V' minus U) >= p^2 h a/8.
On the other hand, changing the side of one vertex changes the size of
a cut in a simple r-vertex graph by at most r-1. Changing the delta
vertices yields
e_P(U intersect V', V' minus U)
<= e_P(A, V' minus A) + r delta
< tau a + r delta.
The ratio of this upper bound to h a is at most
tau/h + O_p( tau M r/h^2 )
= O_{p,c'}(D^(-0.16))
+ O_{p,c'}(D^(-0.04) log D)
= o(1),
contradicting the lower bound. Thus no bad cut exists. Together with
the size and degree bounds and the witness-cut bound, this proves the
lemma.
All uses of o(1) above occur after p and c' have been fixed. In
particular, an arbitrarily small fixed positive sampling probability
changes the cutoff but does not change any strict exponent inequality.
8.3 CLOSING PATHS THROUGH THREE RESERVOIRS
We now use three disjoint reservoirs of arbitrarily small fixed
relative order. Every edge has both endpoints outside at least one of
them. After reserving connecting edges, we can assign each remaining
edge to such a complement, partition that graph into paths, and close
the paths through its reservoir.
LEMMA (small residue).
Fix eta > 0 and c > 0. For all sufficiently large D, let G be an
r-vertex graph with
D^0.90 <= r <= D^1.02
containing a spanning subgraph of cut expansion at least cD^0.90.
Then E(G) has a partition into
(a) at most 9r completed parts, each a simple cycle or a single
edge, and
(b) the edge sets of at most three residual simple graphs.
The residual graphs have pairwise disjoint vertex sets contained in
V(G), their total order is at most eta r, and each has order strictly
less than r.
PROOF.
Write c0 = min(c,1), and fix
p = min(eta/12, 1/12),
h = (c0/6) sigma.
In particular, 3p < 1, 6p <= eta, and 2p < 1.
By the edge-splitting lemma, the edges of the given spanning expanding
subgraph can be partitioned into three spanning subgraphs P1, P2, P3,
each of cut expansion at least h.
DISJOINT RESERVOIRS AND BOUNDED REPRESENTATIVE LOADS.
Label the vertices independently, using each label i in {1,2,3} with
probability p and a fourth label with probability 1-3p. Let V_i be the
vertices with label i. These three sets are pairwise disjoint, and
each marginal V_i is a Bernoulli-p sample for the fixed graph P_i. By
the vertex-sampling lemma and a union bound over the three marginal
failure probabilities, we can choose the labels so that, for each i,
|V_i| <= 2pr,
|N_{P_i}(v) intersect V_i| >= ph/2 for every v in V(G),
P_i[V_i] has cut expansion at least tau.
Independence between these three success events is not required. The
neighbor assertion makes V_i nonempty and gives every vertex of V_i a
neighbor in V_i, so |V_i| >= 2.
For each i, reserve all edges
E_i^in = E(P_i[V_i]).
Also reserve two edges from each v in V(G) minus V_i to two distinct
representatives in V_i. The representatives can be chosen so that at
most
k0 = ceil(8r/(ph))
of these edges are incident with any one vertex of V_i. Indeed,
process the two choices for every outside vertex in turn. At any
point fewer than 2r edges have been chosen, so the number of
representatives already at capacity k0 is at most
2r/k0 <= ph/4.
There are at least ph/2 potential representatives for the next choice
by the sampling properties. Excluding the saturated ones and, for the
second choice at a vertex, its first representative, leaves at least
ph/4 - 1 > 0
choices for sufficiently large D. This greedy procedure proves the
claim. Denote the selected outside-to-representative edges by E_i^out.
For a fixed i, the internal and outside reservations are disjoint.
Reservations for different values of i also have disjoint edge sets,
because they belong to the edge-disjoint graphs P_i. Let
E_res = union over i=1,2,3 of (E_i^in union E_i^out)
be the entire reserved edge set.
THE COMPLEMENTARY PATH PARTITIONS.
Every edge in E(G) minus E_res has both endpoints outside at least one
V_i, since its two endpoints meet at most two of the three disjoint
reservoirs. Assign each such edge to one such index i, choosing just
one index if several are available. This gives edge-disjoint graphs
G_i on V(G) minus V_i whose edge sets partition all nonreserved edges.
By the endpoint corollary, each G_i has a partition into positive-length
simple paths, with each vertex an endpoint at most twice. Since each
path has two endpoint occurrences, its path family P_i has size at most
|V(G) minus V_i| <= r.
An empty edge set contributes no paths.
For each endpoint occurrence of v in P_i, assign one of its two
reserved edges in E_i^out, using different edges for different
occurrences. This is possible by the endpoint load bound. For a path
Q in P_i with distinct endpoints x,y, let x',y' in V_i be their
assigned representatives. When x' is not y', issue one demand between
them in P_i[V_i]. When x' = y', no routing demand is necessary.
Every demand-end occurrence uses a different reserved edge at its
representative. Hence the total demand load at each vertex of V_i is
at most k0.
ROUTING AND SIMPLE CYCLES.
Apply the routing lemma separately in each P_i[V_i], with expansion
parameter tau, endpoint load k = k0, singleton teams (b = 1), and no
forbidden vertices (z = 0). We check its numerical hypothesis using
the actual order r_i = |V_i|. This graph has order at least two and
cut expansion at least tau, and therefore tau <= r_i - 1. The value l_i
in the routing lemma satisfies
l_i = O( (r/tau) (log r)^2 ),
k0 = O_{p,c}( r/h ).
Here the ceiling in the definition of k0 is absorbed because
r/h >= 6. Consequently
l_i^2 (k0 + 1)
= O_{p,c}( r^3/(tau^2 h) (log r)^4 )
= O_{p,c}( D^0.68 (log D)^4 )
= o(D^0.74)
= o(tau).
Thus the routing condition holds for all sufficiently large D. The
lemma supplies pairwise edge-disjoint simple routing paths for all the
distinct-representative demands in this reservoir. All their edges are
in the reserved set E_i^in.
For Q as above with x' not equal to y', join its endpoints by the edge
xx', the routing path from x' to y', and the edge y'y. Every new
internal vertex lies in V_i, while Q is entirely outside V_i. The
resulting closed walk is therefore a simple cycle.
When x' = y', the two reserved edges themselves form a simple two-edge
connection from x to y through that representative, and again close Q
to a simple cycle. Its two reserved edges are distinct because x is
not y. In this case even a one-edge path Q produces a triangle; with
different representatives the resulting cycle has at least four edges.
Thus every completed cycle has length at least three.
The cycles are edge-disjoint. Their original path edges partition the
nonreserved edges; each assigned representative edge is used once; and
the routing paths are edge-disjoint within each P_i[V_i]. These three
types of edges are disjoint by reservation. The reservations in
different P_i are also edge-disjoint, regardless of vertex overlaps
among different cycles.
COUNTING AND THE EXACT REMAINING EDGE SETS.
We have produced at most
sum over i of |P_i| <= 3r
cycles. Take every unused edge in the union of E_i^out as a
single-edge part, using at most
sum over i=1,2,3 of 2|V(G) minus V_i| <= 6r
further parts. The number of completed parts is therefore at most 9r.
For each i, let H_i be the graph on V_i consisting of exactly the
unused edges of E_i^in. These are the only remaining edges: every
nonreserved edge was placed in a path, every reserved outside edge was
used in a cycle or taken singly, and every reserved internal edge was
used by a routing path or placed in H_i.
In particular, H_i is not defined by taking all remaining edges of the
original induced graph G[V_i]. Nonreserved edges, including ones with
both endpoints in a reservoir, were already assigned to the appropriate
complementary graphs. This accounts for every original edge exactly
once.
The graphs H_i are simple, have the pairwise disjoint vertex sets V_i,
and satisfy
sum over i=1,2,3 of |V(H_i)|
= sum over i of |V_i|
<= 6pr
<= eta r,
|V(H_i)| <= 2pr <= r/6 < r.
Isolated vertices may be retained, or a residual graph with no edges
may be omitted. The only parameters fixed before increasing D were eta,
c, and the constants determined from them. This completes the proof.
9. PAIR FOLDING
Identifying pairs of vertices reduces the order of the graph to which
induction will be applied. After setting aside loops and all but one
edge in each parallel class, each quotient edge has a unique original
representative.
A quotient cycle may enter a pair at one member and leave through the
other. A reserved path joins them. To obtain a simple cycle, the
interiors of these paths must avoid all representative endpoints and
be pairwise disjoint within that cycle. The routing lemma will supply
such paths. The present lemma is the other half: it bounds the number
of edges that must be thrown away during the folding.
A degree bound at the paired vertices alone is insufficient. For
positive integers a and m with m even, pairing the m-vertex side of
K_{m,a} forces a m/2 edges to be set aside, although each paired vertex
has degree a. The lemma therefore also bounds the number of neighbors
in each folding set at every vertex, including vertices outside those
sets.
LEMMA (pair folding).
Let J be a finite simple graph and let X_1, ..., X_t be pairwise
disjoint subsets of its vertex set. Suppose that a >= 1, that
m_i = |X_i| >= max{8, a^2}
for every i, and that
d_J(x) <= a for every x in union of X_i,
d_i(v) := |N_J(v) intersect X_i| <= a
for every v in V(J) and every i.
Then there are pairings within the X_i, each leaving exactly
m_i mod 2
vertices unpaired, and a set E_err subset of E(J) with
|E_err| <= 2 sum over i of m_i,
such that identifying each pair in J minus E_err gives a simple graph
Q. Every edge of Q has exactly one retained original edge as its
representative. Retaining all quotient vertices, including isolated
ones, we have
|V(Q)| = |V(J)| - sum over i of floor(m_i/2).
The assertion also holds when the family of folding sets is empty.
PROOF.
Choose a uniform perfect pairing when m_i is even. When m_i is odd,
adjoin a dummy vertex, choose a uniform perfect pairing on the m_i + 1
vertices, and delete the dummy vertex and its incident pairing edge.
Its original partner is left unpaired. Each pairing with one unpaired
original vertex has exactly one extension of this kind, so the
resulting distribution is uniform. Make the choices for different i
independently.
For distinct specified vertices u,v of a set of order m, symmetry of
the partner of u gives the following exact probabilities. For two
prescribed disjoint pairs, conditioning on the first pair leaves a
uniform perfect pairing on the remaining vertices, including the dummy
when present. Thus
Pr({u,v} is a pair)
= 1/(m-1) when m is even,
= 1/m when m is odd.
Pr(two prescribed disjoint pairs occur)
= 1/((m-1)(m-3)) when m is even,
= 1/(m(m-2)) when m is odd.
In particular, the even-column expressions are valid upper bounds for
both parities.
Let pi send each vertex to its fiber after the identifications. Every
fiber has size one or two. Before removing any edges, let Z count the
original edges that become loops, plus the unordered pairs of distinct
original edges that become the same nonloop edge. We bound E Z by
classifying all possible errors.
CASE 1: LOOPS AND COLLISIONS WITH A COMMON ORIGINAL ENDPOINT.
An original edge becomes a loop precisely when its endpoints form a
pair in some X_i. There are at most a m_i/2 original edges inside X_i,
so its expected loop contribution is at most
a m_i / (2(m_i-1)).
Two distinct edges sharing an original endpoint have the form vu, vw
with u not equal to w. If they become the same nonloop edge, then
pi(u) = pi(w) is not equal to pi(v),
so u,w must be paired in some X_i. No other identification is
possible: identifying all three original vertices would require a
fiber of size at least three.
Consequently the contribution charged to X_i is at most
(1/(m_i-1)) sum over v in V(J) of binom(d_i(v), 2)
<= a(a-1) m_i / (2(m_i-1)).
Here binom(d,2) <= (a-1)d/2 for every integer 0 <= d <= a, and
sum over v in V(J) of d_i(v)
= sum over x in X_i of d_J(x)
<= a m_i.
The equality counts both incidences of every internal edge on both
sides.
Combining the loop and common-endpoint bounds, the expectation is at
most
sum over i of a^2 m_i / (2(m_i-1))
<= (4/7) sum over i of a^2,
since m_i >= 8.
CASE 2: COLLISIONS WITH FOUR DISTINCT ORIGINAL ENDPOINTS.
Write the two edges as uv and xy, with four different vertices. For
them to become the same nonloop edge, the two fibers must be either
{u,x}, {v,y} or {u,y}, {v,x}.
All four vertices therefore belong to folding sets: a singleton fiber
cannot contain two distinct original endpoints.
If the two paired fibers lie in one X_i, then both original edges are
internal to X_i. Writing e_i = |E(J[X_i])|, there are at most
binom(e_i,2) <= e_i^2/2
possible vertex-disjoint edge pairs. The two possible pairing
patterns give probability at most
2 / ((m_i-1)(m_i-3)).
As e_i <= a m_i/2, their total contribution is at most
a^2 m_i^2 / (4(m_i-1)(m_i-3))
<= (16/35) sum over i of a^2.
For the last inequality use m_i/(m_i-1) <= 8/7 and
m_i/(m_i-3) <= 8/5.
If the two paired fibers instead lie in different sets X_i, X_j, then
both original edges run between those sets. There is just one
possible pairing pattern, since each pair must remain within its own
set. Put
e_ij = e_J(X_i, X_j).
There are at most binom(e_ij,2) <= e_ij^2/2 vertex-disjoint edge pairs.
Independence between the two pairings and the probability bounds
above give the contribution
sum over i<j of e_ij^2 / (2(m_i-1)(m_j-1))
<= (32/49) sum over i<j of e_ij^2/(m_i m_j)
<= (16/49) sum over i of a^2.
Indeed, for each fixed i,
sum over j not equal to i of e_ij^2/(m_i m_j)
<= (a/m_i) sum over j not equal to i of e_ij
<= a^2.
The first inequality uses e_ij <= a m_j, and the second follows from
the total degree bound on X_i. Summing over i counts each unordered
pair of sets twice.
The preceding cases exhaust distinct original edges: in a simple
graph, two distinct edges either have one common endpoint or have four
distinct endpoints.
The three error bounds give
E Z
<= (4/7 + 16/35 + 16/49) sum over i of a^2
= (332/245) sum over i of a^2
<= (332/245) sum over i of m_i
< 2 sum over i of m_i
when t > 0. Some choice of pairings has no greater error count than
its expectation.
For this choice delete each original loop edge and, in each nonloop
parallel class of size s, delete all but one original edge. The latter
requires s-1 <= binom(s,2) deletions, so the number of deleted edges is
at most Z. The remaining graph is simple after identification, and
the retained representative in each class is unique.
Deletions do not remove vertices, giving the order formula. If t = 0,
use the identity map and delete no edges. This proves the lemma.
10. RESOLVING BATCHES
We now combine the routing lemma and the pair-folding lemma. This is
the local engine that reduces a whole batch of tiny graphs while keeping
enough reserved edges to lift cycles later.
The proof runs in seven steps. Steps 10.1 and 10.2 build the quotient
Q_W from J_W: first trim edges to heavy neighbors and record demands
that will later close the trimmed paths into cycles; then pair active
vertices and fold. Steps 10.3 and 10.4 turn each quotient cycle into
switch demands and bound the total demand load at every vertex by its
degree in F. Step 10.5 applies the routing lemma once per router R.
Steps 10.6 and 10.7 check that the completed cycles are simple and
account for every edge exactly once.
The setup has several layers.
D is a large scale.
a = D^0.01,
L0 = D^0.03,
B0 = D^0.30,
sigma= D^0.90.
Y is a finite vertex set. A family W consists of subsets W of Y, each
of order at most B0. For each index W there is a simple graph J_W on W.
The edge sets of the J_W are pairwise disjoint. Let F = F(Y) be their
union, taken on Y.
A family R consists of simple graphs R on pairwise disjoint vertex
subsets of Y. Each R has order
sigma <= r_R <= D^1.02,
its edge set is disjoint from E(F), and its edges are partitioned into
two spanning graphs P_R and T_R. Both P_R and T_R have cut expansion at
least sigma/4. We call P_R the router.
For some pairs (W,R) an active set
X_{W,R} subset of W intersect V(R)
is specified. It satisfies
|X_{W,R}| >= L0,
d_F(x) <= a for every x in X_{W,R}.
Sums over (W,R) below include only active sets. Write
Sigma_Y = sum over active (W,R) of |X_{W,R}|.
LEMMA (batch resolution).
For every sufficiently large real D, with the notation above, there
are finite simple quotient graphs Q_W, with all quotient vertices
retained, whose orders satisfy
q_W = |W| - sum over active R of floor(|X_{W,R}|/2)
<= |W| - (1/3) sum over active R of |X_{W,R}|
<= B0,
sum over W of q_W
<= sum over W of |W| - (1/3) Sigma_Y.
For every choice of cycle-and-edge partitions of these Q_W, having t_W
parts, there are sets U_R subset of E(P_R) and a cycle-and-edge
partition of
E(F) disjoint union (disjoint union over R of U_R)
with at most
sum over W of t_W + 8 Sigma_Y
parts. The graphs
R' = R - U_R,
kept on V(R), contain the untouched spanning graphs T_R, so each still
has a spanning subgraph of cut expansion at least sigma/4. The
completed parts and these remaining graphs together partition
E(F) disjoint union (disjoint union over R of E(R)).
All thresholds in this lemma are absolute.
PROOF.
We first choose the quotient graphs and prepare some paths to be
closed. No router edges are used until all quotient partitions have
also been specified.
10.1 REMOVING EDGES TO HEAVY NEIGHBORS
The path trimming below is the elementary operation used by Conlon,
Fox and Sudakov. Decompose a bipartite graph into paths and remove
terminal edges so that the remaining endpoints lie on one prescribed
side. We keep the endpoint loads under the single degree bound on the
union of all batches.
Fix a batch W. Its active sets are pairwise disjoint because the
pieces R have disjoint vertex sets.
For an active set X = X_{W,R}, put
H_X = { v in W : |N_{J_W}(v) intersect X| > a },
E_X = E_{J_W}(X,H_X).
Every vertex in any active set has degree at most a in J_W, since J_W
is a subgraph of F. Thus H_X is disjoint from every active set in this
batch, including X.
If H_X is nonempty, counting edges gives
a |H_X| < |E_X|
<= sum over x in X of d_{J_W}(x)
<= a |X|.
In all cases |H_X| <= |X|.
The sets E_X for different active X are disjoint. In fact, each of
their edges has one endpoint in its specified active set and its other
endpoint outside every active set, so it cannot belong to the set
specified by a different active set.
Apply the endpoint-path corollary to the bipartite graph with parts X
and H_X and edge set E_X. It gives at most
|X| + |H_X| <= 2|X|
positive-length simple paths, since their total number of endpoint
occurrences is at most 2(|X|+|H_X|).
From each path delete its terminal edge at each endpoint belonging to
H_X, counting those deleted edges singly. At most two distinct edges
are deleted. A one-edge path has only one endpoint in H_X. If both
endpoints lie in H_X, the path has at least two edges, with distinct
terminal edges.
Ignore any remnant with no edges. Every other remnant is a simple
path with both endpoints in X: this follows directly by removing the
H_X endpoints from the alternating bipartite path. Its length is even
and at least two, so its endpoints are distinct.
For each such remnant L record a demand between its endpoints in P_R,
forbid internally the set
V(L) intersect V(R),
and give this demand its own team. Once this demand is routed, its
remnant will form one cycle.
Each original path therefore accounts for at most two single edges and
one cycle, for a total of at most 6|X| parts. We do not require an
endpoint-load-two bound for the trimmed paths; their endpoint loads
will be bounded using their incident original edges in the global load
argument below.
10.2 CHOOSING THE QUOTIENTS
Remove all the sets E_X from J_W and call the resulting graph J_W^0,
retaining the vertex set W. Each active vertex still has degree at
most a.
For each active X and every v in W, either v was in H_X, in which case
all its edges into X were removed, or it originally had at most a
neighbors in X. Hence
|N_{J_W^0}(v) intersect X| <= a
in both cases.
For large D we have
L0 >= max{8, a^2}.
Apply the pair-folding lemma to J_W^0 and its active sets. Count its
error edges singly in their original form and call the simple resulting
quotient Q_W. Denote its quotient map by pi_W. Each edge e of Q_W has
a unique retained original representative, written hat e.
The number of these single-edge parts is at most
2 sum over R of |X_{W,R}|.
Every identified pair removes exactly one vertex. Since
floor(m/2) >= m/3
for every integer m >= 2, the exact order formula from the pair-folding
lemma yields
q_W <= |W| - (1/3) sum over active R of |X_{W,R}| <= B0,
and summing yields the total order bound. This construction of all Q_W
is independent of their subsequent partitions.
10.3 THE SWITCH DEMANDS OF A QUOTIENT CYCLE
Now fix arbitrary cycle-and-edge partitions of all the Q_W. Restore
each single-edge part as its unique original representative.
For a cycle C in Q_W, list its distinct vertices in cyclic order as
z_1, ..., z_s,
where s >= 3, and write
e_j = z_j z_{j+1},
with indices interpreted cyclically.
At z_j let u_j be the endpoint of hat e_{j-1} in the fiber
pi_W^(-1)(z_j), and let v_j be the endpoint of hat e_j in that fiber.
If u_j = v_j, the two edges join without any added path.
Otherwise that fiber is a folded pair {u_j,v_j} in one active set
X_{W,R}. Record a demand from u_j to v_j in P_R.
For every demand from this cycle forbid internally
Z_C intersect V(R),
where
Z_C = union over j=1 to s of V(hat e_j).
Thus every original endpoint on the entire cycle, including the
endpoints of all its other switches, is forbidden internally.
The demands belonging to this cycle and this router form one team.
Teams for different cycles, including cycles from different batch
indices, are distinct. The single-demand teams recorded during the
heavy-neighbor work are also distinct from these teams.
10.4 THE LOAD BOUND OVER ALL BATCHES
Fix one piece R. Gather every demand for P_R from all batches and
both constructions.
Each endpoint is in an active set, hence has degree at most a in the
one graph F(Y). To bound its total demand load, associate each
occurrence of an endpoint x with an incident edge of F(Y) as follows:
For the demand closing a remnant L, use the terminal edge of L
at x.
At a switch u_j not equal to v_j, associate the occurrence of u_j
with hat e_{j-1} and that of v_j with hat e_j.
At a fixed vertex these associated incident edges are distinct.
For the first construction this follows from the edge-disjoint path
partition and from the disjointness of the designated edge sets.
For the second construction, a quotient edge belongs to exactly one
part, has exactly one original representative, and its incidence at a
given original vertex can be used only at the unique visit to its
quotient fiber in that cycle. The cycles are simple, and a switch uses
different original vertices for its two incidences.
The two constructions use disjoint edges because all designated edges
were removed before folding. Finally, edges from different batches are
distinct by hypothesis, regardless of overlap of their vertex sets or
differences in their pairings.
This proves an injection into incident edges of F(Y) and hence
number of demand-end occurrences at x
<= d_{F(Y)}(x)
<= a.
Vertices that are never endpoints have load zero.
10.5 SUPPLYING ALL THE CONNECTIONS
A team from a cycle C has at most
s <= q_W <= B0
demands, and
|Z_C| <= 2s <= 2B0.
A heavy-neighbor remnant has at most |W| <= B0 vertices; its team has
size one.
Thus in the routing lemma we may use
r = r_R,
h = sigma/4,
k = a,
b = B0,
z = 2B0.
With that lemma's definitions of g and l, the range
sigma <= r_R <= D^1.02 gives, uniformly in R,
l = O(D^0.12 log^2 D),
l^2 (a+B0) + 2B0
= O(D^0.54 log^4 D)
= o(D^0.90).
For all sufficiently large D this is at most
sigma/256 = h/64,
which is exactly enough for the routing condition. Apply the routing
lemma once to this full collection in P_R; if the collection is empty,
use no edges.
The paths supplied are pairwise edge-disjoint over all teams and all
batches for this R, and their internal vertex sets are pairwise
disjoint within each team. Do this for every piece R. The constants
are absolute, and do not depend on the number of batches or demands.
10.6 SIMPLICITY OF THE COMPLETED CYCLES
For a heavy-neighbor remnant L, its supplied path is simple and has
distinct endpoints equal to those of L. Its internal vertices avoid
V(L): the forbidden set contains V(L) intersect V(R), and all supplied
path vertices lie in V(R). The union is therefore a simple cycle. It
has at least two remnant edges and at least one supplying edge, so its
length is at least three.
For a quotient cycle C, the fibers of z_1, ..., z_s are mutually
disjoint. At a visit with u_j = v_j, its original representative edges
use one vertex. At a switch, they use the two different vertices of
that fiber and the supplied simple path joins them.
Thus, before adding path interiors, the vertices at different visits
are distinct. Every supplying path interior avoids Z_C, which includes
all these original vertices. Two supplying paths for this cycle in the
same router have disjoint interiors by their common team; paths in
different routers lie in the disjoint vertex sets of different pieces
R.
Consequently interiors of any two switches are disjoint, and none
contains an endpoint of another switch or any other original vertex
used by the cycle. Traversing the representatives and these
connections in cyclic order therefore visits no vertex twice, except
the start when closing the cycle.
An unused twin deserves explicit mention. If a visited fiber is a pair
but u_j = v_j, its other vertex need not belong to Z_C and may occur
inside a supplying path. It is absent from all original representative
edges of this cycle, since those edges use distinct fibers. If it is
used internally, no second supplying path of this cycle can use it: the
team condition excludes this in its router, and the other routers have
disjoint vertex sets. This therefore creates no repeated vertex. The
same reasoning covers vertices in fibers not visited by the cycle.
The resulting cycle contains its s distinct original representative
edges and possibly additional edges, so its length is at least s >= 3.
A quotient cycle with no switches is already a simple cycle of original
edges. Each quotient part thus yields exactly one permitted part.
10.7 EDGE ACCOUNTING AND COST
For each batch, its original edges have exactly four destinations:
(1) designated edges trimmed from paths are single-edge parts;
(2) designated edges in positive-length remnants occur in their
closed cycles;
(3) folding error edges are single-edge parts, taken before
identification;
(4) retained edges have unique representatives in Q_W and occur
once in the restored quotient parts.
These classes partition E(J_W). Empty remnants leave no unaccounted
edge, and the deletion rule for parallel classes retains exactly one
representative for each quotient edge.
Since the J_W have disjoint edge sets, every edge of F occurs once in
this list over all batches.
Let U_R be the set of edges used by all supplying paths in P_R. Each is
used once by the routing lemma. These edges are disjoint from E(F) by
hypothesis, and different routers have disjoint edge sets. Thus all
completed parts form an edge partition of the edge set in the statement.
The heavy-neighbor work contributes at most 6 Sigma_Y parts, folding
errors at most 2 Sigma_Y, and the quotient partitions contribute
exactly sum over W of t_W. Adding a supplying path changes no part
count. This proves the claimed bound.
No edge of T_R was used: U_R is a subset of E(P_R), and E(P_R) is
disjoint from E(T_R). Therefore R' = R - U_R contains the entire
spanning graph T_R on its original vertex set. The edges of R' are
precisely the edges of this assigned piece not already used in a
completed part. This proves both the remaining expansion assertion and
the final edge partition.
11. COMPLETING THE INDUCTION
We now put all the tools together. The induction statement and the
scale layers were set up in Sections 3 and 6. We repeat the main
case split here so the proof is self-contained.
The inductive step has three cases. In the two terminal cases no
prefix needs to grow, so every remaining edge is cheap. In the
scale-gap case we commit to a prefix ending at level t = i+K, fold
and route the boundary batches in each earlier box Y, and recurse
on the quotients Q_W and the tiny residuals.
Recall
theta = 0.95,
K = 200,
P0 = 4(K+1),
eta = 1/(100 P0),
and
C2 = 40 C0,
where C0 is the box-overlap constant from the scale-splitting lemma.
We may take C0 = 2.
The lower scale cutoff D_* is an absolute constant chosen to satisfy a
finite list of eventual inequalities. Only after fixing D_* do we
choose the final constant C. Every auxiliary constant introduced
before that final choice is independent of C and remains valid if the
cutoff is increased.
11.1 BASE CASE
Edgeless graphs have the empty partition.
For 1 <= n < D_*, put every edge in its own single-edge part. This
uses at most n-1 <= D_* n parts. Since phi(n) >= 1/2, it is enough to
have C >= D_*. So the base case holds.
Now suppose n >= D_*, and assume the proposition for every smaller
positive order. Put
D_j = n^(theta^j),
m = min { j >= 0 : D_j < D_* }.
Take D_* > 2. Then m is finite and positive, and the scales
D_0, ..., D_(m-1) all satisfy the cutoff.
11.2 TERMINAL CASES
We have the prospective layers from Section 6. Recall
N_j = sum over level-j boxes Y of |Y|,
S_j = sum over level-j pieces R of |V(R)|,
with S_j = 0 for j >= m.
If every S_j vanishes, keep all prospective stages. Use the long
cycles as completed parts and take the remaining edges singly.
The remaining graphs lie on the level-(m-1) boxes. Each has average
degree at most D_m < D_*. Their total number of edges is therefore
less than
N_(m-1) D_m / 2 < D_* n.
The number of long cycles removed through all levels is at most
20n / log D_(m-1) <= 20n.
So this terminal case costs at most
(20 + D_*) n
parts.
Otherwise choose an index i by the prefix-selection lemma applied to
the sequence (S_j). If
i + K >= m - 1,
again keep every stage. Retain all long cycles as completed parts and
take every edge of the final boundary graphs singly. The same estimate
as above gives at most
(20 + D_*) n
parts for the long cycles and the final single edges.
The zero extension of (S_j) ensures that
sum from j=0 to m-1 of S_j <= P0 S_i.
Apply the small-residue lemma to each piece at its own scale, with c=1
and the fixed eta. This completes at most
9 P0 S_i
parts and leaves graphs of total order at most
eta P0 S_i = S_i/100 <= n/50 < n/4.
Each individual residual graph has order at most eta r < n, where r is
the order of its parent piece: the piece's vertex set is a subset of
V(G), so r <= n, and eta < 1.
Apply the induction hypothesis to each nonempty residual graph. Their
total additional cost is at most C n/4, using phi <= 1.
Both terminal cases are therefore covered by the bound
T(D_*) n + C n/4,
where
T(D_*) = 20 + D_* + 18 P0.
For C >= 4 T(D_*), this is at most
C n/2 <= C phi(n) n.
This choice will also cover the base cases.
11.3 A PREFIX WITH A SCALE GAP
It remains to consider
i + K < m - 1.
Keep the stages through
t = i + K,
and put
D = D_i,
w = log D,
H = C2 theta^(-K),
B0 = D^0.30,
a = D^0.01,
L0 = D^0.03,
sigma = D^0.90.
Since log D_t = theta^K w, the earlier layer bounds imply
N_t <= (1 + H/w) n,
|L_t| <= H n/w.
The latter uses C2 >= 40 > 20.
Fix a level-i box Y, of order
y <= D^1.02.
Let T_Y be the sum of the orders of its level-t descendants. Each such
descendant carries its remaining graph after stage t. It has order at
most
D^(1.02 theta^K) < D^0.001,
and that graph has average degree at most
D^(theta^(K+1)).
Moreover,
y <= T_Y <= (1 + H/w) y <= 2y.
For the last inequality, note that
H/w = C2/log D_t <= 1.
Let F(Y) be the graph on Y whose edges are exactly the remaining edges
in these descendants. Their assigned edge sets are disjoint, so F(Y)
is simple and
2 |E(F(Y))|
<= T_Y D^(theta^(K+1))
<= 2 y D^(theta^(K+1)).
11.4 BATCHES AND ACTIVE SETS
Each descendant has fewer than L0 vertices. We first group descendants
to make larger folding sets possible. The batch order cap B0 keeps
quotient cycles within the routing team bound.
Partition the indexed descendants into batches whose sums of orders are
at most B0. This can be done with at most
1 + 4y/B0
batches. Require the cutoff to ensure
D^0.001 <= B0/2.
Fill a batch until the next descendant would exceed B0, then start a
new one. Every batch except possibly the last has order sum greater
than B0/2, so their number is at most
1 + 2 T_Y/B0.
For each batch let W be the union of its vertex sets, and let J_W
contain exactly its remaining assigned edges. The batch index is
retained in this notation. Denote the family by W(Y).
Thus the J_W partition E(F(Y)), the sets W cover Y, and
|W| <= B0,
sum over W in W(Y) of |W| <= T_Y,
sum over Y in Y_i sum over W in W(Y) of |W| <= N_t.
The order sums used in forming batches include all descendant
multiplicities; passing to a union within a batch can only decrease
them.
Since each level-t box has a unique indexed level-i ancestor, the batch
edge sets over all Y partition the boundary remainder. Thus, at the
boundary of the committed prefix, the assigned edge sets give the
disjoint union
E(G) =
disjoint union over L in L_t of E(L)
disjoint union
disjoint union over j=0 to t of
disjoint union over R in R_j of E(R)
disjoint union
disjoint union over Y in Y_i of
disjoint union over W in W(Y) of E(J_W).
ACTIVE SETS.
Call a vertex of Y good if its degree in F(Y) is at most a. By the
descendant-degree bound and the scale window, the number of other
vertices is at most
2 y D^(theta^(K+1) - 0.01)
<= 2 y D^(-0.009)
<= y/w,
where the final inequality is another uniform large-scale requirement.
For each W in W(Y) and each level-i piece R belonging to Y, consider
all good vertices of
W intersect V(R).
If their number is at least L0, retain this set as X_{W,R} and call it
active. Otherwise skip it. Active sets in a fixed batch are disjoint,
because the pieces in Y have disjoint vertex sets.
There are at most y/sigma such pieces. Consequently the total size of
all skipped sets in Y, counting occurrences in different batches
separately, is at most
L0 (1 + 4y/B0) y/sigma
<= y (D^(-0.87) + 4D^(-0.15))
<= y/w.
Here the exponent -0.15 uses y <= D^1.02, and the last inequality is
imposed for all scales above the cutoff.
Let s(Y) be the sum of the orders of the level-i pieces in Y, and
define
Sigma_Y =
sum over active (W,R) in Y of |X_{W,R}|,
Sigma = sum over Y in Y_i of Sigma_Y.
Every good piece vertex occurs in at least one batch, since the batches
cover Y. Choose one such occurrence per vertex. At most y/w piece
vertices are not good, and at most y/w of the chosen occurrences can
lie in skipped sets. Hence
Sigma_Y >= s(Y) - 2y/w.
For the upper bound, let u_Y(v) >= 1 be the number of batches in Y
containing v. Then
sum over v in Y of (u_Y(v)-1)
= sum over W in W(Y) of |W| - y.
Since the pieces in Y are vertex-disjoint, their excess occurrences are
bounded by this full excess. Thus
Sigma_Y <= s(Y) + sum over W in W(Y) of |W| - y.
Summing the two bounds, using N_i <= 2n, N_i >= n, and the gap and
batch bounds, gives
S_i - 4n/w
<= Sigma
<= S_i + N_t - N_i
<= S_i + H n/w.
This counts a nongood vertex only once per indexed box in the lower
bound; no bound on its number of batch occurrences is needed. Overlaps
between different boxes are already included in both S_i and N_i.
11.5 RESOLVING THE BATCHES AND THE PIECES
In every level-i piece R, apply the edge-splitting lemma with two
classes to partition its assigned edges into spanning graphs P_R and
T_R, each with cut expansion at least sigma/4. Reserve P_R as a
router and leave T_R untouched during the batch work.
All hypotheses of the batch-resolution lemma now hold in each Y. The
J_W have order at most B0 and disjoint assigned edges; their union is
F(Y). The pieces have orders between sigma and D^1.02, disjoint vertex
sets within Y, and edges disjoint from F(Y). Every vertex of an active
X_{W,R} has degree at most a in the whole F(Y), and its active set has
order at least L0. In particular the degree bound is shared across all
batches, as required by that lemma.
The lemma produces simple quotient graphs Q_W, with orders
q_W = |W| - sum over active R of floor(|X_{W,R}|/2)
<= |W| - (1/3) sum over active R of |X_{W,R}|.
Every batch has positive order and pair identifications leave at least
one vertex, so
1 <= q_W <= B0.
Also
B0 = D^0.30 <= n^0.30 < n.
Apply the induction hypothesis to these quotients, retaining isolated
quotient vertices in their order counts. The batch lemma lifts all the
resulting quotient parts simultaneously. In each Y, the additional
number of completed parts is at most 8 Sigma_Y, and the remaining graph
on every R still contains T_R. In particular, lifting a quotient cycle
produces one simple cycle and has no additional part charge.
Apply the small-residue lemma, with the fixed eta, to the remaining
graph of every level-i piece using c=1/4. Apply it to every other piece
of the committed prefix at its own scale using c=1. The total number of
parts supplied by these applications is at most
9 P0 S_i.
If H is their family of residual graphs, then
sum over H' in H of |V(H')|
<= eta sum from j=0 to t of S_j
<= eta P0 S_i.
Every nonempty member has order at most eta r < n, for the same reason
as in the terminal case. Induction applies to all of them.
Within each Y, the batch-resolution lemma resolves exactly the batch
category in the edge ledger together with the router edges it consumes.
Every consumed router edge comes from exactly one level-i piece and is
used once. The piece lemmas are applied only after those edges have
been removed, and partition all remaining piece edges into completed
parts and the members of H.
Distinct indexed boxes have disjoint assigned edge sets even when their
vertex sets overlap. Thus the only unresolved original edges after
lifting the quotient partitions are precisely the assigned edges of H,
each appearing once. Recursively partitioning them completes an edge
partition of G.
11.6 ORDER SAVINGS AND THE FINAL ESTIMATE
Define the absolute constants
A1 = H + 4/3,
A2 = max { 9P0 + 8, 9H }.
By the individual quotient order bound, the batch orders, and the
active-order bound,
sum over Y,W of q_W
<= N_t - Sigma/3
<= n - S_i/3 + A1 n/w.
The parts completed apart from the quotient partitions and the
recursive work on H number at most
|L_t| + 8 Sigma + 9 P0 S_i
<= (9P0 + 8) S_i + 9H n/w
<= A2 (S_i + n/w).
Monotonicity of phi, the bound q_W <= B0, and the piece-residual-order
bound therefore bound the complete partition size by
A2 (S_i + n/w) + C eta P0 S_i
+ C phi(B0) (n - S_i/3 + A1 n/w).
The coefficient of S_i in this expression is at most
A2 + C/100 - C/6
= A2 - 47C/300
<= 0
if C >= 7A2.
It remains to pay for the order-overlap term. Set
delta = 1/sqrt(0.30) - 1 > 0.
For w >= 40/3, both phi(n) and phi(B0) take their nonconstant values,
and log n >= w gives
phi(n) - phi(B0)
= 1/sqrt(0.30w) - 1/sqrt(log n)
>= delta/sqrt w.
For C >= 7A2, the remaining overhead in the inductive cost, beyond
C phi(B0) n, is at most
C (A1 + 1) n/w.
It is absorbed by the potential gain whenever
log D_* >= ((A1 + 1)/delta)^2.
No choice made here requires the total quotient order to be at most n;
the potential gain pays for its possible excess.
11.7 CHOOSING THE CONSTANTS
We finally specify the order of constant choices.
The parameters theta, K, P0, the scale-split constant C0 >= 1, and
hence C2, H, A1, A2, and delta, are already absolute and fixed.
Choose D_* large enough for the scale-splitting lemma, the
batch-resolution lemma, the edge-splitting lemma with two classes at
expansion D^0.90, and the small-residue lemma with the fixed eta and
c in {1, 1/4}. Also impose
log D_* >= max { C2, 40/3 },
the cutoff absorption inequality, and, for every D >= D_*,
D^(-0.01) <= 1/log D,
D^0.001 <= (1/2) D^0.30,
2 D^(-0.009) <= 1/log D,
D^(-0.87) + 4D^(-0.15) <= 1/log D.
These are uniform eventual inequalities between fixed powers and
logarithms. Such a cutoff exists independently of C.
After fixing it, choose
C >= max { 7A2, 4T(D_*) }.
The base and terminal cases then hold, and the estimates above give at
most C phi(n) n parts in the remaining case. This closes the strong
induction.
Since phi(n) <= 1, the proposition proves the main theorem for positive
order. The zero-vertex graph has the empty partition, completing all
cases.
END OF PROOF.