The Setting
Graphs are simple graphs on a finite vertex set; is the vertex set of a graph , its edge set and its number of edges. A cycle-and-edge partition of into parts is a partition of into pairwise disjoint 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.
Given a bound of parts per vertex for every graph of smaller order, the question is what the pieces defined below cost and what layers of a piece, at scales that fall from its order down to a cutoff , give for its cost.
Pieces and Stage Splits
Fix a finite vertex set . A graph on is supported on a set of vertices when every edge of has both ends in .✦ A piece on is a set of vertices together with a graph on supported on .✦ The set may contain isolated vertices of , and the order of is .
A cycle graph on is a graph on whose edges are exactly the edges of one cycle in .✦ A list of graphs on is an edge partition of a graph on when, for any two vertices and , the number of members of in which and are adjacent, a member listed twice counted twice, is if is an edge of and otherwise.✦
For a real number , a graph on has cut expansion at least on a set of vertices when (1)✦ where is the number of edges of with one end in and the other in .
A stage split of a piece on consists of cycle graphs on , its cycles, and a list of pieces, its boxes, whose vertex sets lie in , are nonempty when is, and cover .✦ With each box come a list of pieces, the pieces of , whose vertex sets lie in and are pairwise disjoint, and a graph on supported on , the remainder of . The cycles and the graphs of the boxes together form an edge partition of , and for each box the remainder and the graphs of the pieces of together form an edge partition of .
For a real number , a stage split of is bounded at scale when it has at most cycles, every piece of every box has and a graph of cut expansion at least on , and the boxes satisfy (2)✦ where is the logarithm to base , the sum runs over all boxes, and the other two bounds hold for every box .
Layers
Let .✦ The scales at a real number are the numbers for .✦
A split system on assigns to every stage and every piece on a stage split of .✦ Given and a piece , the frontier at layer is a list of pieces: consists of alone, and is the list of the boxes of the stage splits , , listed one after another.✦
The pieces of level of a list of pieces are the pieces of all the boxes of the stage splits , , listed one after another.✦ Write for the pieces of level of , and for the pieces from the first layers, the lists in turn. Write for the list of the cycles of the stage splits with and , and for the number of its members.✦
The vertex mass of a list of pieces is , a piece listed several times counted each time.✦ The frontier mass at layer is , the total order of the pieces of the frontier . The piece mass at layer is ✦, the total order of the pieces of level of the frontier .
Layered splitting data for a piece of order on at a cutoff , a real number, consist of a split system on and an integer , the number of layers, such that, with the scales at and the frontiers of and , (3)✦ the stage split is bounded at scale for every and every , and for every and every .
For real numbers and , the scale is -ready when , and (4)✦
The constant is , with .✦
The Claim
Theorem 1. There is a real number such that (a), (b) and (c) hold for every piece on a finite vertex set and every real number , and (d) holds for every such and every real number . In (b), (c) and (d), layered splitting data for at cutoff are given, with layers; are the scales at , and , , and are those of the data.
If (5)✦ then has layered splitting data at cutoff .
Let be such that for every graph with . Then, for every , every piece in satisfies (6)✦
Let , let every scale with be -ready, and let be a natural number with . Let be such that every graph with has , and has if also . If every piece in satisfies , then (7)✦
Let and let every scale with be -ready. If is a real number with for every piece in , then (8)✦
What Is Checked
The claim is stated over the decomposition cost , pieces and their stage splits bounded at a scale, and layered splitting data at a cutoff with their frontiers , the lists and , the vertex masses and , the -ready scales and the constant .