标题： 随机图在给定度数下的通用直径界限 显示英文标题

标题： Universal diameter bounds for random graphs with given degrees

摘要： 给定一个图$G$，令$\mathrm{diam}(G)$为$G$中位于同一连通分量中的任意两个顶点之间的最大距离，令$\mathrm{diam}^+(G)$为$G$中任意两个顶点之间的最大距离；因此，如果$G$不连通，则$\mathrm{diam}^+(G)=\infty$。 固定一个正整数序列$(d_1,\ldots,d_n)$，令$\mathbf{G}$是一个具有$V(\mathbf{G})=[n]:=\{1,\ldots,n\}$的均匀随机连通简单图，使得$\mathrm{deg}_{\mathbf{G}}(v)=d_v$对所有$v \in [n]$成立。 我们证明，除非一个$1-o(1)$比例的顶点具有度数$2$，否则$\mathbb{E}[\mathrm{diam}(\mathbf{G})]=O(\sqrt{n})$。很容易看出，这个界限对于一般的度序列是最佳的（特别是在树的情况下，其中$\sum_{v=1}^n d_v = 2(n-1)$）。我们还证明，这个界限在没有连通性约束的情况下仍然成立。作为证明的关键输入，我们证明了最小度数为$3$的图以高概率是连通的且直径为对数级别：如果$\min(d_1,\ldots,d_n) \ge 3$则$\mathrm{diam}^+(\mathbf{G})=O_{\mathbb{P}}(\log n)$；这个界限也是最佳的。 显示英文摘要

摘要： Given a graph $G$, let $\mathrm{diam}(G)$ be the greatest distance between any two vertices of $G$ which lie in the same connected component, and let $\mathrm{diam}^+(G)$ be the greatest distance between any two vertices of $G$; so $\mathrm{diam}^+(G)=\infty$ if $G$ is not connected. Fix a sequence $(d_1,\ldots,d_n)$ of positive integers, and let $\mathbf{G}$ be a uniformly random connected simple graph with $V(\mathbf{G})=[n]:=\{1,\ldots,n\}$ such that $\mathrm{deg}_{\mathbf{G}}(v)=d_v$ for all $v \in [n]$. We show that, unless a $1-o(1)$ proportion of vertices have degree $2$, then $\mathbb{E}[\mathrm{diam}(\mathbf{G})]=O(\sqrt{n})$. It is not hard to see that this bound is best possible for general degree sequences (and in particular in the case of trees, in which $\sum_{v=1}^n d_v = 2(n-1)$). We also prove that this bound holds without the connectivity constraint. As a key input to the proofs, we show that graphs with minimum degree $3$ are with high probability connected and have logarithmic diameter: if $\min(d_1,\ldots,d_n) \ge 3$ then $\mathrm{diam}^+(\mathbf{G})=O_{\mathbb{P}}(\log n)$; this bound is also best possible.