The Setting
Let be a graph on a vertex set of order , and let be a spanning subgraph of in which every set of vertices sends many edges to its complement. The reservoir steps of the proof of Lemma 4.3 of the OpenAI preprint on a linear cycle-and-edge decomposition of every graph colour the edges of with three colours and give each colour class a reservoir: a small set of vertices, well connected inside the class, to which every vertex outside the set is joined by two edges of the class, its spokes.
The first step builds the colouring and the reservoirs from the expansion of , for a large parameter , so that the classes and the reservoirs inside them still expand. The second step starts from edge-disjoint sets of edges of , the completed parts, covering every edge of except the spokes and the edges of each class inside its reservoir; it bounds the number of parts and of unused spokes, the spokes lying in no completed part, and places the edges still uncovered inside the reservoirs.
Cut Expansion, Colour Classes and Spokes
A graph on a vertex set of order has cut expansion at least a real number if (1)✦ where is the number of edges of between and . A graph on has cut expansion at least on a set if (2)✦ where is the number of edges of with one end in and the other in .
A colouring of the pairs of vertices with three colours gives each unordered pair of vertices one of the colours . The colour class of a graph on under is the spanning subgraph of whose edges are the edges of that colours .✦
For constants , the reservoir expansion coefficient and the reservoir sampling probability are (3)
The spokes of a set of vertices under a map are the pairs with and .✦ The set of all reservoir spokes of three sets under maps is (4)✦
The edges of a graph inside a set of vertices are the edges of with both ends in , the edge set of the subgraph of induced on .✦
For a family of sets of edges, the completed parts, the set of completed edges is the union .✦ The unused spokes form the set .✦
The restriction of to a set of pairs of vertices is the spanning subgraph of whose edges are the edges of in .✦ Given graphs on , sets of vertices and completed edges , the residual graph is the restriction of to .
The Claim
Theorem 1 (Reservoir preparation). Let , with and as in (3). There is a real number such that the following holds for every . Let be a graph on a vertex set of order with , and let be a spanning subgraph of of cut expansion at least . Then there are a colouring of the pairs of vertices with three colours, whose colour classes of are edge-disjoint subgraphs of , pairwise disjoint sets of vertices with , and maps from to , such that for each colour (5)✦
Theorem 2 (Reservoir remainder). Let be a graph on a vertex set of order , let be pairwise edge-disjoint subgraphs of , let be sets of vertices, the reservoirs, and let be maps from to such that is an edge of for every and , with the set of spokes (4). Let be at most pairwise disjoint sets of edges of whose union contains every edge of outside and outside . Then (6)✦ and the edges of outside are the edges of the residual graphs .
What Is Checked
The claims (5) and (6) are stated over graphs on a finite vertex set and their spanning subgraphs, cut expansion (1) and cut expansion on a set (2), the colour classes of a colouring of the pairs with three colours, the reservoir expansion coefficient and sampling probability (3), the spoke set (4) and the edges inside a reservoir, and the completed edges, unused spokes and residual graphs of a family of completed parts.