Minimum degree $k$ and $k$-connectedness usually arrive together
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913515578589184 |
|---|---|
| author | Diskin, Sahar Geisler, Anna |
| author_facet | Diskin, Sahar Geisler, Anna |
| contents | Let $d,n\in \mathbb{N}$ be such that $d=ω(1)$, and $d\le n^{1-a}$ for some constant $a>0$. Consider a $d$-regular graph $G=(V, E)$ and the random graph process that starts with the empty graph $G(0)$ and at each step $G(i)$ is obtained from $G(i-1)$ by adding uniformly at random a new edge from $E$. We show that if $G$ satisfies some (very) mild global edge-expansion, and an almost optimal edge-expansion of sets up to order $O(d\log n)$, then for any constant $k\in \mathbb{N}$ in the random graph process on $G$, typically the hitting times of minimum degree at least $k$ and of $k$-connectedness are equal. This, in particular, covers both $d$-regular high dimensional product graphs and pseudo-random graphs, and confirms a conjecture of Joos from 2015. We further demonstrate that this result is tight in the sense that there are $d$-regular $n$-vertex graphs with optimal edge-expansion of sets up to order $Ω(d)$, for which the probability threshold of minimum degree at least one is different than the probability threshold of connectivity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14398 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Minimum degree $k$ and $k$-connectedness usually arrive together Diskin, Sahar Geisler, Anna Combinatorics Probability 05C80, 60K35 Let $d,n\in \mathbb{N}$ be such that $d=ω(1)$, and $d\le n^{1-a}$ for some constant $a>0$. Consider a $d$-regular graph $G=(V, E)$ and the random graph process that starts with the empty graph $G(0)$ and at each step $G(i)$ is obtained from $G(i-1)$ by adding uniformly at random a new edge from $E$. We show that if $G$ satisfies some (very) mild global edge-expansion, and an almost optimal edge-expansion of sets up to order $O(d\log n)$, then for any constant $k\in \mathbb{N}$ in the random graph process on $G$, typically the hitting times of minimum degree at least $k$ and of $k$-connectedness are equal. This, in particular, covers both $d$-regular high dimensional product graphs and pseudo-random graphs, and confirms a conjecture of Joos from 2015. We further demonstrate that this result is tight in the sense that there are $d$-regular $n$-vertex graphs with optimal edge-expansion of sets up to order $Ω(d)$, for which the probability threshold of minimum degree at least one is different than the probability threshold of connectivity. |
| title | Minimum degree $k$ and $k$-connectedness usually arrive together |
| topic | Combinatorics Probability 05C80, 60K35 |
| url | https://arxiv.org/abs/2409.14398 |