Frankl–Rödl graph

Definition and examples

Let n be a positive integer, and let γ be a real number in the unit interval 0 ≤ γ ≤ 1. Suppose additionally that (1 − γ)n is an even number. Then the Frankl–Rödl graph FR γ n is the graph on the 2ⁿ vertices of an n-dimensional unit hypercube [0,1]ⁿ in which two vertices are adjacent when their Hamming distance (the number of coordinates in which the two differ) is exactly (1 − γ)n. Here, the requirement that (1 − γ)n be even is necessary in order to prevent the result from being a bipartite graph. The Frankl–Rödl graph will necessarily be disconnected (with at least one connected component for each of the two sides of the bipartition of the corresponding hypercube graph) but this is non-problematic for its applications.

As an example, the Frankl–Rödl graph FR 1 / 3 3 connects vertices two steps apart in an ordinary three-dimensional cube, as shown in the illustration. Geometrically, this connection pattern forms a shape known as the stella octangula; graph-theoretically, it forms two connected components, each of which is a four-vertex complete graph. Similarly, the Frankl–Rödl graph FR 1 / 2 4 connects vertices two steps apart in a four-dimensional hypercube, and results in a graph consisting of two copies of the cocktail party graph K_2,2,2,2. The two Frankl–Rödl graphs of dimension five, FR 1 / 5 5 and FR 3 / 5 5 , are each formed from two copies of the two complementary Clebsch graphs of degree five and ten respectively.

Properties

The Frankl–Rödl graph FR γ n is a regular graph, of degree

It inherits the symmetries of its underlying hypercube, making it a symmetric graph.

As Frankl & Rödl (1987) showed, when γ ≤ 1/4, the size of a maximum independent set in a Frankl–Rödl graph FR γ n is

The Ω in this formula is an instance of big Ω notation. For constant values of γ and variable n, this independent set size is a small fraction of the 2ⁿ vertices of the graph. More precisely, this fraction is inversely proportional to an exponential function of n and a polynomial function of the graph size. Because each color in proper coloring of the Frankl–Rödl graph forms an independent set with few vertices, the number of colors must be large (again, a polynomial function of the graph size).

In computational complexity

The vertex cover problem involves finding a set of vertices that touches every edge of the graph. It is NP-hard but can be approximated to within an approximation ratio of two, for instance by taking the endpoints of the matched edges in any maximal matching. Evidence that this is the best possible approximation ratio of a polynomial-time approximation algorithm is provided by the fact that, when represented as a semidefinite program, the problem has an integrality gap of two; this gap is the ratio between the solution value of the integer solution (a valid vertex cover) and of its semidefinite relaxation. According to the unique games conjecture, for many problems such as this the optimal approximation ratio is provided by the integrality gap of their semidefinite relaxation. However, the Frankl–Rödl graphs provide the only known instances of vertex cover for which the integrality gap can be as bad as two.

Frankl–Rödl graphs have also been used to study semidefinite approximations for graph coloring. In this application, in particular, researchers have studied graph 3-colorability in connection with the Frankl–Rödl graphs with parameter γ = 1/4. Even though the Frankl–Rödl graphs with this parameter value have high chromatic number, semidefinite programming is unable to distinguish them from 3-colorable graphs. However, for these graphs, algebraic methods based on polynomial sums of squares can provide stronger bounds that certify their need for many colors. This result challenges the optimality of semidefinite programming and the correctness of the unique games conjecture.