Invitation to Reconfiguration - Part II
Org: Nicolas Bousquet
(CNRS, Université de Lyon) and Anna Lubiw
(University of Waterloo)
- DANIEL CRANSTON, Virginia Commonwealth University
In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent [PDF]
A Kempe swap in a proper coloring interchanges the colors on some
maximal connected 2-colored subgraph. Two $k$-colorings are
$k$-equivalent if we can transform one into the other using Kempe
swaps. We show that if $G$ is 6-regular with a toroidal embedding
where every non-contractible cycle has length at least 7, then all
5-colorings of $G$ are 5-equivalent. Bonamy, Bousquet, Feghali, and
Johnson asked if this holds when $G$ is formed from the Cartesian
product of $C_m$ and $C_n$ by adding parallel diagonals inside all
4-faces. We answer their question affirmatively when $m,n\ge 6$.
Joint with Reem Mahmoud.
- SATYAN DEVADOSS, University of San Diego
Associativity reconfigurations: Colors, Graphs, Polytopes [PDF]
Fifty years ago, the associahedron made its debut, a polytope that captured reconfigurations of associativity structures in homotopy theory. The beauty of this polytope is the multiplicity of areas in which it now appears, a sampling of which include root systems, real algebraic geometry, phylogenetics, string theory, computational geometry, and holomorphic curves. This should not surprise us since the principle of associativity is ubiquitous. We showcase this marvelous polytope and consider its generalizations into triangulations of polygons, connectivity of graphs, and colorings of tubes.
- MARC HEINRICH, University of Leeds
Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth [PDF]
The Glauber dynamics is a random process recolouring at each step a random vertex of a graph with a new colour chosen uniformly at random. It is known that when the total number of colours available is at least $\Delta+2$, this process converges to a uniform distribution. A well known conjecture states that under this condition the time it takes for the convergence to happen, called the mixing time, is polynomial in the size of the graph. We study this problem for two specific class of graphs: graphs of bounded treewidth and chordal graph.
- KUIKUI LIU, University of Washington
Markov Chain Analysis Through the Lens of High-Dimensional Expanders [PDF]
The Markov Chain Monte Carlo paradigm is one of the most widely used methods for sampling from challenging distributions, both practically and theoretically. We discuss a recent line of work that leverages the perspective of high-dimensional expanders and their local-to-global properties to analyze Markov chains in the discrete setting. We will highlight numerous connections with other areas including geometry of polynomials, statistical physics, and more. Specific applications include sampling from bases of matroids, and spin systems in statistical physics. Based on several joint works with Nima Anari, Zongchen Chen, Shayan Oveis Gharan, Eric Vigoda, and Cynthia Vinzant.
- JONATHAN NARBONI, Université de Bordeaux
On Vizing's edge colouring question [PDF]
In his 1965 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes (i.e. swapping the colours of a maximal bichromatic component)? We answer this question in the affirmative for triangle-free graphs.
This is joint work with Marthe Bonamy, Oscar Defrain, Tereza Klimošová, Aurélie Lagoutte