Abstract | ||
---|---|---|
In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed r∈ℕ, almost every n-vertex K r+1-free graph is r-partite. In this paper we extend this result to all functions r = r(n) with r ⩽ (logn)1/4. The proof combines a new (close to sharp) supersaturation version of the Erdős-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobás and Simonovits. |
Year | Venue | Field |
---|---|---|
2017 | Combinatorica | Discrete mathematics,Graph,Combinatorics,Hypergraph,Rothschild,Stability theorem,Mathematics |
DocType | Volume | Issue |
Journal | 37 | 4 |
Citations | PageRank | References |
2 | 0.41 | 9 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
József Balogh | 1 | 862 | 89.91 |
neal bushaw | 2 | 2 | 0.41 |
mauricio collares neto | 3 | 2 | 0.41 |
Hong Liu | 4 | 39 | 8.54 |
r a h morris | 5 | 2 | 0.41 |
Maryam Sharifzadeh | 6 | 11 | 3.83 |