Paper Info
Title
The Final Size of the Cℓ-free Process.
Abstract
We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of C4. We show that, with probability tending to 1 as n â聠聮 ∞, the final graph produced by this process has maximum degree O((nlogn)1/3) and consequently size O(n4/3(logn)1/3), which are sharp up to constants. This confirms conjectures of Bohman and Keevash and of Osthus and Taraz, and improves upon previous bounds due to Bollobás and Riordan and Osthus and Taraz.
Year
DOI
Venue
2011
10.1017/S0963548311000368
SIAM J. Discrete Math.
Keywords
DocType
Volume
following random graph process,final graph,c4-free process,maximum degree,final size,n isolated vertex,previous bound
Journal
28
Issue
ISSN
Citations 
3
0963-5483
0
PageRank 
References 
Authors
0.34
6
1
Name
Order
Citations
PageRank
Michael E. Picollelli1102.56