Sparse Graphs Coalition

User Tools

Site Tools

Trace: • playground • 2021session3
sessions:2021sessions:2021session4

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
sessions:2021sessions:2021session4 [2021/03/28 08:04] – created ross.kangsessions:2021sessions:2021session4 [2022/04/21 09:39] (current) – ross.kang
Line 3: Line 3:
 In graph reconfiguration, we are given two solutions of a problem and the goal is to transform a solution into another while keeping a valid solution all along the transformation. Reconfiguration is related to various fields such as enumeration, counting, random sampling, discrete geometry, bio-informatics, or combinatorial game theory. In graph reconfiguration, we are given two solutions of a problem and the goal is to transform a solution into another while keeping a valid solution all along the transformation. Reconfiguration is related to various fields such as enumeration, counting, random sampling, discrete geometry, bio-informatics, or combinatorial game theory.
  
-The goal of the workshop is to tackle combinatorial and algorithmic questions related to graph reconfiguration in general with a special attention in graph recoloring. Graph recoloring has been studied for more than 40 years with two possible recoloring steps: single vertex recolorings (at each step we can change the color of one vertex) and Kempe recolorings (where at each step we can flip the colors of a Kempe chain). In particular, one can ask the following question: you many colors are needed to guarantee that we can transform any k-coloring into any other by allowing to recolor only one vertex at a time? For planar graphs, for instance, one can easily show that the answer is 7. If such a transformation exists, how many steps are needed? In the case of planar graphs, the answer to this question is still open.+The goal of the workshop is to tackle combinatorial and algorithmic questions related to graph reconfiguration in general with a special attention to graph recoloring. Graph recoloring has been studied for more than 40 years with two possible recoloring steps: single vertex recolorings (at each step we can change the color of one vertex) and Kempe recolorings (where at each step we can flip the colors of a Kempe chain). In particular, one can ask the following question: you many colors are needed to guarantee that we can transform any k-coloring into any other by allowing to recolor only one vertex at a time? For planar graphs, for instance, one can easily show that the answer is 7. If such a transformation exists, how many steps are needed? In the case of planar graphs, the answer to this question is still open.
  
 This workshop will focus mainly on exploring the connections with other areas. This workshop will focus mainly on exploring the connections with other areas.
 +
 +==== Organisers ====
 +
 +[[https://www.labri.fr/perso/mbonamy/|Marthe Bonamy]] and [[https://perso.liris.cnrs.fr/nbousquet/|Nicolas Bousquet]]
  
 ==== Workshop dates ==== ==== Workshop dates ====
Line 13: Line 17:
 ==== Confirmed participants ==== ==== Confirmed participants ====
  
-  * [[marthe.bonamy@gmail.com|Marthe Bonamy]] (organiser)+  * [[marthe.bonamy@u-bordeaux.com|Marthe Bonamy]] (organiser)
   * [[nicolas.bousquet@univ-lyon1.fr|Nicolas Bousquet]] (organiser)   * [[nicolas.bousquet@univ-lyon1.fr|Nicolas Bousquet]] (organiser)
 +  * Valentin Bartier
 +  * Sébastien Bonduelle
 +  * Marcin Brianski
 +  * Stijn Cambie
 +  * Wouter Cames van Batenburg
 +  * Dan Cranston
 +  * Matt Coulson
 +  * Konrad Dabrowski
 +  * Carl Feghali
 +  * Laurent Feuilloley
 +  * Aliénor Goubault
 +  * Marc Heinrich
 +  * Felix Hommelsheim
 +  * Clément Legrand-Duchesne
 +  * Frantisek Kardos
 +  * Tomas Kaiser
 +  * Aurelie Lagoutte
 +  * Owen Merkel
 +  * Benjamin Moore
 +  * Amer Mouawad
 +  * Moritz Muhlenthaler
 +  * Jonathan Narboni
 +  * Guillem Perarnau
 +  * Sebastian Siebertz
  
-Registration details: tba 
  
-Registration deadline: tba+Registration details:  
 +Please send an email to the organizers if you are interested to participate. 
 + 
 +Registration deadline: 21st of May (closed)
  
 ==== Open problems ==== ==== Open problems ====
  
-Submission details: tba+Submission details:  
 + Template: https://www.mimuw.edu.pl/~mp248287/opl-example.tgz
  
-Submission deadline: tba+Submit open problems related to reconfiguration (generously interpreted) by email to the organisers. The main aim of the workshop is to work on and solve these! 
  
-==== Schedule (tbc) ====+Submission deadline: 27th of May (closed) 
 + 
 +==== Schedule ====
  
   1. Monday, 31 May   1. Monday, 31 May
-    a. +    9h45 - Introduction 
 +    10h - Amer Mouawad - Algorithmic aspects of reconfiguration 
 +    11h15 - Marc Heinrich - A survey on graph recoloring 
 +    14h - Open problem session 
 +    15h30 - Partition into small groups
   2. Tuesday, 1 June   2. Tuesday, 1 June
-    a. +    11h - Coffee break (on Wonder) 
 +    15h - Cofee break (on Wonder) 
 +    15h30 - Progress report
   3. Wednesday, 2 June   3. Wednesday, 2 June
-    a. +    11h - Coffee break (on Wonder) 
 +    15h - Cofee break (on Wonder) 
 +    15h30 - Progress report
   4. Thursday, 3 June   4. Thursday, 3 June
-    a. +    11h - Coffee break (on Wonder) 
 +    15h - Cofee break (on Wonder) 
 +    15h30 - Progress report
   5. Friday, 4 June   5. Friday, 4 June
-    a. +    11h - Coffee break (on Wonder) 
 +    14h30 - Progress report 
 + 
 +(All the time have to be read Central European Summer Time, i.e. UTC+2). 
 + 
 +==== Research results ==== 
 + 
 +  * Cambie, Cames van Batenburg, Cranston. Optimally Reconfiguring List and Correspondence Colourings. https://arxiv.org/abs/2204.07928 
  
-==== Talks (tbc) ==== 
  
sessions/2021sessions/2021session4.1616918694.txt.gz · Last modified: 2021/03/28 08:04 by ross.kang