论文标题
扩展扩展器的超临界随机子图及其后果
Expansion in Supercritical Random Subgraphs of Expanders and its Consequences
论文作者
论文摘要
2004年，Frieze，Krivelevich和Martin [17]在伪随机图的随机子图中建立了巨型成分的出现。我们研究了巨型成分的几种典型特性，最著名的是其扩展特性。我们在巨人中建立了连接集的渐近顶点扩展，$ \ tilde {o} \ left（ε^2 \ right）$。从这些扩展属性中，我们得出巨人的直径通常为$ o_is \ left（\ log n \ right）$，并且在巨型上懒惰的随机步行的混合时间是渐近的$ o_is \ left（\ log log^2 n \ right）$。我们还显示了巨人（不一定连接的）线性大小子集的相似渐近扩展特性，并且典型的大型扩展器作为亚图。
In 2004, Frieze, Krivelevich and Martin [17] established the emergence of a giant component in random subgraphs of pseudo-random graphs. We study several typical properties of the giant component, most notably its expansion characteristics. We establish an asymptotic vertex expansion of connected sets in the giant by a factor of $\tilde{O}\left(ε^2\right)$. From these expansion properties, we derive that the diameter of the giant is typically $O_ε\left(\log n\right)$, and that the mixing time of a lazy random walk on the giant is asymptotically $O_ε\left(\log^2 n\right)$. We also show similar asymptotic expansion properties of (not necessarily connected) linear sized subsets in the giant, and the typical existence of a large expander as a subgraph.
