# Stijn Cambie, The precise diameter of reconfiguration graphs

## May 23 Monday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)

### Speaker

Stijn Cambie
IBS Extremal Combinatorics and Probability Group

Reconfiguration is about changing instances in small steps. For example, one can perform certain moves on a Rubik’s cube, each of them changing its configuration a bit. In this case, in at most 20 steps, one can end up with the preferred result. One could construct a graph with as nodes the possible configurations of the Rubik’s cube (up to some isomorphism) and connect two nodes if one can be obtained by applying only one move to the other. Finding an optimal solution, i.e. a minimum number of moves to solve a Rubik’s cube is now equivalent to finding the distance in the graph.

We will wonder about similar problems in reconfiguration, but applied to list- and DP-colouring. In this case, the small step consists of recolouring precisely one vertex. Now we will be interested in the diameter of the reconfiguration graph and show that sometimes we can determine the precise diameters of these.

As such, during this talk, we present some main ideas of [arXiv:2204.07928].

## Details

Date:
May 23 Monday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Room B332