{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T01:40:10Z","timestamp":1750470010642,"version":"3.41.0"},"reference-count":9,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T00:00:00Z","timestamp":1188604800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> be a graph with no three independent vertices. How many edges of <jats:italic>G<\/jats:italic> can be packed with edge-disjoint copies of <jats:italic>K<\/jats:italic><jats:sub>\n\t      <jats:italic>k<\/jats:italic>\n\t    <\/jats:sub>? More specifically, let <jats:italic>f<\/jats:italic><jats:sub>\n\t      <jats:italic>k<\/jats:italic>\n\t    <\/jats:sub>(<jats:italic>n<\/jats:italic>, <jats:italic>m<\/jats:italic>) be the largest integer <jats:italic>t<\/jats:italic> such that, for any graph with <jats:italic>n<\/jats:italic> vertices, <jats:italic>m<\/jats:italic> edges, and independence number 2, at least <jats:italic>t<\/jats:italic> edges can be packed with edge-disjoint copies of <jats:italic>K<\/jats:italic><jats:sub>\n\t      <jats:italic>k<\/jats:italic>\n\t    <\/jats:sub>. Tur\u00e1n's theorem together with Wilson's Theorem assert that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline1\">\n\t      <jats:alt-text>$f_k(n,m)=(1-o(1))\\frac{n^2}{4}$<\/jats:alt-text>\n\t    <\/jats:inline-graphic> if <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline2\">\n\t      <jats:alt-text>$m \\approx \\frac{n^2}{4}$<\/jats:alt-text>\n\t    <\/jats:inline-graphic>. A conjecture of Erd\u0151s states that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline3\">\n\t      <jats:alt-text>$f_3(n,m) \\geq (1-o(1))\\frac{n^2}{4}$<\/jats:alt-text>\n\t    <\/jats:inline-graphic> for all plausible <jats:italic>m<\/jats:italic>. For any \u03b5 &gt; 0, this conjecture was open even if <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline4\">\n\t      <jats:alt-text>$m \\leq n^2(\\frac{1}{4}+\\epsilon)$<\/jats:alt-text>\n\t    <\/jats:inline-graphic>. Generally, <jats:italic>f<\/jats:italic>_<jats:sub>\n\t      <jats:italic>k<\/jats:italic>\n\t    <\/jats:sub>(<jats:italic>n<\/jats:italic>,<jats:italic>m<\/jats:italic>) may be significantly smaller than <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline5\">\n\t      <jats:alt-text>$\\frac{n^2}{4}$<\/jats:alt-text>\n\t    <\/jats:inline-graphic>. Indeed, for <jats:italic>k<\/jats:italic>=7 it is easy to show that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline6\">\n\t      <jats:alt-text>$f_7(n,m) \\leq \\frac{21}{90}{n^2}$<\/jats:alt-text>\n\t    <\/jats:inline-graphic> for <jats:italic>m<\/jats:italic> \u2248 0.3<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>. Nevertheless, we prove the following result. For every <jats:italic>k<\/jats:italic>\u2265 3 there exists \u03b3&gt;0 such that if <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline7\">\n\t      <jats:alt-text>$m \\leq n^2(\\frac{1}{4}+\\gamma)$<\/jats:alt-text>\n\t    <\/jats:inline-graphic> then <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548306008194_inline8\">\n\t      <jats:alt-text>$f_k(n,m) \\geq (1-o(1))\\frac{n^2}{4}$<\/jats:alt-text>\n\t    <\/jats:inline-graphic>. In the special case <jats:italic>k<\/jats:italic>=3 we obtain the reasonable bound \u03b3 \u2265 10<jats:sup>\u22124<\/jats:sup>. In particular, the above conjecture of Erd\u0151s holds whenever <jats:italic>G<\/jats:italic> has fewer than 0.2501<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> edges.<\/jats:p>","DOI":"10.1017\/s0963548306008194","type":"journal-article","created":{"date-parts":[[2006,11,3]],"date-time":"2006-11-03T12:34:03Z","timestamp":1162557243000},"page":"805-817","source":"Crossref","is-referenced-by-count":2,"title":["Packing Cliques in Graphs with Independence Number 2"],"prefix":"10.1017","volume":"16","author":[{"given":"RAPHAEL","family":"YUSTER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,9,1]]},"reference":[{"key":"S0963548306008194_manual_ref-6","first-page":"279","volume-title":"Theory of Graphs","author":"Simonovits","year":"1968"},{"key":"S0963548306008194_manual_ref-7","first-page":"647","article-title":"Decomposition of complete graphs into subgraphs isomorphic to a given graph","volume":"XV","author":"Wilson","year":"1975","journal-title":"Congressus Numerantium"},{"doi-asserted-by":"publisher","key":"S0963548306008194_manual_ref-3","DOI":"10.1016\/S0012-365X(00)00312-5"},{"doi-asserted-by":"publisher","key":"S0963548306008194_manual_ref-4","DOI":"10.1007\/s004930170003"},{"doi-asserted-by":"publisher","key":"S0963548306008194_manual_ref-5","DOI":"10.1002\/jgt.20031"},{"doi-asserted-by":"publisher","key":"S0963548306008194_manual_ref-8","DOI":"10.1016\/j.jctb.2005.02.002"},{"doi-asserted-by":"publisher","key":"S0963548306008194_manual_ref-2","DOI":"10.1016\/S0012-365X(96)00044-1"},{"doi-asserted-by":"publisher","key":"S0963548306008194_manual_ref-9","DOI":"10.1002\/rsa.20048"},{"doi-asserted-by":"publisher","key":"S0963548306008194_manual_ref-1","DOI":"10.1007\/978-1-4612-0619-4"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548306008194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T01:12:39Z","timestamp":1750468359000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548306008194\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":9,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0963548306008194"],"URL":"https:\/\/doi.org\/10.1017\/s0963548306008194","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2007,9]]}}}