The Setting
All graphs are simple graphs on finite vertex sets. The order of a graph is the number of vertices of the vertex set that is on, isolated vertices included. A cycle-and-edge partition of a graph into parts is a partition of into sets, each the edge set of a cycle of or a single edge of .✦ The decomposition cost of is the least for which has a cycle-and-edge partition into parts.✦
The lemma is a step of an induction on the order that bounds the decomposition cost by a multiple of the order. The edges of a graph are shared among batches , each on a small vertex set , and beside lie routers, graphs of large cut expansion on pairwise disjoint vertex sets. In each batch, sets of vertices of low degree, the active sets, each inside the vertex set of one router, are paired off and each pair is identified to one vertex; the batch folds to a quotient of smaller order, to which the induction applies. The question is how much order the folding saves, and how many extra parts it takes to turn cycle-and-edge partitions of the quotients into a partition of , with some router edges, into cycles and single edges.
Pairings and Folded Quotients
A pairing of a set is a fixed-point-free involution of : and for every .✦ The quotient of by a pairing is the set of classes of the equivalence relation (1)✦ and each of its classes is a pair . The projection of onto sends each element to its class.✦
For a finite set , let be itself when is even and with one new point added when is odd. A padded pairing of is a pairing of .✦
Let be pairwise disjoint subsets of a finite set , indexed by a finite set , and let be padded pairings of the . The folded quotient is the disjoint union (2)✦ of the vertices outside all the and the pairs of each . The projection fixes each vertex outside all the and sends a vertex of to its class in .✦ For an edge of a graph on , is the pair .
Prepared Batches
Let be a graph on and pairwise disjoint subsets of . A prepared batch for and consists of padded pairings of the , a graph on , the quotient of the batch, a set of retained edges and a set of set-aside edges of , and, for each , at most paths of , each of length at least with both ends in , such that:✦
the paths, over all , are pairwise edge-disjoint, and is the disjoint union of , and the edge sets of the paths;
the edges of are the pairs with , and each edge of is for exactly one ;
the set and the order of satisfy (3) (4)
Cut Expansion on a Set
A graph on has cut expansion at least a real number on a set if (5)✦ where is the number of edges of with one end in and the other in .
The Claim
Theorem 1.
Let be pairwise disjoint subsets of a finite set , each with at least two elements, and let be padded pairings of the . Then (6)✦
Let be a graph on a finite set , let be pairwise disjoint subsets of , and let be real. If for every and every (7)✦ then and have a prepared batch.
There is a real such that the following holds for every . Let be a subgraph of a graph on , and let be pairwise disjoint subsets of , with finite and . Let , with finite, be pairwise edge-disjoint subgraphs of whose edge sets cover , and let be sets with such that every edge of has both ends in . For each , let , with finite, be pairwise disjoint subsets of , each contained in one of the sets and such that for every .
Let be pairwise edge-disjoint subgraphs of , each edge-disjoint from and of cut expansion at least on . For each , let a prepared batch for and be given whose quotient has a cycle-and-edge partition into parts. Then there are a set of edges of the graphs , disjoint from , and a partition of into parts, each the edge set of a cycle of or a single edge of , with (8)✦
Let be pairwise edge-disjoint subgraphs of , each edge-disjoint from , with all its edges inside and of cut expansion at least on , such that . Suppose that and for all and , that is an integer with for every , and that is a real number such that for every graph with and . Then there are subgraphs , each of cut expansion at least on , such that (9)✦
In the paper, the result reads: for every sufficiently large real , with , , and , let be the union of graphs with pairwise disjoint edge sets, each on a set of at most vertices of a finite set , let be graphs on pairwise disjoint subsets of , of orders between and and edge-disjoint from , each with its edges split into two spanning graphs, the router and , both of cut expansion at least , and for some pairs let an active set with and for be given, with ; then there are quotient graphs of order , so that , such that for every choice of cycle-and-edge partitions of the into parts there are sets and a cycle-and-edge partition of into at most parts, each still contains and so a spanning subgraph of cut expansion at least , and these parts together with the graphs partition . The library states the lemma in the four parts above, with the quotients taken from prepared batches.
What Is Checked
The claim is stated over graphs on finite vertex sets and their paths, padded pairings of pairwise disjoint vertex sets with the folded quotient and its projection , prepared batches, cut expansion on a set, cycle-and-edge partitions into parts and the decomposition cost . Beyond the claim, the library proves that, for pairwise disjoint , is the disjoint union of the vertices outside all the and the sets .✦