Maximum D(n,k) asymptotics in IS reconfiguration

Question 8 · arXiv:2301.02020

arXiv Question high confidence— first stated 2023-01-05

Authors: Nicolas Bousquet, Bastien Durain, Théo Pierron, Stéphan Thomassé

Status open high confidence

The source paper establishes D(n,k) = Ω(2^{n/5}) for the range 3n/10 ≤ k ≤ 2n/5, giving an exponential lower bound on max_k D(n,k), and leaves the precise asymptotics as Question 8. No follow-up paper resolving or improving this asymptotic question was found in searches covering arXiv and published literature through May 2026.

Reviewer notes. No follow-up work addressing the asymptotic behavior of max_k D(n,k) was found. The source paper itself is the state of the art: it proves the exponential lower bound D(n,k) = Ω(2^{n/5}) for k in [3n/10, 2n/5], which implies max_k D(n,k) grows at least exponentially in n, but the exact asymptotic (upper and matching lower bound) remains open.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. What is the asymptotic behavior of $\max_k D(n, k)$?

Context

The authors prove that for every $n$ and every $k$ with $3n/10 \leq k \leq 2n/5$, $D(n,k) = \Omega(2^{n/5})$, and remark that it is quite surprising that this exponential lower bound holds for such a wide range of values of $k$.

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