Rainbow Turán Problem for Even Cycles

Details Rainbow Turán Problem for Even Cycles Rainbow Turán Problem for Even Cycles

2012-02-15

arxiv.org/abs/1202.3221v1

Mathematics

Combinatorics

12 pages

Scientific paper

An edge-colored graph is rainbow if all its edges are colored with distinct colors. For a fixed graph $H$, the rainbow Tur\'an number $\mathrm{ex}^{\ast}(n,H)$ is defined as the maximum number of edges in a properly edge-colored graph on $n$ vertices with no rainbow copy of $H$. We study the rainbow Tur\'an number of even cycles, and prove that for every fixed $\varepsilon > 0$, there is a constant $C(\varepsilon)$ such that every properly edge-colored graph on $n$ vertices with at least $C(\varepsilon) n^{1 + \varepsilon}$ edges contains a rainbow cycle of even length at most $2 \lceil \frac{\ln 4 - \ln \varepsilon}{\ln (1 + \varepsilon)} \rceil$. This partially answers a question of Keevash, Mubayi, Sudakov, and Verstra\"ete, who asked how dense a graph can be without having a rainbow cycle of any length.

Affiliated with

Also associated with

No associations

Rating

Rainbow Turán Problem for Even Cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rainbow Turán Problem for Even Cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow Turán Problem for Even Cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556577