The Setting
Let be a graph on a vertex set of order . The decomposition cost of is the least number of parts in a partition of into edge sets of cycles of and single edges of .
Here is large and well connected on a scale set by a parameter : its order lies between two powers of , and contains a spanning subgraph whose cut expansion, the least ratio of the number of edges leaving a nonempty proper vertex set to the size of the smaller of its two sides, is at least a constant times a power of . The question is how few vertices can carry the edges of left over by at most pairwise edge-disjoint cycles and single edges of .
Cycle-or-edge Sets and Cut Expansion
A cycle-or-edge set of a graph on a vertex set is a set of unordered pairs of vertices of that is either the edge set of a cycle of or the set of a single edge of .✦
For a graph on a finite vertex set and a set , the edge boundary is the set of edges of with one end in and the other in . A graph on a finite vertex set of order has cut expansion at least a real number if (1)✦
The Claim
Theorem 1. Let and be positive reals. There is a real number with the following property. Let , let be a graph on a vertex set of order with , and suppose that contains a spanning subgraph of cut expansion at least . Then there are an integer , cycle-or-edge sets of , subgraphs of and sets , each containing both ends of every edge of , such that the sets are pairwise disjoint and (2)✦
In the paper, the result reads: for fixed and and all sufficiently large , if is an -vertex graph with containing a spanning subgraph of cut expansion at least , then has a partition into at most completed parts, each a simple cycle or a single edge, and the edge sets of at most three residual simple graphs on pairwise disjoint subsets of , each of order less than , with total order at most . The completed parts correspond to the cycle-or-edge sets of the theorem. The theorem has exactly three residual graphs , , , any of which may have no edges, and allows the sets , , to overlap.
What Is Checked
The claim (2) is stated over graphs on a finite vertex set, the cycle-or-edge sets of such a graph, and cut expansion (1).