"False"
Skip to content
printicon
Main menu hidden.

Extremal independent set reconfiguration

Thu
11
May
Time Thursday 11 May, 2023 at 14:15 - 15:15
Place Zoom

Abstract: Two independent sets A,B of size k of a graph G are said to be adjacent if their symmetric difference is reduced to two vertices (i.e. |A \ B|=|B \ A|=1).  Consider the graph R_k(G) whose vertices are k-independent sets and where two sets A,B are adjacent with the notion of adjacency defined above. One can then wonder: given two k-independent sets, are they in the same connected component of R_k(G) ? How many steps are needed to find a transformation? Can we efficiently find a transformation? All these problems, called reconfiguration problems, have attracted a lot of attention recently.

In the first part of the talk, we will briefly survey some important results and open problems on the topic. In the second part we will focus on "extremal reconfiguration" which consists in studying the following problem: what is the largest possible diameter of a connected component of R_k(G) for a given k and a given graph size n ? We provide some general upper and lower bounds.
In the particular case of k=3, we prove that this diameter can be almost quadratic (in n) but cannot be quadratic. To do so, we exhibit some relations between this problem and the so-called (6, 3)-theorem of Ruzsa-Szemerédi.

Event type: Seminar

Speaker: Nicolas Bousquet, CNRS Lyon

Contact
Victor Falgas Ravry
Read about Victor Falgas Ravry