{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:05:50Z","timestamp":1761609950887},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2020,10,12]],"date-time":"2020-10-12T00:00:00Z","timestamp":1602460800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For a real constant <jats:italic>\u03b1<\/jats:italic>, let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000358_inline1.png\" \/><jats:tex-math>$\\pi _3^\\alpha (G)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be the minimum of twice the number of <jats:italic>K<\/jats:italic><jats:sub>2<\/jats:sub>\u2019s plus <jats:italic>\u03b1<\/jats:italic> times the number of <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>\u2019s over all edge decompositions of <jats:italic>G<\/jats:italic> into copies of <jats:italic>K<\/jats:italic><jats:sub>2<\/jats:sub> and <jats:italic>K<\/jats:italic><jats:sub>3<\/jats:sub>, where <jats:italic>K<jats:sub>r<\/jats:sub><\/jats:italic> denotes the complete graph on <jats:italic>r<\/jats:italic> vertices. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000358_inline2.png\" \/><jats:tex-math>$\\pi _3^\\alpha (n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be the maximum of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000358_inline3.png\" \/><jats:tex-math>$\\pi _3^\\alpha (G)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> over all graphs <jats:italic>G<\/jats:italic> with <jats:italic>n<\/jats:italic> vertices.<\/jats:p><jats:p>The extremal function <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000358_inline4.png\" \/><jats:tex-math>$\\pi _3^3(n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> was first studied by Gy\u0151ri and Tuza (<jats:italic>Studia Sci. Math. Hungar.<\/jats:italic><jats:bold>22<\/jats:bold> (1987) 315\u2013320). In recent progress on this problem, Kr\u00e1l\u2019, Lidick\u00fd, Martins and Pehova (<jats:italic>Combin. Probab. Comput.<\/jats:italic><jats:bold>28<\/jats:bold> (2019) 465\u2013472) proved via flag algebras that<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000358_inline5.png\" \/><jats:tex-math>$\\pi _3^3(n) \\le (1\/2 + o(1)){n^2}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We extend their result by determining the exact value of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000358_inline6.png\" \/><jats:tex-math>$\\pi _3^\\alpha (n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and the set of extremal graphs for all <jats:italic>\u03b1<\/jats:italic> and sufficiently large <jats:italic>n<\/jats:italic>. In particular, we show for <jats:italic>\u03b1<\/jats:italic> = 3 that <jats:italic>K<jats:sub>n<\/jats:sub><\/jats:italic> and the complete bipartite graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548320000358_inline7.png\" \/><jats:tex-math>${K_{\\lfloor n\/2 \\rfloor,\\lceil n\/2 \\rceil }}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> are the only possible extremal examples for large <jats:italic>n<\/jats:italic>.<\/jats:p>","DOI":"10.1017\/s0963548320000358","type":"journal-article","created":{"date-parts":[[2020,10,12]],"date-time":"2020-10-12T10:53:15Z","timestamp":1602499995000},"page":"271-287","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Sharp bounds for decomposing graphs into edges and triangles"],"prefix":"10.1017","volume":"30","author":[{"given":"Adam","family":"Blumenthal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernard","family":"Lidick\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanitsa","family":"Pehova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Pfender","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oleg","family":"Pikhurko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Volec","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,10,12]]},"reference":[{"key":"S0963548320000358_ref26","unstructured":"[26] Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pp. 279\u2013319. Academic Press."},{"key":"S0963548320000358_ref5","unstructured":"[5] Delcourt, M. and Postle, L. (2019) Progress towards Nash-Williams\u2019 conjecture on triangle decompositions. arXiv:1909.00514"},{"key":"S0963548320000358_ref27","unstructured":"[27] Tuza, Z. (2001) Unsolved combinatorial problems, Part I. BRICS Lecture Series LS-01-1."},{"key":"S0963548320000358_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3500-0"},{"key":"S0963548320000358_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205075"},{"key":"S0963548320000358_ref22","unstructured":"[22] Pikhurko, O. and Razborov, A. (2017) Asymptotic structure of graphs with the minimum number of triangles. Combin. Probab. Comput. 26 138\u2013160."},{"key":"S0963548320000358_ref19","unstructured":"[19] Kr\u00e1l\u2019, D. , Lidick\u00fd, B. , Martins, T. L. and Pehova, Y. (2019) Decomposing graphs into edges and triangles. Combin. Probab. Comput. 28 465\u2013472."},{"key":"S0963548320000358_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548320000358_ref16","unstructured":"[16] Gy\u0151ri, E. and Tuza, Z. (1987) Decompositions of graphs into complete subgraphs of given order. Studia Sci. Math. Hungar. 22 315\u2013320."},{"key":"S0963548320000358_ref9","unstructured":"[9] Erd\u0151s, P. (1971) Some unsolved problems in graph theory and combinatorial analysis. In Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pp. 97\u2013109. Academic Press."},{"key":"S0963548320000358_ref18","unstructured":"[18] Kahn, J. (1981) Proof of a conjecture of Katona and Tarj\u00e1n. Period. Math. Hungar. 12 81\u201382."},{"key":"S0963548320000358_ref13","unstructured":"[13] Gy\u0151ri, E. (1992) Edge disjoint cliques in graphs. In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 357\u2013363. North-Holland."},{"key":"S0963548320000358_ref11","unstructured":"[11] Gy\u0151ri, E. (1988) On the number of edge-disjoint triangles in graphs of given size. In Combinatorics (Eger, 1987), Vol. 52 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 267\u2013276. North-Holland."},{"key":"S0963548320000358_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170003"},{"key":"S0963548320000358_ref2","unstructured":"[2] Barber, B. , K\u00fchn, D. , Lo, A. and Osthus, D. (2016) Edge-decompositions of graphs with high minimum degree. Adv. Math. 288 337\u2013385."},{"key":"S0963548320000358_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/fmp.2020.7"},{"key":"S0963548320000358_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/0602001"},{"key":"S0963548320000358_ref6","unstructured":"[6] Dross, F. (2016) Fractional triangle decompositions in graphs with large minimum degree. SIAM J. Discrete Math. 30 36\u201342."},{"key":"S0963548320000358_ref21","unstructured":"[21] Nash-Williams, C. (1970) An unsolved problem concerning decomposition of graphs into triangles. In Combinatorial Theory and Its Applications III, pp. 1179\u20131183. North-Holland."},{"key":"S0963548320000358_ref28","unstructured":"[28] Yuster, R. (2005) Integer and fractional packing of families of graphs. Random Struct. Algorithms 26 110\u2013118."},{"key":"S0963548320000358_ref10","unstructured":"[10] Erd\u0151s, P. , Goodman, A. W. and P\u00f3sa, L. (1966) The representation of a graph by set intersections. Canad. J. Math. 18 106\u2013112."},{"key":"S0963548320000358_ref7","unstructured":"[7] Dukes, P. and Horsley, D. (2020) On the minimum degree required for a triangle decomposition. SIAM J. Discrete Math. 34 597\u2013610."},{"key":"S0963548320000358_ref8","unstructured":"[8] Erd\u0151s, P. (1967) Some recent results on extremal problems in graph theory: results. In Theory of Graphs (Internat. Sympos., Rome, 1966), pp. 117\u2013123 (English), pp. 124\u2013130 (French). Gordon & Breach."},{"key":"S0963548320000358_ref25","unstructured":"[25] Razborov, A. (2008) On the minimal density of triangles in graphs. Combin. Probab. Comput. 17 603\u2013618."},{"key":"S0963548320000358_ref15","unstructured":"[15] Gy\u0151ri, E. and Kostochka, A. V. (1979) On a problem of G. O. H. Katona and T. Tarj\u00e1n. Acta Math. Acad. Sci. Hungar. 34 321\u2013327."},{"key":"S0963548320000358_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"S0963548320000358_ref24","unstructured":"[24] Razborov, A. (2007) Flag algebras. J. Symb. Logic 72 1239\u20131282."},{"key":"S0963548320000358_ref23","unstructured":"[23] Pyber, L. (1992) Covering the edges of a graph by \u2026. In Sets, Graphs and Numbers (Budapest, 1991), Vol. 60 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 583\u2013610. North-Holland."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000358","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T12:51:29Z","timestamp":1614862289000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000358\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,12]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["S0963548320000358"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000358","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,12]]},"assertion":[{"value":"\u00a9 The Author(s) (2020)","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}