The phase transition in Achlioptas processes
46 mins 36 secs,
178.25 MB,
iPod Video
480x270,
29.97 fps,
44100 Hz,
522.25 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Riordan, O (University of Oxford)
Monday 11th July 2016 - 11:45 to 12:30 |
|---|
| Created: | 2016-07-19 10:28 |
|---|---|
| Collection: | Theoretical Foundations for Statistical Network Analysis |
| Publisher: | Isaac Newton Institute |
| Copyright: | Riordan, O |
| Language: | eng (English) |
| Distribution: |
World
(downloadable)
|
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| Abstract: | The classical random graph process starts with a fixed set of n vertices and no edges. Edges are then added one-by-one, uniformly at random. One of the most interesting features of this process, established by Erdős and Rényi more than 50 years ago, is the phase transition near n/2 edges, where a single `giant' component emerges from a sea of small components. This example serves as a starting point for understanding phase transitions in a wide variety of other contexts. Around 2000, Dimitris Achlioptas suggested an innocent-sounding variation of the model: at each stage two edges are selected at random, but only one is added, the choice depending on (typically) the sizes of the components it would connect. This may seem like a small change, but these processes do not have the key independence property that underlies our understanding of the classical process. One can ask many questions about Achlioptas processes; the most interesting concern the phase transition: does the critical value change from n/2? Is the nature of the transition the same or not? I will describe a number of results on these questions from joint work with Lutz Warnke. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.94 Mbits/sec | 678.59 MB | View | Download | |
| WebM | 640x360 | 674.12 kbits/sec | 230.17 MB | View | Download | |
| iPod Video * | 480x270 | 522.25 kbits/sec | 178.25 MB | View | Download | |
| MP3 | 44100 Hz | 249.78 kbits/sec | 85.34 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||