Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.09489 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911877354749952 |
|---|---|
| author | Brody, Joshua Devlin, Pat Dudeja, Aditi Rivkin, Emmi |
| author_facet | Brody, Joshua Devlin, Pat Dudeja, Aditi Rivkin, Emmi |
| contents | In this paper we study $d$-dependent random graphs -- introduced by Brody and Sanchez -- which are the family of random graph distributions where each edge is present with probability $p$, and each edge is independent of all but at most $d$ other edges. For this random graph model, we analyze degree sequences, jumbledness, connectivity, and subgraph containment. Our results mirror those of the classical Erdős--Rényi random graph, which are recovered by specializing our problem to $d=0$, although we show that in many regards our setting is appreciably more nuanced. We survey what is known for this model and conclude with a variety of open questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09489 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Evolution of locally dependent random graphs Brody, Joshua Devlin, Pat Dudeja, Aditi Rivkin, Emmi Combinatorics 05C80 (primary) In this paper we study $d$-dependent random graphs -- introduced by Brody and Sanchez -- which are the family of random graph distributions where each edge is present with probability $p$, and each edge is independent of all but at most $d$ other edges. For this random graph model, we analyze degree sequences, jumbledness, connectivity, and subgraph containment. Our results mirror those of the classical Erdős--Rényi random graph, which are recovered by specializing our problem to $d=0$, although we show that in many regards our setting is appreciably more nuanced. We survey what is known for this model and conclude with a variety of open questions. |
| title | Evolution of locally dependent random graphs |
| topic | Combinatorics 05C80 (primary) |
| url | https://arxiv.org/abs/2405.09489 |