Sharp bounds for decomposing graphs into edges and triangles
Date
2021-03
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Cambridge University Press
Abstract
For a real constant α, let πα(G) be the minimum of twice the number of K₂’s plus α times the number of K₃’s over all edge decompositions of G into copies of K₂ and K₃, where Kr denotes the complete graph on r vertices. Let πα(n) be the maximum of πα(G) over all graphs G with n vertices.
The extremal function π ³(n) was first studied by Győri and Tuza (Studia Sci. Math. Hungar. 22 (1987) 315–320). In recent progress on this problem, Král’, Lidický, Martins and Pehova (Combin. Probab. Comput. 28 (2019) 465–472) proved via flag algebras that π ³(n) (1/2+o(1))n2 . We extend their result by determining the exact value of πα(n) and the set of extremal graphs for all α and sufficiently large n. In particular, we show for α 3 that Kn and the complete bipartite graph Kln/₂J,₁n/₂l are the only possible extremal examples for large n.
The extremal function π ³(n) was first studied by Győri and Tuza (Studia Sci. Math. Hungar. 22 (1987) 315–320). In recent progress on this problem, Král’, Lidický, Martins and Pehova (Combin. Probab. Comput. 28 (2019) 465–472) proved via flag algebras that π ³(n) (1/2+o(1))n2 . We extend their result by determining the exact value of πα(n) and the set of extremal graphs for all α and sufficiently large n. In particular, we show for α 3 that Kn and the complete bipartite graph Kln/₂J,₁n/₂l are the only possible extremal examples for large n.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
Comments
This article is published as Blumenthal A, Lidický B, Pehova Y, Pfender F, Pikhurko O, Volec J. Sharp bounds for decomposing graphs into edges and triangles. Combinatorics, Probability and Computing. 2021;30(2):271-287. doi:10.1017/S0963548320000358.
Rights Statement
© The Author(s) (2020). 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.