The Setting
Let be a graph on vertices with average degree at most , where is a large real number. Lemma 5.1 cuts at the scale . A few edge-disjoint cycles, each of length at least , are taken out first.
The library states the lemma in two forms: for each graph and each large scale, a decomposition into long cycles, boxes with their pieces, and residual graphs, and a single choice of such a decomposition for all graphs on a given vertex set at all scales at once.
Pieces, Cuts and Edge Partitions
Throughout, is a finite set and a graph on is a simple graph with vertex set ; denotes the number of edges of a graph . A graph on is supported on a set when every edge of has both ends in .✦
A piece on is a pair of a set and a graph on supported on .✦ The set may contain vertices that lie on no edge of ; its size is the order of the piece, and is the average degree of the piece.
Let be a real number. A graph on has cut expansion at least on a set when every set satisfies (1)✦ where is the number of edges of with one end in and the other in . A piece has cut expansion at least when has cut expansion at least on .
A finite family of graphs on , in which a graph may occur more than once, is an edge partition of a graph on when every pair of vertices , satisfies (2)✦ We then write .
Stage Splits
A cycle graph on is a graph on whose edges are exactly the edges of one cycle of .✦
A stage split of a piece on consists of a finite family of cycle graphs on , a finite family of pieces on , called boxes, and, for each box, a finite family of pieces on , called the pieces of the box, and a graph on , called its residual graph, such that (3)✦ and such that every is a subset of , nonempty when is, the sets cover , the sets of the pieces of each box are pairwise disjoint subsets of , and each is supported on .
For a real number , with the logarithm to base , a stage split of a piece is bounded at scale when (4)✦ and when every box has order at most , every piece of a box has order between and and cut expansion at least , and the residual graph of every box satisfies .
The Claim
Theorem 1. There is a real number with the following two properties.
(a) Let be a real number, and let be a piece on a finite set with nonempty and average degree at most . Then has a stage split that is bounded at scale and whose family of cycle graphs satisfies (5)✦
(b) Let be a finite set. There is a choice, for every real number and every piece on , of a stage split of such that (6)✦
In the paper, the result reads: there are absolute constants and , where one may take , such that for every real , every graph on a nonempty vertex set of order with average degree at most admits a family of edge-disjoint cycles of length at least with and a partition of the remaining edges into graphs on boxes covering with and , and, for each box , a partition of into graphs on pairwise disjoint sets , each of cut expansion at least and of order , and a residual graph on all of with , the cycles, pieces and residual graphs together partitioning .
What Is Checked
The claims (5) and (6) are stated over pieces on a finite set and their cut expansion (1), edge partitions (2), cycle graphs, and stage splits (3) with their boundedness (4) at scale .