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.
@article{10_37236_11771,
author = {Nicolas Bousquet and Bastien Durain and Th\'eo Pierron and St\'ephan Thomass\'e},
title = {Extremal independent set reconfiguration},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {3},
doi = {10.37236/11771},
zbl = {1519.05188},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11771/}
}
TY - JOUR
AU - Nicolas Bousquet
AU - Bastien Durain
AU - Théo Pierron
AU - Stéphan Thomassé
TI - Extremal independent set reconfiguration
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/11771/
DO - 10.37236/11771
ID - 10_37236_11771
ER -
%0 Journal Article
%A Nicolas Bousquet
%A Bastien Durain
%A Théo Pierron
%A Stéphan Thomassé
%T Extremal independent set reconfiguration
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11771/
%R 10.37236/11771
%F 10_37236_11771
Nicolas Bousquet; Bastien Durain; Théo Pierron; Stéphan Thomassé. Extremal independent set reconfiguration. The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11771
