TY - JOUR
T1 - On Multicolor Turán Numbers
AU - Balogh, József
AU - Liebenau, Anita
AU - Mattos, Letícia
AU - Morrison, Natasha
N1 - The second author was partially supported by the Australian Research Council (DP). The first author was partially supported by NSF grants DMS-1764123 and RTG DMS-1937241. The third author was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689) and AMS-Simons Travel fund. The fourth author was supported by NSERC Discovery Grant RGPIN-2021-02511. L. Mattos would like to thank Imolay for presenting the problem to her in the Berlin Combinatorics Research Seminar in Summer 2022. The authors thank the Oberwolfach Workshop on Combinatorics, Probability and Computing 2022 for hosting them. We note that we obtained the bound exC5(C3,n) = n2/25 + \u03B8(n) independently (cf. Theorem 2.2) before learning about the analogous result of Kovacs and Nagy (Theorem 1.6 in [6]). We thank both referees for their careful reading and useful comments.
\\ast Received by the editors February 16, 2024; accepted for publication (in revised form) June 18, 2024; published electronically August 26, 2024. https://doi.org/10.1137/24M1639488 Funding: The second author was partially supported by the Australian Research Council (DP). The first author was partially supported by NSF grants DMS-1764123 and RTG DMS-1937241. The third author was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy --The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689) and AMS-Simons Travel fund. The fourth author was supported by NSERC Discovery Grant RGPIN-2021-02511. \\dagger Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA ([email protected]). \\ddagger School of Mathematics and Statistics, UNSW Sydney, NSW 2052, Australia (a.liebenau@ unsw.edu.au). \\S Institut fu\\\"r Informatik, Universit\\a\"t Heidelberg, Im Neuenheimer Feld 205, D-69120 Heidelberg, Germany ([email protected]). \\P Department of Mathematics and Statistics, University of Victoria, Victoria, B.C., Canada ([email protected]).
PY - 2024
Y1 - 2024
N2 - We address a problem which is a generalization of Turán-type problems recently introduced by Imolay, Karl, Nagy, and Váli. Let F be a fixed graph and let G be the union of k edge-disjoint copies of F, namely G = ∪ ki=1Fi, where each Fi is isomorphic to a fixed graph F and E(Fi) ∩ E(Fj) = ∅ for all i ≠ j. We call a subgraph H ⊆ G multicolored if H and Fi share at most one edge for all i. Define exF (H, n) to be the maximum value k such that there exists G = ∪ ki=1Fi on n vertices without a multicolored copy of H. We show that exC5 (C3, n) ≤ n2/25 + 3n/25 + o(n) and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.
AB - We address a problem which is a generalization of Turán-type problems recently introduced by Imolay, Karl, Nagy, and Váli. Let F be a fixed graph and let G be the union of k edge-disjoint copies of F, namely G = ∪ ki=1Fi, where each Fi is isomorphic to a fixed graph F and E(Fi) ∩ E(Fj) = ∅ for all i ≠ j. We call a subgraph H ⊆ G multicolored if H and Fi share at most one edge for all i. Define exF (H, n) to be the maximum value k such that there exists G = ∪ ki=1Fi on n vertices without a multicolored copy of H. We show that exC5 (C3, n) ≤ n2/25 + 3n/25 + o(n) and that all extremal graphs are close to a blow-up of the 5-cycle. This bound is tight up to the linear error term.
UR - http://www.scopus.com/inward/record.url?scp=85202433999&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85202433999&partnerID=8YFLogxK
U2 - 10.1137/24M1639488
DO - 10.1137/24M1639488
M3 - Article
AN - SCOPUS:85202433999
SN - 0895-4801
VL - 38
SP - 2297
EP - 2311
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 3
ER -