论文标题
随机扭曲的高管 - 结构和随机性之间
Randomly twisted hypercubes -- between structure and randomness
论文作者
论文摘要
扭曲的高管是布尔超立方体的概括，通过迭代连接两个图形实例，通过均匀随机的完美匹配来获得。 Dudek等。表明当两个实例独立时，这些图的直径最佳。 我们在实例可以具有普遍依赖性的情况下以及在特殊情况下相同的情况下研究扭曲的高管。我们表明，所得图具有随机的常规图，包括小直径，大顶点膨胀，其特征值的半圆形定律以及没有非平凡的自动形态。但是，与随机的常规图相反，扭曲的超振管允许短路方案。
Twisted hypercubes are generalizations of the Boolean hypercube, obtained by iteratively connecting two instances of a graph by a uniformly random perfect matching. Dudek et al. showed that when the two instances are independent, these graphs have optimal diameter. We study twisted hypercubes in the setting where the instances can have general dependence, and also in the particular case where they are identical. We show that the resultant graph shares properties with random regular graphs, including small diameter, large vertex expansion, a semicircle law for its eigenvalues and no non-trivial automorphisms. However, in contrast to random regular graphs, twisted hypercubes allow for short routing schemes.
