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

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 k8k\geq8 with k{9,11,16,18,25}k\notin\{9,11,16,18,25\}. The independence ratio conjecture.

α({1,k,k+7})={4k+279k+72if k0(mod9),49if k1(mod9),4k+289k+72if k2(mod9),8k+2118k+63if k3(mod9),4k+299k+72if k4(mod9),4k29k+9if k5(mod9),4k+309k+72if k6(mod9),4k+269k+72if k7(mod9),4k+319k+72if k8(mod9).\overline{\alpha}(\{1,k,k+7\})= \begin{cases} \frac{4k+27}{9k+72} & \text{if } k\equiv0\pmod9,\\ \frac49 & \text{if } k\equiv1\pmod9,\\ \frac{4k+28}{9k+72} & \text{if } k\equiv2\pmod9,\\ \frac{8k+21}{18k+63} & \text{if } k\equiv3\pmod9,\\ \frac{4k+29}{9k+72} & \text{if } k\equiv4\pmod9,\\ \frac{4k-2}{9k+9} & \text{if } k\equiv5\pmod9,\\ \frac{4k+30}{9k+72} & \text{if } k\equiv6\pmod9,\\ \frac{4k+26}{9k+72} & \text{if } k\equiv7\pmod9,\\ \frac{4k+31}{9k+72} & \text{if } k\equiv8\pmod9. \end{cases}

These values are conjectured from computed independence ratios for similar distance graphs; the source gives no proof or resolution for this family.

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.