We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the structure of Dense graphs with bounded clique number.
- Authors
Oberkampf, Heiner; Schacht, Mathias
- Abstract
We study structural properties of graphs with bounded 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 (2006) and, more recently, Goddard and Lyle (2011) 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(ɛ).
- Subjects
DENSE graphs; HOMOMORPHISMS; EVIDENCE
- Publication
Combinatorics, Probability & Computing, 2020, Vol 29, Issue 5, p641
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548319000324