Central limit theorem for crossings in randomly embedded graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913540545183744 |
|---|---|
| author | Arenas-Velilla, Santiago Arizmendi, Octavio Paguyo, J. E. |
| author_facet | Arenas-Velilla, Santiago Arizmendi, Octavio Paguyo, J. E. |
| contents | We consider the number of crossings in a random embedding of a graph, $G$, with vertices in convex position. We give explicit formulas for the mean and variance of the number of crossings as a function of various subgraph counts of $G$. Using Stein's method and size-bias coupling, we establish an upper bound on the Kolmogorov distance between the distribution of the number of crossings and a standard normal random variable. We also consider the case where $G$ is a random graph and obtain a Kolmogorov bound between the distribution of crossings and a Gaussian mixture distribution. As applications, we obtain central limit theorems with convergence rates for the number of crossings in random embeddings of matchings, path graphs, cycle graphs, disjoint union of triangles, random $d$-regular graphs, and mixtures of random graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_11570 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Central limit theorem for crossings in randomly embedded graphs Arenas-Velilla, Santiago Arizmendi, Octavio Paguyo, J. E. Probability Combinatorics 60C05, 60F05 We consider the number of crossings in a random embedding of a graph, $G$, with vertices in convex position. We give explicit formulas for the mean and variance of the number of crossings as a function of various subgraph counts of $G$. Using Stein's method and size-bias coupling, we establish an upper bound on the Kolmogorov distance between the distribution of the number of crossings and a standard normal random variable. We also consider the case where $G$ is a random graph and obtain a Kolmogorov bound between the distribution of crossings and a Gaussian mixture distribution. As applications, we obtain central limit theorems with convergence rates for the number of crossings in random embeddings of matchings, path graphs, cycle graphs, disjoint union of triangles, random $d$-regular graphs, and mixtures of random graphs. |
| title | Central limit theorem for crossings in randomly embedded graphs |
| topic | Probability Combinatorics 60C05, 60F05 |
| url | https://arxiv.org/abs/2308.11570 |