Geodesic
Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract
Discrete mathematics & theoretical computer science, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015) (2015).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2015_special_285_a5,
     author = {Panagiotou, Konstantinos and Stufler, Benedikt and Weller, Kerstin},
     title = {Scaling {Limits} of {Random} {Graphs} from {Subcritical} {Classes:} {Extended} abstract},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)},
     year = {2015},
     doi = {10.46298/dmtcs.2461},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2461/}
}
TY  - JOUR
AU  - Panagiotou, Konstantinos
AU  - Stufler, Benedikt
AU  - Weller, Kerstin
TI  - Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract
JO  - Discrete mathematics & theoretical computer science
PY  - 2015
VL  - DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2461/
DO  - 10.46298/dmtcs.2461
LA  - en
ID  - DMTCS_2015_special_285_a5
ER  - 
%0 Journal Article
%A Panagiotou, Konstantinos
%A Stufler, Benedikt
%A Weller, Kerstin
%T Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract
%J Discrete mathematics & theoretical computer science
%D 2015
%V DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2461/
%R 10.46298/dmtcs.2461
%G en
%F DMTCS_2015_special_285_a5
Panagiotou, Konstantinos; Stufler, Benedikt; Weller, Kerstin. Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract. Discrete mathematics & theoretical computer science, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015) (2015). doi : 10.46298/dmtcs.2461. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2461/

Cité par Sources :