Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909623773036544 |
|---|---|
| author | Gao, Pu Ohapkin, Yuval |
| author_facet | Gao, Pu Ohapkin, Yuval |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_02216 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity Gao, Pu Ohapkin, Yuval Combinatorics 05C80 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. |
| title | Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity |
| topic | Combinatorics 05C80 |
| url | https://arxiv.org/abs/2007.02216 |