Achlioptas process phase transitions are continuous (Q453240): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
In the well-known Erdős-Rényi graph sequence, the initial graph \(G(0)\) is the empty graph on \(n\) vertices, and \(G(m)\) is obtained from \(G(m-1)\) by inserting an edge at a randomly selected empty vertex-pair site for \(m=1,2,\dots\). The proportion of vertices in the largest connected component converges in probability to zero if and only if \(m/n\) converges to a value not larger than \(1/2\). This phase transition at the critical value \(1/2\) can be changed by modifying the rule for edge selections. It has been conjectured that a certain ``product rule'' exhibits so called ``explosive percolation''. This conjecture is here disproved by investigating a general edge selection rule which specifies how at least one edge is inserted among the vertex-pair sites in a random fixed-size sample of vertices. It is shown that this rule leads to continuous phase transitions. Convergence of the proportion of vertices in any largest component and convergence of the proportions of vertices in components of different orders are investigated. | |||
Property / review text: In the well-known Erdős-Rényi graph sequence, the initial graph \(G(0)\) is the empty graph on \(n\) vertices, and \(G(m)\) is obtained from \(G(m-1)\) by inserting an edge at a randomly selected empty vertex-pair site for \(m=1,2,\dots\). The proportion of vertices in the largest connected component converges in probability to zero if and only if \(m/n\) converges to a value not larger than \(1/2\). This phase transition at the critical value \(1/2\) can be changed by modifying the rule for edge selections. It has been conjectured that a certain ``product rule'' exhibits so called ``explosive percolation''. This conjecture is here disproved by investigating a general edge selection rule which specifies how at least one edge is inserted among the vertex-pair sites in a random fixed-size sample of vertices. It is shown that this rule leads to continuous phase transitions. Convergence of the proportion of vertices in any largest component and convergence of the proportions of vertices in components of different orders are investigated. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C80 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60C05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6083940 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Random graph processes | |||
Property / zbMATH Keywords: Random graph processes / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
phase transition | |||
Property / zbMATH Keywords: phase transition / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
explosive percolation | |||
Property / zbMATH Keywords: explosive percolation / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1102.5306 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Explosive Percolation in Random Networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Avoiding a giant component / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Creating a Giant Component / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Evolution of Random Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3286850 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Phase transitions for modified Erdős--Rényi processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3496342 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Potpourri / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Birth control for giants / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4938890 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1979727552 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:11, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Achlioptas process phase transitions are continuous |
scientific article |
Statements
Achlioptas process phase transitions are continuous (English)
0 references
19 September 2012
0 references
In the well-known Erdős-Rényi graph sequence, the initial graph \(G(0)\) is the empty graph on \(n\) vertices, and \(G(m)\) is obtained from \(G(m-1)\) by inserting an edge at a randomly selected empty vertex-pair site for \(m=1,2,\dots\). The proportion of vertices in the largest connected component converges in probability to zero if and only if \(m/n\) converges to a value not larger than \(1/2\). This phase transition at the critical value \(1/2\) can be changed by modifying the rule for edge selections. It has been conjectured that a certain ``product rule'' exhibits so called ``explosive percolation''. This conjecture is here disproved by investigating a general edge selection rule which specifies how at least one edge is inserted among the vertex-pair sites in a random fixed-size sample of vertices. It is shown that this rule leads to continuous phase transitions. Convergence of the proportion of vertices in any largest component and convergence of the proportions of vertices in components of different orders are investigated.
0 references
Random graph processes
0 references
phase transition
0 references
explosive percolation
0 references