The phase transition in bounded-size Achlioptas processes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2017
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912211758219264 |
|---|---|
| author | Riordan, Oliver Warnke, Lutz |
| author_facet | Riordan, Oliver Warnke, Lutz |
| contents | Perhaps the best understood phase transition is that in the component structure of the uniform random graph process introduced by Erdős and Rényi around 1960. Since the model is so fundamental, it is very interesting to know which features of this phase transition are specific to the model, and which are `universal', at least within some larger class of processes (a `universality class'). Achlioptas process, a class of variants of the Erdős--Rényi process that are easy to define but difficult to analyze, have been extensively studied from this point of view. Here, settling a number of conjectures and open problems, we show that all `bounded-size' Achlioptas processes share (in a strong sense) all the key features of the Erdős--Rényi phase transition. We do not expect this to hold for Achlioptas processes in general. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1704_08714 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | The phase transition in bounded-size Achlioptas processes Riordan, Oliver Warnke, Lutz Probability Statistical Mechanics Combinatorics 05C80, 60C05, 90B15 Perhaps the best understood phase transition is that in the component structure of the uniform random graph process introduced by Erdős and Rényi around 1960. Since the model is so fundamental, it is very interesting to know which features of this phase transition are specific to the model, and which are `universal', at least within some larger class of processes (a `universality class'). Achlioptas process, a class of variants of the Erdős--Rényi process that are easy to define but difficult to analyze, have been extensively studied from this point of view. Here, settling a number of conjectures and open problems, we show that all `bounded-size' Achlioptas processes share (in a strong sense) all the key features of the Erdős--Rényi phase transition. We do not expect this to hold for Achlioptas processes in general. |
| title | The phase transition in bounded-size Achlioptas processes |
| topic | Probability Statistical Mechanics Combinatorics 05C80, 60C05, 90B15 |
| url | https://arxiv.org/abs/1704.08714 |