论文标题
图形的截止的通用性，并增加了随机匹配
Universality of cutoff for graphs with an added random matching
论文作者
论文摘要
我们在定义为以下的一类随机图上建立了截止的通用性，以简单随机步行。给定有限图$ g =（v，e）$带有$ | v | $，即使我们定义了一个随机图$ g^*=（v，e \ cup e'），通过选择$ e'$作为（无序的）对$ v $的随机完美匹配而获得的。我们表明，对于一系列此类图，如果$ g_n $的最小尺寸为$ g_n $的最小尺寸，则所有$ n $的最小尺寸为$ g_n $，则所有$ n $的最小尺寸，则在$ g_n^*$上随机步行$ g_n^*$展示cutoft cutoft cutoft w.h.p.这提供了一个简单的通用操作，可以在给定的图中添加一些随机性，从而导致截止。
We establish universality of cutoff for simple random walk on a class of random graphs defined as follows. Given a finite graph $G=(V,E)$ with $|V|$ even we define a random graph $ G^*=(V,E \cup E')$ obtained by picking $E'$ to be the (unordered) pairs of a random perfect matching of $V$. We show that for a sequence of such graphs $G_n$ of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of $G_n$ is at least 3 for all $n$, then the random walk on $G_n^*$ exhibits cutoff w.h.p. This provides a simple generic operation of adding some randomness to a given graph, which results in cutoff.
