The typical structure of graphs with no large cliques

József Balogh; Neal Bushaw; Maurício Collares; Hong Liu; Robert Morris; Maryam Sharifzadeh

doi:10.1007/s00493-015-3290-9

The typical structure of graphs with no large cliques

József Balogh
, Neal Bushaw
, Maurício Collares
, Hong Liu
, Robert Morris
, Maryam Sharifzadeh

Mathematics

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	617-632
Number of pages	16
Journal	Combinatorica
Volume	37
Issue number	4
DOIs	https://doi.org/10.1007/s00493-015-3290-9
State	Published - Aug 1 2017

Keywords

05C30
05C35
05C75
05D40

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Online availability

10.1007/s00493-015-3290-9

Library availability

Discover UIUC Full Text

Cite this

@article{2577f8ccb2ec4614ac41a7a2354617eb,

title = "The typical structure of graphs with no large cliques",

abstract = "In 1987, Kolaitis, Pr{\"o}mel and Rothschild proved that, for every fixed r∈ℕ, almost every n-vertex Kr+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{\H o}s-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollob{\'a}s and Simonovits.",

keywords = "05C30, 05C35, 05C75, 05D40",

author = "J{\'o}zsef Balogh and Neal Bushaw and Maur{\'i}cio Collares and Hong Liu and Robert Morris and Maryam Sharifzadeh",

note = "Research supported in part by a Simons Fellowship, NSF CAREER Grant DMS-0745185, Marie Curie FP7-PEOPLE-2012-IIF 327763, Arnold O. Beckman Research Award (UIUC Campus Research Board 13039) (JB), CAPES bolsa Proex (MCN), a CNPq bolsa PDJ (NB) and a CNPq bolsa de Produtividade em Pesquisa (RM)",

year = "2017",

month = aug,

day = "1",

doi = "10.1007/s00493-015-3290-9",

language = "English (US)",

volume = "37",

pages = "617--632",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - The typical structure of graphs with no large cliques

AU - Balogh, József

AU - Bushaw, Neal

AU - Collares, Maurício

AU - Liu, Hong

AU - Morris, Robert

AU - Sharifzadeh, Maryam

N1 - Research supported in part by a Simons Fellowship, NSF CAREER Grant DMS-0745185, Marie Curie FP7-PEOPLE-2012-IIF 327763, Arnold O. Beckman Research Award (UIUC Campus Research Board 13039) (JB), CAPES bolsa Proex (MCN), a CNPq bolsa PDJ (NB) and a CNPq bolsa de Produtividade em Pesquisa (RM)

PY - 2017/8/1

Y1 - 2017/8/1

N2 - In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed r∈ℕ, almost every n-vertex Kr+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.

AB - In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed r∈ℕ, almost every n-vertex Kr+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.

KW - 05C30

KW - 05C35

KW - 05C75

KW - 05D40

UR - https://www.scopus.com/pages/publications/84966550531

UR - https://www.scopus.com/pages/publications/84966550531#tab=citedBy

U2 - 10.1007/s00493-015-3290-9

DO - 10.1007/s00493-015-3290-9

M3 - Article

AN - SCOPUS:84966550531

SN - 0209-9683

VL - 37

SP - 617

EP - 632

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

The typical structure of graphs with no large cliques

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this