Rainbow subdivisions of cliques

Tao Jiang; Shoham Letzter; Abhishek Methuku; Liana Yepremyan

doi:10.1002/rsa.21186

Rainbow subdivisions of cliques

Tao Jiang, Shoham Letzter, Abhishek Methuku, Liana Yepremyan

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

Abstract

We show that for every integer (Formula presented.) and large (Formula presented.), every properly edge-colored graph on (Formula presented.) vertices with at least (Formula presented.) edges contains a rainbow subdivision of (Formula presented.). This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.

Original language	English (US)
Pages (from-to)	625-644
Number of pages	20
Journal	Random Structures and Algorithms
Volume	64
Issue number	3
Early online date	Oct 25 2023
DOIs	https://doi.org/10.1002/rsa.21186
State	Published - May 2024
Externally published	Yes

Keywords

cycles
expanders
expansion
homomorphism
mixing time
rainbow Turan number
random walk
subdivision of cliques

ASJC Scopus subject areas

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Online availability

10.1002/rsa.21186

Library availability

Discover UIUC Full Text

Cite this

@article{a0a819a0b84f41cab3a5610aadc3c967,

title = "Rainbow subdivisions of cliques",

abstract = "We show that for every integer (Formula presented.) and large (Formula presented.), every properly edge-colored graph on (Formula presented.) vertices with at least (Formula presented.) edges contains a rainbow subdivision of (Formula presented.). This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.",

keywords = "cycles, expanders, expansion, homomorphism, mixing time, rainbow Turan number, random walk, subdivision of cliques",

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

note = "Research supported by National Science Foundation grant DMS‐1855542. Research supported by the Royal Society. Research supported by the EPSRC, grant no. EP/S00100X/1 (Abhishek Methuku). This research was carried out while being supported by Marie Sklodowska Curie Global Fellowship, H2020‐MSCA‐IF‐2018:846304 hosted by London School of Economics, UK. The researcher is currently supported by NSF grant 2247013.",

year = "2024",

month = may,

doi = "10.1002/rsa.21186",

language = "English (US)",

volume = "64",

pages = "625--644",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley \& Sons, Ltd.",

number = "3",

}

TY - JOUR

T1 - Rainbow subdivisions of cliques

AU - Jiang, Tao

AU - Letzter, Shoham

AU - Methuku, Abhishek

AU - Yepremyan, Liana

N1 - Research supported by National Science Foundation grant DMS‐1855542. Research supported by the Royal Society. Research supported by the EPSRC, grant no. EP/S00100X/1 (Abhishek Methuku). This research was carried out while being supported by Marie Sklodowska Curie Global Fellowship, H2020‐MSCA‐IF‐2018:846304 hosted by London School of Economics, UK. The researcher is currently supported by NSF grant 2247013.

PY - 2024/5

Y1 - 2024/5

N2 - We show that for every integer (Formula presented.) and large (Formula presented.), every properly edge-colored graph on (Formula presented.) vertices with at least (Formula presented.) edges contains a rainbow subdivision of (Formula presented.). This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.

AB - We show that for every integer (Formula presented.) and large (Formula presented.), every properly edge-colored graph on (Formula presented.) vertices with at least (Formula presented.) edges contains a rainbow subdivision of (Formula presented.). This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.

KW - cycles

KW - expanders

KW - expansion

KW - homomorphism

KW - mixing time

KW - rainbow Turan number

KW - random walk

KW - subdivision of cliques

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

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

U2 - 10.1002/rsa.21186

DO - 10.1002/rsa.21186

M3 - Article

AN - SCOPUS:85174617379

SN - 1042-9832

VL - 64

SP - 625

EP - 644

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3

ER -

Rainbow subdivisions of cliques

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this