Frankl–Rödl graph

The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices.

[1] They have since become of interest to computational complexity theorists, as difficult examples for semidefinite programming based approximation algorithms for the vertex cover and graph coloring problems.

Their properties with respect to these algorithms have been used to call into question the unique games conjecture.

is the graph on the 2n vertices of an n-dimensional unit hypercube [0,1]n in which two vertices are adjacent when their Hamming distance (the number of coordinates in which the two differ) is exactly (1 − γ)n.[2] Here, the requirement that (1 − γ)n be even is necessary in order to prevent the result from being a bipartite graph.

, are each formed from two copies of the two complementary Clebsch graphs of degree five and ten respectively.

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

For constant values of γ and variable n, this independent set size is a small fraction of the 2n vertices of the graph.

The vertex cover problem involves finding a set of vertices that touches every edge of the graph.

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.

[5][6][7] 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.