Extremal independent set reconfiguration (Q6133144)

Summary: The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on independent sets are widely studied: for example, it is well known that an \(n\)-vertex graph has at most \(3^{n/3}\) maximum independent sets (and this is tight). This paper investigates the asymptotic behavior of maximum possible length of a shortest reconfiguration sequence for independent sets of size \(k\) among all \(n\)-vertex graphs. We give a tight bound for \(k=2\). We also provide a subquadratic upper bound (using the hypergraph removal lemma) as well as an almost tight construction for \(k=3\). We generalize our results for larger values of \(k\) by proving an \(n^{2\lfloor k/3 \rfloor}\) lower bound.