2016/02/06 by Heiner Oberkampf, Oberkampf, Heiner, Mathias Schacht +1 · 1 citation
Computer Science · Mathematics · #005C75 (secondary) #05C35 (primary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:005C75 #msc:05C35
paper · pdf · doi:10.48550/arxiv.1602.02302
arxiv created 2016/02/06 · openalex publication_date 2016/02/06 · arxiv updated 2016/02/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study structural properties of graphs with fixed clique number and high minimum degree. In particular, we show that there exists a function L=L(r,ε), such that every Kr-free graph G on n vertices with minimum degree at least ((2r-5)/(2r-3)+ε)n is homomorphic to a Kr-free graph on at most L vertices. It is known that the required minimum degree condition is approximately best possible for this result. For r=3 this result was obtained by Łuczak [On the structure of triangle-free graphs of large minimum degree, Combinatorica 26 (2006), no. 4, 489-493] and, more recently, Goddard and Lyle [Dense graphs with small clique number, J. Graph Theory 66 (2011), no. 4, 319-331] deduced the general case from Łuczak's result. Łuczak's proof was based on an application of Szemerédi's regularity lemma and, as a consequence, it only gave rise to a tower-type bound on L(3,ε). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for L(r,ε) that is doubly exponential in poly(ε).