The Setting
A cycle-and-edge partition of a graph is a partition of the edge set of into parts, each the edge set of a cycle of or a single edge of ; Erdős and Gallai conjectured that every graph on vertices has one with parts. The induction toward such a partition cuts a graph in layers. At the first layer the graph, of size , is split as in Lemma 5.1 of the preprint “A linear cycle-and-edge decomposition of every graph” (the paper), taking out a few cycles and leaving smaller pieces of large cut expansion; each of these is split again at a smaller size scale, layer after layer, until the scale falls below a cutoff.
The library defines the scales, the layers of splits down to a cutoff, and a potential of one real variable used by the induction.
Pieces and Splits
Fix a finite set of vertices. A graph on is supported on a set when every edge of has both ends in .✦ A piece on is a set together with a graph on supported on ; the set may hold isolated vertices of , and the order of is .✦
Write for the number of edges of a graph ✦ and, for , for the number of edges of between and ✦. The graph has cut expansion at least on when for every .✦
Given a graph on , a sequence of graphs on is an edge partition of when every edge of lies in exactly one of and none of them has an edge outside .✦ A cycle graph on is a graph on whose edges are exactly those of one cycle, every other vertex being isolated.✦
A stage split of a piece consists of cycle graphs on , a sequence of pieces called boxes, and for each box a sequence of pieces, the pieces of , together with a graph on supported on , the remainder of .✦ The vertex sets of the boxes lie in , are nonempty when is, and cover ; the pieces of each box have pairwise disjoint vertex sets inside . The graphs and the graphs of the boxes form an edge partition of , and for each box the remainder and the graphs of the pieces of form an edge partition of .
Given a real number , a stage split of is bounded at scale when, with the base 2 logarithm, (1)✦ for every box and every piece of , and every such has cut expansion at least on .
A split system on assigns to every stage and every piece on a stage split of .✦ A split system on generates from a piece on layers of pieces: the layer is alone, and consists of the pieces of the boxes of the stage splits for .
The Definition
Definition 1. The potential is the function on the real numbers given by (2)✦ The scale exponent is the real number (3)✦ and the scale at a real number and a layer is (4)✦ Let be a piece on of order , let be a real number, and let be the scales at . Layered splitting data for at the cutoff consist of a split system on and an integer such that (5)✦
In the paper, the result reads: and for , and with .
What Is Checked
The definitions (2), (3) and (4) are stated over the real numbers, and (5) over a piece on a finite vertex set and a real cutoff, with split systems on that set whose stage splits are held to the bounds (1) along the layers.