The Setting
The induction of Section 7 cuts a graph into pieces scale by scale. It starts from a piece of order and works at layer at the scale for a fixed : every piece reached at that layer is split into cycles and boxes, and every box into pieces of large cut expansion and a sparse remainder. Let be the total order of the pieces of large cut expansion made at layer .✦ The item asks for a layer with whose pieces carry a fixed share of all pieces made in layers through .
The library states the result for every integer , with in place of , and, with , for the layers of the induction.
Pieces and Stage Splits
Fix a finite ground set . A graph on is supported on a finite set when every edge of has both ends in .✦ A piece on is a finite set , the vertices assigned to , together with a graph on supported on ; the set may hold isolated vertices, and its size is the order of .✦ For a graph on , is the number of edges of , and for a piece on , is the number of edges of the graph of .
A list of graphs on is an edge partition of a graph on when every edge of is an edge of exactly one member of and no member of has an edge outside , a graph occurring twice in counted twice.✦ A cycle graph on is a graph on whose edges are exactly those of one cycle in it.✦ A graph on has cut expansion at least on a set when (1)✦ where is the number of edges of with one end in and the other in .
A stage split of a piece consists of a list of cycle graphs, its cycles; a list of pieces, its boxes; and for every box a list of pieces, the pieces of , and a graph supported on the vertex set of , the remainder of .✦ The vertex sets of the boxes lie inside that of , are nonempty when that of is, and together cover it. The pieces of a box have pairwise disjoint vertex sets inside that of , and their graphs together with form an edge partition of the graph of . The cycles and the graphs of the boxes form an edge partition of the graph of .
A stage split of is bounded at scale when it has at most cycles, the orders of its boxes sum to at most , with the base logarithm, and every box and every piece of satisfy (2)✦ the graph of having cut expansion at least on the vertex set of .
A split system on assigns to every level and every piece on a stage split of .✦
Layers and Piece Mass
For a piece of order , the induction scale at layer is ✦, with the scale exponent ✦. Given a split system , the frontier at layer is a list of pieces: is alone, and is obtained from by splitting every piece of with the stage split .✦
Layered splitting data for at threshold consist of a split system and a number of layers with for and , such that for the stage split of every piece of is bounded at scale , and for every piece of has .✦
The vertex mass of a list of pieces is the sum of their orders, a piece counted as often as it occurs.✦ The pieces of level of a list of pieces are the pieces of all boxes of the stage splits , in .✦ For a piece with a split system , the piece mass of at layer is the vertex mass of the pieces of level of .✦ The pieces from the first layers, those of level of for , have vertex mass . The constant in (4) is at .✦
The Claim
Theorem 1. Let be an integer and a sequence of nonnegative reals that vanishes from some index on and is not identically zero. Then some index has and (3)✦ Let be a piece with layered splitting data of layers at a threshold , and let be its piece mass at layer . If , then some layer has and (4)✦
In the paper, the result reads: if is a nonnegative, finitely supported sequence that is not identically zero, there is an index with and , where and .
What Is Checked
The claim (3) is stated over nonnegative real sequences that vanish from some index on, and (4) over layered splitting data for a piece: a split system whose stage splits are bounded at the induction scales , the frontiers it reaches, and the piece masses of its layers.