{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T02:27:29Z","timestamp":1787365649945,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["426894"],"award-info":[{"award-number":["426894"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["522400"],"award-info":[{"award-number":["522400"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number $\\tau(G)$ is at most twice the triangle packing number $\\nu(G)$, where the triangle packing number $\\nu(G)$ is the maximum size of a set of edge-disjoint triangles in $G$ and the triangle covering number $\\tau(G)$ is the minimal size of a set of edges intersecting all triangles. In this paper, we prove that Tuza's conjecture holds in the Erd\u00f6s--R\u00e9nyi random graph $G(n,m)$ for all ranges of $m$, closing the \u201cgap\u201d in what was previously known. (Recently, this result was also independently proved by Jeff Kahn and Jinyoung Park.) We employ a random greedy process called the online triangle packing process to produce a triangle packing in $G(n,m)$ and analyze this process by using the differential equations method.<\/jats:p>","DOI":"10.1137\/20m1351771","type":"journal-article","created":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T12:00:46Z","timestamp":1632139246000},"page":"2145-2169","source":"Crossref","is-referenced-by-count":2,"title":["Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process"],"prefix":"10.1137","volume":"35","author":[{"given":"Patrick","family":"Bennett","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Cushman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Dudek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22533"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-005-0628-x"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000067"},{"key":"atypb5","unstructured":"A. Basit and D. Galvin,\n                      personal communication\n                      , 2019."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548320000115"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.02.018"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2015.04.015"},{"key":"atypb9","first-page":"489","volume":"2013","author":"Bohman T.","journal-title":"Italy"},{"key":"atypb10","first-page":"292","author":"Bollob\u00e1s B.","year":"2000","journal-title":"NJ"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1998.12004872"},{"key":"atypb12","first-page":"15","author":"Bollob\u00e1s B.","year":"2009","journal-title":"Berlin"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760037"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060217"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"G. Fiz Pontiveros, S. Griffiths, and R. Morris,\n                      The Triangle-Free Process and $R(3,k)$\n                      , Mem. Amer. Math. Soc. 263, American Mathematical Society, Providence, RI, 2020.","DOI":"10.1090\/memo\/1274"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80045-7"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788087"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00183-6"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb22","unstructured":"J. Kahn and J. Park,\n                      Tuza's Conjecture for Random Graphs\n                      , preprint, arXiv:2007.04351, 2020,http:\/\/arxiv.org\/abs\/2007.04351."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)00228-W"},{"key":"atypb24","unstructured":"S. Janson, T. \u0141 uczak, and A. Ruci\u0144ski,\n                      Random Graphs\n                      , Wiley-Interscience, New York, 2009."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21821"},{"key":"atypb26","first-page":"888","author":"Tuza Zs.","year":"1984","journal-title":"Netherlands"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000103"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000235"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1351771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:23Z","timestamp":1787321243000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1351771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1351771"],"URL":"https:\/\/doi.org\/10.1137\/20m1351771","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}