Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles

By Oliver Janzer. Israel Journal of Mathematics, 2020

49 citations recorded by the source corpus.

The rainbow Turán number ex* ( 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 ≥ 2, ex*( n, C _2 k ) = O ( n ^1+1/ k ). This is tight and establishes a conjecture of Keevash, Mubayi, Sudakov and Verstraëte. 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 cn (log n )^4 edges contains a rainbow cycle. It is known that there exist properly edge-coloured n -vertex graphs with Ω( n log n ) edges which do not contain any rainbow cycle. Secondly, we show that in any proper edge-colouring of K _ n with $$o\left({{n^{{r \over {r - 1}} \cdot {{k - 1} \over k}}}} \right)$$$$o\left({{n^{{r \over {r - 1}} \cdot {{k - 1} \over k}}}} \right)$$ o ( n r r − 1 ⋅ 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 cn ^2−1/ r (log n )^7/ r edges contains the r -blow-up of an even cycle. Finally, we prove that the r -blow-up of C _2_ k has Turán number $$O\left({{n^{2 - {1 \over r} + {1 \over {k + r - 1}} + o\left(1 \right)}}} \right)$$$$O\left({{n^{2 - {1 \over r} + {1 \over {k + r - 1}} + o\left(1 \right)}}} \right)$$ O ( n 2 − 1 r + 1 k + r − 1 + o ( 1 ) ) , which can be used to disprove an old conjecture of Erdős and Simonovits.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/125c0f54b2a4adeff8209e815bf85efea0a23aea