Abstract | ||
---|---|---|
AbstractThe Cï -free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of Cï is created. For every ï ï 4 we show that, with high probability as nï ∞, the maximum degree is Onlogn1/ï -1, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the Cï -free process typically terminates with ï nï /ï -1logn1/ï -1 edges, which answers a question of Erdï s, Suen and Winkler. This is the first result that determines the final number of edges of the more general H-free process for a non-trivial class of graphs H. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to 'transfer' certain decreasing properties from the binomial random graph to the H-free process. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 490-526, 2014 |
Year | DOI | Venue |
---|---|---|
2014 | 10.1002/rsa.20468 | Periodicals |
Keywords | DocType | Volume |
H-free process,random graph process,differential equation method | Journal | 44 |
Issue | ISSN | Citations |
4 | 1042-9832 | 3 |
PageRank | References | Authors |
0.43 | 7 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lutz Warnke | 1 | 19 | 6.13 |