Rainbow Tur\'an number of even cycles, repeated patterns and blow-ups of cycles

DOI10.1007/S11856-022-2380-9MaRDI QIDQ6341840arXivFDO

Publication date 1 June 2020

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Paths and cycles (05C38) Ramsey theory (05D10)

Abstract: The rainbow Tur'an number

m a t h r m {e x}^{*} (n, H)

of a graph

H

is the maximum possible number of edges in a properly edge-coloured

n

-vertex graph with no rainbow subgraph isomorphic to

H

. We prove that for any integer

k g e q 2

,

m a t h r m {e x}^{*} (n, C_{2 k}) = O (n^{1 + 1 / k})

. This is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstra"ete. We use the same method to prove several other conjectures in various topics. First, we prove that there exists a constant

c

such that any properly edge-coloured

n

-vertex graph with more than

c n (l o g n)^{4}

edges contains a rainbow cycle. It is known that there exist properly edge-coloured

n

-vertex graphs with

O m e g a (n l o g n)

edges which do not contain any rainbow cycle. Secondly, we show that in any proper edge-colouring of

K_{n}

with

o (n^{f r a c r r - 1 c d o t f r a c k - 1 k})

colours, there exist

r

colour-isomorphic, pairwise vertex-disjoint copies of

C_{2 k}

. This proves in a strong form a conjecture of Conlon and Tyomkyn, and a strenghtened version proposed by Xu, Zhang, Jing and Ge. Moreover, we answer a question of Jiang and Newman by showing that there exists a constant

c = c (r)

such that any

n

-vertex graph with more than

c n^{2 - 1 / r} (l o g n)^{7 / r}

edges contains the

r

-blowup of an even cycle. Finally, we prove that the

r

-blowup of

C_{2 k}

has Tur'an number

O (n^{2 - f r a c 1 r + f r a c 1 k + r - 1 + o (1)})

, which can be used to disprove an old conjecture of ErdH os and Simonovits.

This page was built for publication: Rainbow Tur\'an number of even cycles, repeated patterns and blow-ups of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341840)