The Setting
Let be a graph of order whose vertex sets expand, expansion being counted in vertices rather than in edges as in cut expansion. The question is how long a cycle, and how long a path, must contain, in terms of and the rate at which its vertex sets expand.
Vertex Expansion
The external neighbourhood of a set of vertices of is the set of vertices of outside that are adjacent to at least one vertex of : (1)✦
For a real number , a graph of order has vertex expansion at least when every nonempty set of at most vertices has at least vertices in its external neighbourhood: (2)✦
The Claim
Theorem 1. Let be a real number and let be a graph of order with vertex expansion at least .
If and , then contains a cycle of length , where (3)✦
There are distinct vertices of , each adjacent to the next, where (4)✦
In the paper, the result reads: with , for every sufficiently large integer and , a graph of order in which for every with contains a cycle of length greater than .
The box asks of only that and , which the paper’s satisfies for every large .
What Is Checked
The two statements in the box are stated over a graph of order and a real number , through the external neighbourhoods (1) of the vertex sets of and the condition that has vertex expansion at least as in (2).