论文标题
高维产品图上的渗透
Percolation on High-dimensional Product Graphs
论文作者
论文摘要
我们考虑在基本图是规则且有界顺序的高维产品图上的渗透。在亚临界体制中，我们表明通常最大的组件是顶点数量的对数。在超临界方案中，我们的主要结果恢复了最大成分顺序的尖锐渐近，并表明所有其他组件通常在顶点数量中具有对数的顺序对数。特别是，我们表明该相变量与二项式随机图之一定量相似。 This generalises the results of Ajtai, Komlós, and Szemerédi and of Bollobás, Kohayakawa, and Łuczak who showed that the $d$-dimensional hypercube, which is the $d$-fold Cartesian product of an edge, undergoes a phase transition quantitatively similar to the one of the binomial random graph.
We consider percolation on high-dimensional product graphs, where the base graphs are regular and of bounded order. In the subcritical regime, we show that typically the largest component is of order logarithmic in the number of vertices. In the supercritical regime, our main result recovers the sharp asymptotic of the order of the largest component, and shows that all the other components are typically of order logarithmic in the number of vertices. In particular, we show that this phase transition is quantitatively similar to the one of the binomial random graph. This generalises the results of Ajtai, Komlós, and Szemerédi and of Bollobás, Kohayakawa, and Łuczak who showed that the $d$-dimensional hypercube, which is the $d$-fold Cartesian product of an edge, undergoes a phase transition quantitatively similar to the one of the binomial random graph.
