Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract
We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling fact...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2015-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2461/pdf |
| _version_ | 1797270248675606528 |
|---|---|
| author | Konstantinos Panagiotou Benedikt Stufler Kerstin Weller |
| author_facet | Konstantinos Panagiotou Benedikt Stufler Kerstin Weller |
| author_sort | Konstantinos Panagiotou |
| collection | DOAJ |
| description | We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $\text{D}(\mathsf{C}_n)$ and height $\text{H}(\mathsf{C}_n^\bullet)$ of the rooted random graph $\mathsf{C}_n^\bullet$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on $\mathsf{C}_n$, where we show the convergence to $\mathcal{T}_{\mathsf{e}}$ under an appropriate rescaling. |
| first_indexed | 2024-04-25T02:01:15Z |
| format | Article |
| id | doaj.art-f0e0dcd0ad984b699205fafd88a99278 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:15Z |
| publishDate | 2015-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f0e0dcd0ad984b699205fafd88a992782024-03-07T15:01:25ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502015-01-01DMTCS Proceedings, 27th...Proceedings10.46298/dmtcs.24612461Scaling Limits of Random Graphs from Subcritical Classes: Extended abstractKonstantinos Panagiotou0Benedikt Stufler1https://orcid.org/0000-0001-9162-2144Kerstin Weller2Ludwig Maximilian University [Munich]Ludwig Maximilian University [Munich]Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich]We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $\text{D}(\mathsf{C}_n)$ and height $\text{H}(\mathsf{C}_n^\bullet)$ of the rooted random graph $\mathsf{C}_n^\bullet$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on $\mathsf{C}_n$, where we show the convergence to $\mathcal{T}_{\mathsf{e}}$ under an appropriate rescaling.https://dmtcs.episciences.org/2461/pdfscaling limitsrandom graphscontinuum random trees[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Konstantinos Panagiotou Benedikt Stufler Kerstin Weller Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract Discrete Mathematics & Theoretical Computer Science scaling limits random graphs continuum random trees [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract |
| title_full | Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract |
| title_fullStr | Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract |
| title_full_unstemmed | Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract |
| title_short | Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract |
| title_sort | scaling limits of random graphs from subcritical classes extended abstract |
| topic | scaling limits random graphs continuum random trees [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2461/pdf |
| work_keys_str_mv | AT konstantinospanagiotou scalinglimitsofrandomgraphsfromsubcriticalclassesextendedabstract AT benediktstufler scalinglimitsofrandomgraphsfromsubcriticalclassesextendedabstract AT kerstinweller scalinglimitsofrandomgraphsfromsubcriticalclassesextendedabstract |