论文标题
Glauber动力学，用于弦图的颜色和有限树宽的图形
Glauber dynamics for colourings of chordal graphs and graphs of bounded treewidth
论文作者
论文摘要
图形颜色上的glauber动力学是一个随机过程，它包括在每个步骤中重新上色一个图形的随机顶点，并在其附近尚未存在的颜色中随机选择了新颜色。众所周知，如果可用的颜色总数至少为$δ+2 $，其中$δ$是图的最大程度，则此过程将收敛到所有颜色集的均匀分布。此外，一个众所周知的猜想是，收敛发生的时间（称为混合时间）在图的大小中是多项式。在文献中，通过允许更多颜色或将图表限制为特定类别或两者兼而有之，已经研究了该猜想的许多较弱的变体。本文通过研究弦图上的Glauber动力学的混合时间以及有界树宽的图，遵循了这一研究。我们表明，在以下两种情况下，混合时间在图的大小中是多项式的： - 在具有有界树宽的图表上，至少$δ+2 $颜色， - 在弦图上，如果颜色的数量至少为$（1+ \ varepsilon）（δ+1）$，则对于任何固定常数$ \ varepsilon $。
The Glauber dynamics on the colourings of a graph is a random process which consists in recolouring at each step a random vertex of a graph with a new colour chosen uniformly at random among the colours not already present in its neighbourhood. It is known that when the total number of colours available is at least $Δ+2$, where $Δ$ is the maximum degree of the graph, this process converges to a uniform distribution on the set of all the colourings. Moreover, a well known conjecture is that the time it takes for the convergence to happen, called the mixing time, is polynomial in the size of the graph. Many weaker variants of this conjecture have been studied in the literature by allowing either more colours, or restricting the graphs to particular classes, or both. This paper follows this line of research by studying the mixing time of the Glauber dynamics on chordal graphs, as well as graphs of bounded treewidth. We show that the mixing time is polynomial in the size of the graph in the two following cases: - on graphs with bounded treewidth, and at least $Δ+2$ colours, - on chordal graphs if the number of colours is at least $(1+\varepsilon) (Δ+1)$, for any fixed constant $\varepsilon$.
