The Setting
Let be a graph of order with and cut expansion at least , where is a constant and is a large parameter. Keep each vertex of independently with probability , a constant in , and let be the set of kept vertices. The question is how much of the expansion of survives in the induced subgraph once is large, with a bound on the failure probability that holds for all such at once.
Cut Expansion
A graph on a finite vertex set of order has cut expansion at least a real number when every set satisfies (1)✦ where is the number of edges of with one end in and the other in .
For a set , a graph on has cut expansion at least on when its induced subgraph has cut expansion at least : every satisfies (2)✦ where is the number of edges of with one end in and the other in .
Random Vertex Samples
Bernoulli vertex sampling with parameter on a finite set is the product probability measure on under which the coordinates , , are independent and each equals with probability .✦ The sampled vertex set of a point is .✦
For a graph on , the set of neighbours of a vertex in a set is the set of vertices of adjacent to .✦
Let be a graph on of order , and let , and be real numbers. A point is a good vertex sample for with parameters , , when its sampled vertex set satisfies (3)✦ and has cut expansion at least on .
The Claim
Theorem 1. Let , and be real numbers. There is a real number , depending only on , and , with the following property. Let , and let be a graph on a finite vertex set whose order satisfies and which has cut expansion at least . Then, for drawn from Bernoulli vertex sampling with parameter on , (4)✦
In the paper, the result reads: fix and , let have order and cut expansion at least , and select each vertex independently with probability to form ; then with probability as , , for every , and has cut expansion at least , the error being uniform over the stated graphs and orders.
What Is Checked
The claim (4) is stated over graphs on a finite vertex set and their cut expansion (1), over Bernoulli vertex sampling and the sampled vertex set, and over good vertex samples (3), built from the neighbours of a vertex in a set and from cut expansion on a set of vertices (2).