Generalized rainbow Turán problems

Dániel Gerbner; Tamás Mészáros; Abhishek Methuku; Cory Palmer

doi:10.37236/9964

Generalized rainbow Turán problems

Dániel Gerbner
, Tamás Mészáros
, Abhishek Methuku
, Cory Palmer

Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)] initiated the systematic study of the following generalized Turán problem: for fixed graphs H and F and an integer n, what is the maximum number of copies of H in an n-vertex F-free graph? An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Turán number of F is defined as the maximum number of edges in a properly edge-colored graph on n vertices with no rainbow copy of F . The study of rainbow Turán problems was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Comb. Probab. Comput. 16 (2007)]. Motivated by the above problems, we study the following problem: What is the maximum number of copies of F in a properly edge-colored graph on n vertices without a rainbow copy of F? We establish several results, including when F is a path, cycle or tree.

Original language	English
Article number	#P2.44
Journal	Electronic Journal of Combinatorics
Volume	29
Issue number	2
DOIs	https://doi.org/10.37236/9964
State	Published - 2022

Funding

∗Supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office – NKFIH under the grants K 116769, KH130371 and SNN 129364. †Supported by the Dahlem Research School. ‡Supported by EPSRC grant EP/S00100X/1 (A. Methuku) and by IBS-R029-C1. §Supported by a grant from the Simons Foundation #712036. Supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office – NKFIH under the grants K 116769, KH130371 and SNN 129364. Supported by the Dahlem Research School. Supported by EPSRC grant EP/S00100X/1 (A. Methuku) and by IBS-R029-C1. Supported by a grant from the Simons Foundation #712036.

Funders	Funder number
Simons Foundation	712036
Engineering and Physical Sciences Research Council	EP/S00100X/1, IBS-R029-C1
K 116769, SNN 129364, KH130371

Access to Document

10.37236/9964

Cite this

@article{9f943a2b8e424b2d94cd8f0c25901926,

title = "Generalized rainbow Tur{\'a}n problems",

abstract = "Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)] initiated the systematic study of the following generalized Tur{\'a}n problem: for fixed graphs H and F and an integer n, what is the maximum number of copies of H in an n-vertex F-free graph? An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Tur{\'a}n number of F is defined as the maximum number of edges in a properly edge-colored graph on n vertices with no rainbow copy of F . The study of rainbow Tur{\'a}n problems was initiated by Keevash, Mubayi, Sudakov and Verstra{\"e}te [Comb. Probab. Comput. 16 (2007)]. Motivated by the above problems, we study the following problem: What is the maximum number of copies of F in a properly edge-colored graph on n vertices without a rainbow copy of F? We establish several results, including when F is a path, cycle or tree.",

author = "D{\'a}niel Gerbner and Tam{\'a}s M{\'e}sz{\'a}ros and Abhishek Methuku and Cory Palmer",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2022",

doi = "10.37236/9964",

language = "English",

volume = "29",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

number = "2",

}

TY - JOUR

T1 - Generalized rainbow Turán problems

AU - Gerbner, Dániel

AU - Mészáros, Tamás

AU - Methuku, Abhishek

AU - Palmer, Cory

PY - 2022

Y1 - 2022

N2 - Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)] initiated the systematic study of the following generalized Turán problem: for fixed graphs H and F and an integer n, what is the maximum number of copies of H in an n-vertex F-free graph? An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Turán number of F is defined as the maximum number of edges in a properly edge-colored graph on n vertices with no rainbow copy of F . The study of rainbow Turán problems was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Comb. Probab. Comput. 16 (2007)]. Motivated by the above problems, we study the following problem: What is the maximum number of copies of F in a properly edge-colored graph on n vertices without a rainbow copy of F? We establish several results, including when F is a path, cycle or tree.

AB - Alon and Shikhelman [J. Comb. Theory, B. 121 (2016)] initiated the systematic study of the following generalized Turán problem: for fixed graphs H and F and an integer n, what is the maximum number of copies of H in an n-vertex F-free graph? An edge-colored graph is called rainbow if all its edges have different colors. The rainbow Turán number of F is defined as the maximum number of edges in a properly edge-colored graph on n vertices with no rainbow copy of F . The study of rainbow Turán problems was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Comb. Probab. Comput. 16 (2007)]. Motivated by the above problems, we study the following problem: What is the maximum number of copies of F in a properly edge-colored graph on n vertices without a rainbow copy of F? We establish several results, including when F is a path, cycle or tree.

UR - https://www.scopus.com/pages/publications/85133723437

U2 - 10.37236/9964

DO - 10.37236/9964

M3 - Article

AN - SCOPUS:85133723437

SN - 1077-8926

VL - 29

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - #P2.44

ER -

Generalized rainbow Turán problems

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this