论文标题
常规图上的三角过程
A triangle process on regular graphs
论文作者
论文摘要
开关是对图表边缘进行局部更改的操作，通常是为了保留顶点度。我们研究了一组受限制的开关，称为三角形开关。每个三角开关都会创建或删除至少一个三角形。三角形开关可用于定义马尔可夫链，该链以给定的度序列生成图形，并且具有比具有相同度的均匀随机图中的典型三角形（3个周期）。我们证明，对于所有$ d \ geq 3 $，一组三角形开关将所有$ d $ regular图形的集合连接起来。因此，在这些图表上，任何向所有三角形开关分配正概率的马尔可夫链都是不可还原的。我们还针对2个规则图研究了这个问题。
Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one triangle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all $d$-regular graphs on $n$ vertices, for all $d\geq 3$. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs.
