Independence ratio conjecture for the distance graphs {1,6,k}\{1,6,k\}

Let G(S)G(S) be the distance graph on the integers with generating set SS, and let α(S)\overline{\alpha}(S) denote its maximum density of an independent set. Let k>6k>6 with k{7,10,12,17}k\notin\{7,10,12,17\}. The independence ratio conjecture.

α({1,6,k})={3k7k+7if k0(mod7),37if k1(mod7),3k+17k+7if k2(mod7),3k27k+7if k3(mod7),3k+27k+7if k4(mod7),3k17k+7if k5(mod7),37if k6(mod7).\overline{\alpha}(\{1,6,k\})= \begin{cases} \frac{3k}{7k+7} & \text{if } k\equiv 0\pmod{7},\\ \frac{3}{7} & \text{if } k\equiv 1\pmod{7},\\ \frac{3k+1}{7k+7} & \text{if } k\equiv 2\pmod{7},\\ \frac{3k-2}{7k+7} & \text{if } k\equiv 3\pmod{7},\\ \frac{3k+2}{7k+7} & \text{if } k\equiv 4\pmod{7},\\ \frac{3k-1}{7k+7} & \text{if } k\equiv 5\pmod{7},\\ \frac{3}{7} & \text{if } k\equiv 6\pmod{7}. \end{cases}

The source notes that the proposed extremal sets are proved for all residue classes except k3(mod7)k\equiv3\pmod 7, so the displayed formula remains conjectural in that class.

Sources & referencesView supporting material

Primary source

James M. Carraher, David Galvin, Stephen G. Hartke, A. J. Radcliff and Derrick Stolee, “On the independence ratio of distance graphs”, arXiv:1401.7183 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.