Random graph processes are basic mathematical models for large-scale networks evolving over time. Their systematic study was pioneered by Erdös and Rényi around 1960, and one key feature of many 'classical' models is that the edges appear independently. While this makes them amenable to a rigorous analysis, it is desirable, both mathematically and in terms of applications, to understand more complicated situations. In this thesis the main goal is to improve our rigorous understanding of evolving random graphs with significant dependencies. The first model we consider is known as an Achlioptas process: in each step two random edges are chosen, and using a given rule only one of them is selected and added to the evolving graph. Since 2000 a large class of 'complex' rules has eluded a rigorous analysis, and it was widely believed that these could give rise to a striking and unusual phenomenon. Making this explicit, Achlioptas, D'Souza and Spencer conjectured in Science that one such rule yields a very abrupt (discontinuous) percolation phase transition. We disprove this, showing that the transition is in fact continuous for all Achlioptas process. In addition, we give the first rigorous analysis of the more 'complex' rules, proving that certain key statistics are tightly concentrated (i) in the subcritical evolution, and (ii) also later on if an associated system of differential equations has a unique solution. The second model we study is the H-free process, where random edges are added subject to the constraint that they do not complete a copy of some fixed graph H. The most important open question for such 'constrained' processes is due to Erdös, Suen and Winkler: in 1995 they asked what the typical final number of edges is. While Osthus and Taraz answered this in 2000 up to logarithmic factors for a large class of graphs H, more precise bounds are only known for a few special graphs. We close this gap for the cases where a cycle of fixed length is forbidden, determining the final number of edges up to constants. Our result not only establishes several conjectures, it is also the first which answers the more than 15-year old question of Erdös et. al. for a class of forbidden graphs H.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:581022 |
| Date | January 2012 |
| Creators | Warnke, Lutz |
| Contributors | Riordan, Oliver |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://ora.ox.ac.uk/objects/uuid:71b48e5f-a192-4684-a864-ea9059a25d74 |
Page generated in 0.002 seconds