Loading Events

« All Events

:

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:

Venue

Room B332
IBS (기초과학연구원) + Google Map

Organizer

Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.