论文标题
未成年人，连通性和直径随机稀疏图
Minors, connectivity, and diameter in randomly perturbed sparse graphs
论文作者
论文摘要
考虑了稀疏图的极端特性，被二项式随机图随机扰动。众所周知，每个$ n $ vertex Graph $ g $都包含一个完整的订单$ω（n/α（g））$。我们证明，添加$ξn$随机边缘，其中$ξ> 0 $是任意的但固定的，将$ n $ vertex Graph $ g $满足满足$α（g）\ leqζ（ξ）n $渐近几乎肯定会导致包含完整订单$ \\ tilde opildeω\ weft（n///s）的图（n $ n $ n $ n $ a）的n///n $ n/n $ $ $ \ sq rt（n n $）这个结果紧紧抓住了隐式对数术语。 对于完整的拓扑未成年人，我们证明存在一个恒定的$ c> 0 $，因此将$ c n $随机边缘添加到图$ g $满足$δ（g）=ω（1）$的图形$ g $，渐近上几乎可以肯定地导致包含$ \\ tildeω（\ tildeω（\ y min \ $）的完整拓扑次数$ \ tilde forme这个结果紧紧抓住了隐式对数术语。 最后，扩展了Bohman，Frieze，Krivelevich和Martin的稠密情况，我们分析了顶点连接性的渐近行为以及随机扰动的稀疏图的直径。
Extremal properties of sparse graphs, randomly perturbed by the binomial random graph are considered. It is known that every $n$-vertex graph $G$ contains a complete minor of order $Ω(n/α(G))$. We prove that adding $ξn$ random edges, where $ξ> 0$ is arbitrarily small yet fixed, to an $n$-vertex graph $G$ satisfying $α(G) \leq ζ(ξ)n$ asymptotically almost surely results in a graph containing a complete minor of order $\tilde Ω\left( n/\sqrt{α(G)}\right)$; this result is tight up to the implicit logarithmic terms. For complete topological minors, we prove that there exists a constant $C>0$ such that adding $C n$ random edges to a graph $G$ satisfying $δ(G) = ω(1)$, asymptotically almost surely results in a graph containing a complete topological minor of order $\tilde Ω(\min\{δ(G),\sqrt{n}\})$; this result is tight up to the implicit logarithmic terms. Finally, extending results of Bohman, Frieze, Krivelevich, and Martin for the dense case, we analyse the asymptotic behaviour of the vertex-connectivity and the diameter of randomly perturbed sparse graphs.
