The Setting
Let be a graph on vertices with cut expansion at least , that is, every set of vertices sends at least edges to the rest, and colour its edges with colours; the edges crossing any such cut are then shared among the sets of edges of one colour. The question is whether the colouring can be chosen so that every colour class still has cut expansion at least , half of the that an even share of every cut would give it.
The question is posed at a large real scale , which bounds the order of and its expansion by powers of , with a constant and the number of colours fixed as grows.
Cut Expansion and Colour Classes
Graphs are simple, on a finite vertex set. For a graph on and a set , is the set of edges of with one end in and the other in . A graph on a vertex set of size has cut expansion at least a real number if every satisfies (1)✦
Let be a graph on , and let assign to every pair of vertices of one of the colours . The colour class of colour is the spanning subgraph of on whose edges are the edges of of colour : (2)✦
The Claim
Theorem 1. Let be a real number and a positive integer. For every sufficiently large real number the following holds. Let be a graph on a vertex set of size with , and let be a real number such that has cut expansion at least . Then there is a colouring of the pairs of vertices of with the colours whose colour classes satisfy (3)✦
In the paper, the result reads: for fixed and a positive integer and all sufficiently large , if an -vertex graph has cut expansion at least and , then its edge set can be partitioned into spanning subgraphs, each with cut expansion at least .
What Is Checked
The claim (3) is stated over graphs on a finite vertex set, their cut expansion (1), and the colour classes (2) of a colouring of the pairs of vertices with colours, for real numbers , and and a positive integer .