The phase transition in Achlioptas processes
46 mins 37 secs,
230.17 MB,
WebM
640x360,
29.97 fps,
44100 Hz,
674.12 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) |