{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T13:27:15Z","timestamp":1776691635394,"version":"3.51.2"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2004,1,19]],"date-time":"2004-01-19T00:00:00Z","timestamp":1074470400000},"content-version":"unspecified","delay-in-days":18,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>The aim of this paper is to prove a Tur\u00e1n-type theorem for random graphs. For <jats:inline-formula>$\\gamma &gt;0$<\/jats:inline-formula> and graphs <jats:inline-formula>$G$<\/jats:inline-formula> and <jats:inline-formula>$H$<\/jats:inline-formula>, write <jats:inline-formula>$G\\to_\\gamma H$<\/jats:inline-formula> if any <jats:inline-formula>$\\gamma$<\/jats:inline-formula>-proportion of the edges of <jats:inline-formula>$G$<\/jats:inline-formula> spans at least one copy of <jats:inline-formula>$H$<\/jats:inline-formula> in <jats:inline-formula>$G$<\/jats:inline-formula>. We show that for every graph <jats:inline-formula>$H$<\/jats:inline-formula> and every fixed real <jats:inline-formula>$\\delta&gt;0$<\/jats:inline-formula>, almost every graph <jats:inline-formula>$G$<\/jats:inline-formula> in the binomial random graph model <jats:inline-formula>$\\cG(n,q)$<\/jats:inline-formula>, with <jats:inline-formula>$q=q(n)\\gg((\\log n)^4\/n)^{1\/d(H)}$<\/jats:inline-formula>, satisfies <jats:inline-formula>$G\\to_{(\\chi(H)-2)\/(\\chi(H)-1)+\\delta}H$<\/jats:inline-formula>, where as usual <jats:inline-formula>$\\chi(H)$<\/jats:inline-formula> denotes the chromatic number of <jats:inline-formula>$H$<\/jats:inline-formula> and <jats:inline-formula>$d(H)$<\/jats:inline-formula> is the \u2018degeneracy number\u2019 of <jats:inline-formula>$H$<\/jats:inline-formula>.<\/jats:p>\n\t  <jats:p>Since <jats:inline-formula>$K_l$<\/jats:inline-formula>, the complete graph on <jats:inline-formula>$l$<\/jats:inline-formula> vertices, is <jats:inline-formula>$l$<\/jats:inline-formula>-chromatic and <jats:inline-formula>$(l-1)$<\/jats:inline-formula>-degenerate, we infer that for every <jats:inline-formula>$l\\geq2$<\/jats:inline-formula> and every fixed real <jats:inline-formula>$\\delta&gt;0$<\/jats:inline-formula>, almost every graph <jats:inline-formula>$G$<\/jats:inline-formula> in the binomial random graph model <jats:inline-formula>$\\cG(n,q)$<\/jats:inline-formula>, with <jats:inline-formula>$q=q(n)\\gg((\\log n)^4\/n)^{1\/(l-1)}$<\/jats:inline-formula>, satisfies <jats:inline-formula>$G\\to_{(l-2)\/(l-1)+\\delta}K_l$<\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548303005856","type":"journal-article","created":{"date-parts":[[2004,1,20]],"date-time":"2004-01-20T13:35:49Z","timestamp":1074605749000},"page":"61-91","source":"Crossref","is-referenced-by-count":21,"title":["The Tur\u00e1n Theorem for Random Graphs"],"prefix":"10.1017","volume":"13","author":[{"given":"YOSHIHARU","family":"KOHAYAKAWA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VOJT\u011aCH","family":"R\u00d6DL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MATHIAS","family":"SCHACHT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2004,1,19]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548303005856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T03:01:54Z","timestamp":1750474914000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548303005856\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["S0963548303005856"],"URL":"https:\/\/doi.org\/10.1017\/s0963548303005856","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}