Super-cubic diameter of 4-configuration graph
Conjecture 4 · arXiv:2301.02020
Status open high confidence
Conjecture 4 from arXiv:2301.02020 asserts $D(n,4) = n^{3-o(1)}$, i.e., the maximum diameter of the 4-independent-set reconfiguration graph on $n$ vertices is nearly cubic. The source paper (published in Electronic Journal of Combinatorics 2023) establishes the upper bound $D(n,4) = o(n^3)$ and the general lower bound $n^{2\lfloor k/3\rfloor}/e^{O_k(\sqrt{\log n})}$, which for $k=4$ gives only $\Omega(n^2/e^{O(\sqrt{\log n})})$, leaving a large gap. A comprehensive web search found no follow-up paper proving or disproving the conjecture.
Reviewer notes. No follow-up found. The conjecture asks whether the 4-configuration graph can have super-quadratic (nearly cubic) diameter; the gap between the $\Omega(n^2/e^{O(\sqrt{\log n})})$ lower bound and $o(n^3)$ upper bound remains open. The paper was also published as Electronic Journal of Combinatorics, Volume 30, Issue 3 (2023), article P3.8.
Context
The authors prove $D(n,3) = \Omega(n^2/e^{O(\sqrt{\log n})})$ and a general lower bound $D(n,k) = n^{2\lfloor k/3\rfloor}/e^{O_k(\sqrt{\log n})}$, but were unable to show that lower and upper bounds almost match for $k \geq 4$. In particular, it is open whether the 4-configuration graph can have super-quadratic diameter, while the upper bound is $o(n^3)$.
Source paper
Extremal Independent Set Reconfiguration
Nicolas Bousquet, Bastien Durain, Théo Pierron, Stéphan Thomassé · 2023-01-05
https://arxiv.org/abs/2301.02020
PDF source