{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:23:51Z","timestamp":1767014631163,"version":"3.48.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T00:00:00Z","timestamp":1764547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T00:00:00Z","timestamp":1764720000000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001661","name":"Ruprecht-Karls-Universit\u00e4t Heidelberg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001661","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,12]]},"abstract":"Abstract<\/jats:title>\n \n We consider the question of how many edge-disjoint near-maximal cliques may be found in the dense Erd\u0151s-R\u00e9nyi random graph\n G<\/jats:italic>\n (\n n<\/jats:italic>\n ,\u00a0\n p<\/jats:italic>\n ). Recently Acan and Kahn showed that the largest such family contains only\n \n \n $$O(n^2\/(\\log {n})^3)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n cliques, with high probability, which disproved a conjecture of Alon and Spencer. We prove the corresponding lower bound,\n \n \n $$\\Omega (n^2\/(\\log {n})^3)$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , by considering a random graph process which sequentially selects and deletes near-maximal cliques. To analyse this process we use the Differential Equation Method. We also give a new proof of the upper bound\n \n \n $$O(n^2\/(\\log {n})^3)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \/<\/mml:mo>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and discuss the problem of the precise size of the largest such clique packing.\n <\/jats:p>","DOI":"10.1007\/s00493-025-00188-6","type":"journal-article","created":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T09:05:23Z","timestamp":1764752723000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Clique packings in random graphs"],"prefix":"10.1007","volume":"45","author":[{"given":"Simon","family":"Griffiths","sequence":"first","affiliation":[]},{"given":"Let\u00edcia","family":"Mattos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,3]]},"reference":[{"key":"188_CR1","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1002\/rsa.20884","volume":"55","author":"H Acan","year":"2019","unstructured":"Acan, H., Kahn, J.: Disproof of a packing conjecture of Alon and Spencer. Random Structures Algorithms 55, 531\u2013544 (2019)","journal-title":"Random Structures Algorithms"},{"key":"188_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Spencer, J.: The Probablistic Method. Wiley, New York (2008)","DOI":"10.1002\/9780470277331"},{"key":"188_CR3","unstructured":"Allen,P., B\u00f6ttcher,J., Clemens,D., Hladk\u1ef3,J., Piguet,D., Taraz,A.: The tree packing conjecture for trees of almost linear maximum degree, arXiv: 2106.11720 (2021)"},{"key":"188_CR4","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s11856-022-2447-7","volume":"255","author":"P Allen","year":"2023","unstructured":"Allen, P., B\u00f6ttcher, J., Clemens, D., Taraz, A.: Perfectly packing graphs with bounded degeneracy and many leaves. Israel J. Math. 255, 501\u2013579 (2023)","journal-title":"Israel J. Math."},{"key":"188_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2019.106739","volume":"354","author":"P Allen","year":"2019","unstructured":"Allen, P., B\u00f6ttcher, J., Hladk\u1ef3, J., Piguet, D.: Packing degenerate graphs. Adv. Math. 354, 106739 (2019)","journal-title":"Adv. Math."},{"key":"188_CR6","doi-asserted-by":"publisher","first-page":"357","DOI":"10.2748\/tmj\/1178243286","volume":"19","author":"K Azuma","year":"1967","unstructured":"Azuma, K.: Weighted sums of certain dependent random variables. Tohoku Math. J. 19, 357\u2013367 (1967)","journal-title":"Tohoku Math. J."},{"key":"188_CR7","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s11856-015-1277-2","volume":"211","author":"J B\u00f6ttcher","year":"2016","unstructured":"B\u00f6ttcher, J., Hladk\u00fd, J., Piguet, D., Taraz, A.: An approximate version of the tree packing conjecture. Israel J. Math. 211, 391\u2013446 (2016)","journal-title":"Israel J. Math."},{"key":"188_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2022.113071","volume":"345","author":"P Bennett","year":"2022","unstructured":"Bennett, P., Dudek, A.: A gentle introduction to the differential equation method and dynamic concentration. Discr. Math. 345, 113071 (2022)","journal-title":"Discr. Math."},{"key":"188_CR9","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1016\/j.aim.2009.02.018","volume":"221","author":"T Bohman","year":"2009","unstructured":"Bohman, T.: The triangle-free process. Adv. Math. 221, 1653\u20131677 (2009)","journal-title":"Adv. Math."},{"key":"188_CR10","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.aim.2015.04.015","volume":"280","author":"T Bohman","year":"2015","unstructured":"Bohman, T., Frieze, A., Lubetzky, E.: Random triangle removal. Adv. Math. 280, 379\u2013438 (2015)","journal-title":"Adv. Math."},{"key":"188_CR11","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00222-010-0247-x","volume":"181","author":"T Bohman","year":"2010","unstructured":"Bohman, T., Keevash, P.: The early evolution of the $$H$$-free process. Invent. Math. 181, 291\u2013336 (2010)","journal-title":"Invent. Math."},{"key":"188_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/rsa.20973","volume":"58","author":"T Bohman","year":"2021","unstructured":"Bohman, T., Keevash, P.: Dynamic Concentration of the Triangle-Free Process. Random Structures Algorithms 58, 177\u2013380 (2021)","journal-title":"Random Structures Algorithms"},{"key":"188_CR13","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02122551","volume":"8","author":"B Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B.: The chromatic number of random graphs. Combinatorica 8, 49\u201355 (1988)","journal-title":"Combinatorica"},{"key":"188_CR14","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1017\/S0305004100053056","volume":"80","author":"B Bollob\u00e1s","year":"1976","unstructured":"Bollob\u00e1s, B., Erd\u0151s, P.: Cliques in random graphs. Math. Proc. of the Cambridge Phil. Soc. 80, 419\u2013427 (1976)","journal-title":"Math. Proc. of the Cambridge Phil. Soc."},{"key":"188_CR15","unstructured":"Delcourt,M., Kelly,T., Postle,L.: Clique Decompositions in Random Graphs via Refined Absorption, arXiv:2402.17857 (2024)"},{"key":"188_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.cosrev.2010.04.002","volume":"4","author":"J D\u00edaz","year":"2010","unstructured":"D\u00edaz, J., Mitsche, D.: The cook-book approach to the differential equation method. Comp. Sci. Rev. 4, 129\u2013151 (2010)","journal-title":"Comp. Sci. Rev."},{"key":"188_CR17","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1007\/s11856-017-1504-0","volume":"219","author":"A Ferber","year":"2019","unstructured":"Ferber, A., Lee, C., Mousset, F.: Packing spanning graphs from separable families. Israel J. Math. 219, 959\u2013982 (2019)","journal-title":"Israel J. Math."},{"key":"188_CR18","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1112\/jlms.12179","volume":"99","author":"A Ferber","year":"2019","unstructured":"Ferber, A., Samotij, W.: Packing trees of unbounded degrees in random graphs. J. London Math. Soc. 99, 653\u2013677 (2019)","journal-title":"J. London Math. Soc."},{"key":"188_CR19","doi-asserted-by":"crossref","unstructured":"Fiz\u00a0Pontiveros,G., Griffiths,S., Morris,R.: The Triangle-Free Process and the Ramsey Number $$R(3,k)$$, Mem. Amer. Math. Soc., 263 (2020), 125pp","DOI":"10.1090\/memo\/1274"},{"key":"188_CR20","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0195-6698(85)80045-7","volume":"6","author":"P Frankl","year":"1985","unstructured":"Frankl, P., R\u00f6dl, V.: Near perfect coverings in graphs and hypergraphs. Europ. J. Comb. 6, 317\u2013326 (1985)","journal-title":"Europ. J. Comb."},{"key":"188_CR21","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1214\/aop\/1176996452","volume":"3","author":"DA Freedman","year":"1975","unstructured":"Freedman, D.A.: On tail probabilities for martingales. Ann. Probab. 3, 100\u2013118 (1975)","journal-title":"Ann. Probab."},{"key":"188_CR22","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.jctb.2004.12.003","volume":"94","author":"A Frieze","year":"2005","unstructured":"Frieze, A., Krivelevich, M.: On packing Hamilton cycles in $$\\varepsilon $$-regular graphs. J. Comb. Theory Ser. B 94, 159\u2013172 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"188_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20396","volume":"41","author":"A Frieze","year":"2012","unstructured":"Frieze, A., Krivelevich, M.: Packing Hamilton cycles in random and pseudo-random hypergraphs. Random Structures Algorithms 41, 1\u201322 (2012)","journal-title":"Random Structures Algorithms"},{"key":"188_CR24","first-page":"1","volume":"284","author":"S Glock","year":"2023","unstructured":"Glock, S., K\u00fchn, D., Lo, A., Osthus, D.: The existence of designs via iterative absorption: hypergraph $$F$$-designs for arbitrary $$F$$. Mem. Amer. Math. Soc. 284, 1\u2013131 (2023)","journal-title":"Mem. Amer. Math. Soc."},{"key":"188_CR25","doi-asserted-by":"crossref","unstructured":"Grable,D. A.: On random greedy triangle packing, Electr. J. Combin., 4 (1997), 19pp","DOI":"10.37236\/1296"},{"key":"188_CR26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13\u201330 (1963)","journal-title":"J. Amer. Statist. Assoc."},{"key":"188_CR27","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/rsa.3240010209","volume":"1","author":"S Janson","year":"1990","unstructured":"Janson, S.: Poisson approximation for large deviations. Random Structures Algorithms 1, 221\u2013230 (1990)","journal-title":"Random Structures Algorithms"},{"key":"188_CR28","doi-asserted-by":"crossref","unstructured":"Janson,S., \u0141uczak,T., Ruci\u0144ski,A.: Random graphs, Wiley-Interscience, 2000","DOI":"10.1002\/9781118032718"},{"key":"188_CR29","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1002\/rsa.10031","volume":"20","author":"S Janson","year":"2002","unstructured":"Janson, S., Ruci\u0144ski, A.: The infamous upper tail. Random Structures Algorithms 20, 317\u2013342 (2002)","journal-title":"Random Structures Algorithms"},{"key":"188_CR30","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00493-004-0038-3","volume":"24","author":"S Janson","year":"2004","unstructured":"Janson, S., Ruci\u0144ski, A.: The deletion method for upper tail estimates. Combinatorica 24, 615\u2013640 (2004)","journal-title":"Combinatorica"},{"key":"188_CR31","doi-asserted-by":"publisher","first-page":"3573","DOI":"10.4171\/jems\/909","volume":"21","author":"F Joos","year":"2019","unstructured":"Joos, F., Kim, J., K\u00fchn, D., Osthus, D.: Optimal packings of bounded degree trees. J. Europ. Math. Soc. 21, 3573\u20133647 (2019)","journal-title":"J. Europ. Math. Soc."},{"key":"188_CR32","doi-asserted-by":"crossref","unstructured":"Karp,R.M., Sipser,M.: Maximum matchings in sparse random graphs, Proc. 22nd Ann. IEEE Symp. Found. Comp. (1981), 364\u2013375","DOI":"10.1109\/SFCS.1981.21"},{"key":"188_CR33","unstructured":"Keevash,P.: The existence of designs, arXiv:1401.3665 (2014)"},{"key":"188_CR34","unstructured":"Keevash,P.: The existence of designs II, arXiv:1802.05900 (2018)"},{"key":"188_CR35","doi-asserted-by":"publisher","first-page":"1769","DOI":"10.4171\/jems\/1604","volume":"27","author":"P Keevash","year":"2025","unstructured":"Keevash, P., Staden, K.: Ringel\u2019s tree packing conjecture in quasirandom graphs. J. Eur. Math. Soc. (JEMS) 27, 1769\u20131826 (2025)","journal-title":"J. Eur. Math. Soc. (JEMS)"},{"key":"188_CR36","doi-asserted-by":"publisher","first-page":"4655","DOI":"10.1090\/tran\/7411","volume":"371","author":"J Kim","year":"2019","unstructured":"Kim, J., K\u00fchn, D., Osthus, D., Tyomkyn, M.: A blow-up lemma for approximate decompositions. Trans. Amer. Math Soc. 371, 4655\u20134742 (2019)","journal-title":"Trans. Amer. Math Soc."},{"key":"188_CR37","doi-asserted-by":"publisher","first-page":"49","DOI":"10.2307\/3212147","volume":"7","author":"TG Kurtz","year":"1970","unstructured":"Kurtz, T.G.: Solutions of ordinary differential equations as limits of pure Markov jump processes. J. Appl. Probab. 7, 49\u201358 (1970)","journal-title":"J. Appl. Probab."},{"key":"188_CR38","unstructured":"Matula,D.: On the complete subgraphs of a random graph, Proc. 2nd Chapel Hill Conf. Combin. Math. Appl., 356\u2013369"},{"key":"188_CR39","first-page":"89","volume":"19","author":"D Matula","year":"1972","unstructured":"Matula, D.: The employee party problem. Notices Amer. Math. Soc. 19, 89\u2013156 (1972)","journal-title":"Notices Amer. Math. Soc."},{"key":"188_CR40","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.jctb.2016.03.003","volume":"119","author":"S Messuti","year":"2016","unstructured":"Messuti, S., R\u00f6dl, V., Schacht, M.: Packing minor-closed families of graphs into complete graphs. J. Combin. Theory Ser. B 119, 245\u2013265 (2016)","journal-title":"J. Combin. Theory Ser. B"},{"key":"188_CR41","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/s00039-021-00576-2","volume":"31","author":"R Montgomery","year":"2021","unstructured":"Montgomery, R., Pokrovskiy, A., Sudakov, B.: A proof of Ringel\u2019s conjecture. Geom. Funct. Anal. 31, 663\u2013720 (2021)","journal-title":"Geom. Funct. Anal."},{"key":"188_CR42","unstructured":"Pl\u00fccker,J.: System der analytischen Geometrie, auf neue Betrachtungsweisen gegr\u00fcndet, und insbesondere eine ausf\u00fchrliche Theorie der Curven dritter Ordnung enthaltend, Duncker und Humblot, 1835"},{"key":"188_CR43","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<161::AID-RSA1>3.0.CO;2-W","volume":"8","author":"V R\u00f6dl","year":"1996","unstructured":"R\u00f6dl, V., Thoma, L.: Asymptotic packing and the random greedy algorithm. Random Structures Algorithms 8, 161\u2013177 (1996)","journal-title":"Random Structures Algorithms"},{"key":"188_CR44","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/rsa.3240070206","volume":"7","author":"J Spencer","year":"1995","unstructured":"Spencer, J.: Asymptotic packing via a branching process. Random Structures Algorithms 7, 167\u2013172 (1995)","journal-title":"Random Structures Algorithms"},{"key":"188_CR45","unstructured":"Warnke,L.: On Wormald\u2019s differential equation method, arXiv:1905.08928 (2019)"},{"key":"188_CR46","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0097-3165(75)90067-9","volume":"18","author":"R Wilson","year":"1975","unstructured":"Wilson, R.: An existence theory for pairwise balanced designs, III: Proof of the existence conjectures. J. Combin. Theory Ser. A 18, 71\u201379 (1975)","journal-title":"J. Combin. Theory Ser. A"},{"key":"188_CR47","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N Wormald","year":"1995","unstructured":"Wormald, N.: Differential equations for random processes and random graphs. Ann. Appl. Probab. 5, 1217\u20131235 (1995)","journal-title":"Ann. Appl. Probab."},{"key":"188_CR48","unstructured":"Wormald, N.: The differential equation method for random graph processes and greedy algorithms, pp. 73\u2013155. PWN Warsaw, Lectures on Approximation and Randomized Algorithms (1999)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00188-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00188-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00188-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:18:01Z","timestamp":1767014281000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00188-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["188"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00188-6","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"4 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"63"}}