Extremal Independent Set Reconfiguration

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 3n/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 n2 k/3 lower bound.