We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Turán Theorem for Random Graphs.
- Authors
YOSHIHARU KOHAYAKAWA; VOJTĚCH RÖDL; MATHIAS SCHACHT
- Abstract
The aim of this paper is to prove a Turán-type theorem for random graphs. For $\gamma >0$ and graphs $G$</formtex> and $H$</formtex>, write $G\to_\gamma H$</formtex> if any $\gamma$</formtex>-proportion of the edges of $G$</formtex> spans at least one copy of $H$</formtex> in $G$</formtex>. We show that for every graph $H$</formtex> and every fixed real $\delta>0$</formtex>, almost every graph $G$</formtex> in the binomial random graph model $\cG(n,q)$</formtex>, with $q=q(n)\gg((\log n)^4/n)^{1/d(H)}$</formtex>, satisfies $G\to_{(\chi(H)-2)/(\chi(H)-1)+\delta}H$</formtex>, where as usual $\chi(H)$</formtex> denotes the chromatic number of $H$</formtex> and $d(H)$</formtex> is the degeneracy number of $H$</formtex>. Since $K_l$</formtex>, the complete graph on $l$</formtex> vertices, is $l$</formtex>-chromatic and $(l-1)$</formtex>-degenerate, we infer that for every $l\geq2$</formtex> and every fixed real $\delta>0$</formtex>, almost every graph $G$</formtex> in the binomial random graph model $\cG(n,q)$</formtex>, with $q=q(n)\gg((\log n)^4/n)^{1/(l-1)}$</formtex>, satisfies $G\to_{(l-2)/(l-1)+\delta}K_l$</formtex>.
- Subjects
RANDOM graphs; GRAPH theory; BINOMIAL theorem; COLOR; COMBINATORICS; ALGEBRA
- Publication
Combinatorics, Probability & Computing, 2004, Vol 13, Issue 1, p61
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/s0963548303005856