Frankl–Rödl graph

In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at a specified even distance from each other. The graphs of this type are parameterized by the dimension of the hypercube and by the distance between adjacent vertices.

Frankl–Rödl graphs are named after Péter Frankl and Vojtěch Rödl, who proved in 1987 that (for certain ranges of the graph parameters) they have small independence number and high chromatic number. 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.

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 ${\displaystyle \operatorname {FR} _{\gamma }^{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.

...
Wikipedia