{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T09:15:48Z","timestamp":1692868548452},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T00:00:00Z","timestamp":1595376000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The triangle packing number <jats:italic>v<\/jats:italic>(<jats:italic>G<\/jats:italic>) of a graph <jats:italic>G<\/jats:italic> is the maximum size of a set of edge-disjoint triangles in <jats:italic>G<\/jats:italic>. Tuza conjectured that in any graph <jats:italic>G<\/jats:italic> there exists a set of at most 2<jats:italic>v<\/jats:italic>(<jats:italic>G<\/jats:italic>) edges intersecting every triangle in <jats:italic>G<\/jats:italic>. We show that Tuza\u2019s conjecture holds in the random graph <jats:italic>G<\/jats:italic> = <jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>, <jats:italic>m<\/jats:italic>), when <jats:italic>m<\/jats:italic> \u2a7d 0.2403<jats:italic>n<\/jats:italic><jats:sup>3\/2<\/jats:sup> or <jats:italic>m<\/jats:italic> \u2a7e 2.1243<jats:italic>n<\/jats:italic><jats:sup>3\/2<\/jats:sup>. This is done by analysing a greedy algorithm for finding large triangle packings in random graphs.<\/jats:p>","DOI":"10.1017\/s0963548320000115","type":"journal-article","created":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T05:56:48Z","timestamp":1595397408000},"page":"757-779","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Large triangle packings and Tuza\u2019s conjecture in sparse random graphs"],"prefix":"10.1017","volume":"29","author":[{"given":"Patrick","family":"Bennett","sequence":"first","affiliation":[]},{"given":"Andrzej","family":"Dudek","sequence":"additional","affiliation":[]},{"given":"Shira","family":"Zerbib","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,7,22]]},"reference":[{"key":"S0963548320000115_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"key":"S0963548320000115_ref23","unstructured":"[23] Wormald, N. (1999) The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms (M. Karo\u0144ski and H. J. Pr\u00f6mel, eds), pp. 73\u2013155, PWN."},{"key":"S0963548320000115_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)00228-W"},{"key":"S0963548320000115_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80045-7"},{"key":"S0963548320000115_ref13","first-page":"1274","article-title":"The triangle-free process and R(3,k)","volume":"263","author":"Fiz Pontiveros","year":"2020","journal-title":"Mem. Amer. Math. Soc."},{"key":"S0963548320000115_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000235"},{"key":"S0963548320000115_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060217"},{"key":"S0963548320000115_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760037"},{"key":"S0963548320000115_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"S0963548320000115_ref8","first-page":"209","article-title":"To prove and conjecture: Paul Erd\u00f6s and his mathematics","volume":"105","author":"Bollob\u00e1s","year":"1998","journal-title":"Amer. Math. Monthly"},{"key":"S0963548320000115_ref4","unstructured":"[4] Basit, A. and Galvin, D. Personal communication."},{"key":"S0963548320000115_ref10","first-page":"15","volume-title":"Handbook of Large-Scale Random Networks","author":"Bollob\u00e1s","year":"2009"},{"key":"S0963548320000115_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2009.02.018"},{"key":"S0963548320000115_ref1","article-title":"A generalization of Tuza\u2019s conjecture","author":"Aharoni","journal-title":"J. Graph Theory."},{"key":"S0963548320000115_ref9","doi-asserted-by":"publisher","DOI":"10.1142\/9789812813428_0007"},{"key":"S0963548320000115_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000067"},{"key":"S0963548320000115_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00183-6"},{"key":"S0963548320000115_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21821"},{"key":"S0963548320000115_ref21","unstructured":"[21] Tuza, Z. (1984) A conjecture. In Finite and Infinite Sets (Eger, Hungary 1981) (A. Hajnal et al., eds), Vol. 37 of Proc. Colloq. Math. Soc. J. Bolyai, p. 888, North-Holland."},{"key":"S0963548320000115_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-005-0628-x"},{"key":"S0963548320000115_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000103"},{"key":"S0963548320000115_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-88-7642-475-5_78"},{"key":"S0963548320000115_ref18","volume-title":"Random Graphs","author":"Janson","year":"2009"},{"key":"S0963548320000115_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2015.04.015"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,14]],"date-time":"2020-09-14T12:06:29Z","timestamp":1600085189000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000115\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,22]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S0963548320000115"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000115","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,22]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}