论文标题
具有指定学位的随机图的子图概率，并应用于色数和连接性
Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
论文作者
论文摘要
Given a graphical degree sequence ${\bf d}=(d_1,\ldots, d_n)$, let $G(n, {\bf d})$ denote a uniformly random graph on vertex set $[n]$ where vertex $ i$ has degree $d_i$ for every $1\le i\le n$.我们在$ g（n，{\ bf d}）$中的任意边缘的联合概率上给出了上限和下限。这些上限和下限大约是在配置模型中可以得到的，因此配置模型中的分析可以直接转换为$ g（n，{\ bf d}）$，而无需在配置模型的条件下产生简单的图形。通过应用此新的概率工具，可以通过更简单的证据来大大改善$ g（n，{\ bf d}）$的许多现有结果。我们给出的一个例子是$ g（n，{\ bf d}）$的色度数。 在另一个应用程序中，我们使用这些联合概率来研究$ g（n，{\ bf d}）$的连接性。当$δ^2 = o（m）$，其中$δ$是$ {\ bf d} $的最大组成部分时，我们完全表征了$ g（n，{\ bf d}）$的连接相位过渡。当$δ$不受限制时，我们还为$ g（n，{\ bf d}）$提供足够的条件。
Given a graphical degree sequence ${\bf d}=(d_1,\ldots, d_n)$, let $G(n, {\bf d})$ denote a uniformly random graph on vertex set $[n]$ where vertex $ i$ has degree $d_i$ for every $1\le i\le n$. We give upper and lower bounds on the joint probability of an arbitrary set of edges in $G(n,{\bf d})$. These upper and lower bounds are approximately what one would get in the configuration model, and thus the analysis in the configuration model can be translated directly to $G(n,{\bf d})$, without conditioning on that the configuration model produces a simple graph. Many existing results of $G(n,{\bf d})$ in the literature can be significantly improved with simpler proofs, by applying this new probabilistic tool. One example we give is about the chromatic number of $G(n,{\bf d})$. In another application, we use these joint probabilities to study the connectivity of $G(n,{\bf d})$. When $Δ^2=o(M)$ where $Δ$ is the maximum component of ${\bf d}$, we fully characterise the connectivity phase transition of $G(n,{\bf d})$. We also give sufficient conditions for $G(n,{\bf d})$ being connected when $Δ$ is unrestricted.
