Achlioptas process phase transitions are continuous (Q453240): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
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 |
Revision as of 11:56, 30 June 2023
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