Name
Abstract | ||
|---|---|---|
The K-4-free process starts with the empty graph on n vertices and at each step adds a new edge chosen uniformly at random from all remaining edges that do not complete a copy of K-4. Let G be the random maximal K-4-free graph obtained at the end of the process. We show that for some positive constant C, with high probability as n ->infinity, the maximum degree in G is at most Cn3/5logn5. This resolves a conjecture of Bohman and Keevash for the K-4-free process and improves on previous bounds obtained by Bollobas and Riordan and by Osthus and Taraz. Combined with results of Bohman and Keevash this shows that with high probability G has Theta(n8/5logn5) edges and is 'nearly regular', i.e., every vertex has degree Theta(n3/5logn5). This answers a question of Erdos, Suen and Winkler for the K-4-free process. We furthermore deduce an additional structural property: we show that whp the independence number of G is at least omega(n2/5(logn)4/5/loglogn), which matches an upper bound obtained by Bohman up to a factor of Theta(loglogn). Our analysis of the K-4-free process also yields a new result in Ramsey theory: for a special case of a well-studied function introduced by Erdos and Rogers we slightly improve the best known upper bound.Copyright (c) 2012 Wiley Periodicals, Inc. Random Struct. Alg. , 44, 355-397, 2014 |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/rsa.20444 | Periodicals |
Keywords | Field | DocType |
H-free process,Ramsey theory,Random graph process | Ramsey theory,Discrete mathematics,Combinatorics,Vertex (geometry),Upper and lower bounds,struct,Null graph,Degree (graph theory),Conjecture,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
44 | 3 | 1042-9832 |
Citations | PageRank | References |
2 | 0.42 | 10 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lutz Warnke | 1 | 19 | 6.13 |