Rainbow Turán number of clique subdivisions

Tao Jiang; Abhishek Methuku; Liana Yepremyan

doi:10.1016/j.ejc.2022.103675

Rainbow Turán number of clique subdivisions

Tao Jiang, Abhishek Methuku, Liana Yepremyan

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

Abstract

We show that for any integer t≥2, every properly edge-coloured graph on n vertices with more than n^1+o(1) edges contains a rainbow subdivision of K_t. Note that this bound on the number of edges is sharp up to the o(1) error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Turán numbers. Our method relies on the framework introduced by Sudakov and Tomon (2022) which we adapt to find robust expanders in the coloured setting.

Original language	English (US)
Article number	103675
Journal	European Journal of Combinatorics
Volume	110
DOIs	https://doi.org/10.1016/j.ejc.2022.103675
State	Published - May 2023
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Online availability

10.1016/j.ejc.2022.103675

Library availability

Discover UIUC Full Text

Cite this

@article{4ee0707bb72b491cba268ec8d2631cd8,

title = "Rainbow Tur{\'a}n number of clique subdivisions",

abstract = "We show that for any integer t≥2, every properly edge-coloured graph on n vertices with more than n1+o(1) edges contains a rainbow subdivision of Kt. Note that this bound on the number of edges is sharp up to the o(1) error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Tur{\'a}n numbers. Our method relies on the framework introduced by Sudakov and Tomon (2022) which we adapt to find robust expanders in the coloured setting.",

author = "Tao Jiang and Abhishek Methuku and Liana Yepremyan",

note = "Research supported by National Science Foundation grant DMS-1855542.Research supported by the EPSRC, grant no. EP/S00100X/1.Research supported by Marie Sklodowska Curie Global Fellowship, H2020-MSCA-IF-2018:846304.",

year = "2023",

month = may,

doi = "10.1016/j.ejc.2022.103675",

language = "English (US)",

volume = "110",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Rainbow Turán number of clique subdivisions

AU - Jiang, Tao

AU - Methuku, Abhishek

AU - Yepremyan, Liana

N1 - Research supported by National Science Foundation grant DMS-1855542.Research supported by the EPSRC, grant no. EP/S00100X/1.Research supported by Marie Sklodowska Curie Global Fellowship, H2020-MSCA-IF-2018:846304.

PY - 2023/5

Y1 - 2023/5

N2 - We show that for any integer t≥2, every properly edge-coloured graph on n vertices with more than n1+o(1) edges contains a rainbow subdivision of Kt. Note that this bound on the number of edges is sharp up to the o(1) error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Turán numbers. Our method relies on the framework introduced by Sudakov and Tomon (2022) which we adapt to find robust expanders in the coloured setting.

AB - We show that for any integer t≥2, every properly edge-coloured graph on n vertices with more than n1+o(1) edges contains a rainbow subdivision of Kt. Note that this bound on the number of edges is sharp up to the o(1) error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Turán numbers. Our method relies on the framework introduced by Sudakov and Tomon (2022) which we adapt to find robust expanders in the coloured setting.

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

UR - https://www.scopus.com/inward/citedby.url?scp=85145842194&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2022.103675

DO - 10.1016/j.ejc.2022.103675

M3 - Article

AN - SCOPUS:85145842194

SN - 0195-6698

VL - 110

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103675

ER -

Rainbow Turán number of clique subdivisions

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this