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.
Speaker: Nicolas Bousquet, CNRS Lyon
This website uses cookies which are stored in your browser. Some cookies are necessary for the page to work properly and others are selectable. You choose which ones you want to allow.