Extremal independent set reconfiguration (Q6133144)
From MaRDI portal
scientific article; zbMATH DE number 7729679
Language | Label | Description | Also known as |
---|---|---|---|
English | Extremal independent set reconfiguration |
scientific article; zbMATH DE number 7729679 |
Statements
Extremal independent set reconfiguration (English)
0 references
18 August 2023
0 references
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.
0 references
combinatorial reconfiguration framework
0 references
configuration graph
0 references