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

The Frankl–Rödl graph ${\displaystyle \operatorname {FR} _{1/2}^{4}}$ consists of two copies of the

cocktail party graph K_2,2,2,2.

The Frankl–Rödl graph ${\displaystyle \operatorname {FR} _{1/5}^{5}}$ consists of two copies of the 5-regular Clebsch graph.

Let n be a positive integer, and let γ be a real number in the

${\displaystyle \operatorname {FR} _{\gamma }^{n}}$

As an example, the Frankl–Rödl graph ${\displaystyle \operatorname {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

. Similarly, the Frankl–Rödl graph ${\displaystyle \operatorname {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, ${\displaystyle \operatorname {FR} _{1/5}^{5}}$ and ${\displaystyle \operatorname {FR} _{3/5}^{5}}$, are each formed from two copies of the two

Properties

The Frankl–Rödl graph ${\displaystyle \operatorname {FR} _{\gamma }^{n}}$ is a regular graph, of degree

${\displaystyle {\binom {n}{(1-\gamma )n}}.}$

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

As Frankl & Rödl (1987) showed,^[3] when γ ≤ 1/4, the size of a

${\displaystyle \operatorname {FR} _{\gamma }^{n}}$

${\displaystyle n(2-\Omega (\gamma )^{2})^{n}.}$

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

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.[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.^[2]

References