Combinatorics, Probability and Computing



Paper

Rainbow Turán Problems


PETER KEEVASH a1, DHRUV MUBAYI a2 1 , BENNY SUDAKOV a3 2 and JACQUES VERSTRAËTE a4
a1 Department of Mathematics, Caltech, Pasadena, CA 91125, USA (e-mail: keevash@caltech.edu)
a2 Department of Mathematics, Statistics and Computer Science, University of Illinois, Chicago, IL 60607 (e-mail: mubayi@math.uic.edu)
a3 Department of Mathematics, Princeton University, Princeton, NJ 08544 (e-mail: bsudakov@math.princeton.edu)
a4 Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, N2V2K7 (e-mail: jverstraete@math.uwaterloo.ca)

Article author query
keevash p   [Google Scholar] 
mubayi d   [Google Scholar] 
sudakov b   [Google Scholar] 
verstraete j   [Google Scholar] 
 

Abstract

For a fixed graph $H$, we define the rainbow Turán number $\ex^*(n,H)$ to be the maximum number of edges in a graph on $n$ vertices that has a proper edge-colouring with no rainbow $H$. Recall that the (ordinary) Turán number $\ex(n,H)$ is the maximum number of edges in a graph on $n$ vertices that does not contain a copy of $H$. For any non-bipartite $H$ we show that $\ex^*(n,H)=(1+o(1))\ex(n,H)$, and if $H$ is colour-critical we show that $\ex^{*}(n,H)=\ex(n,H)$. When $H$ is the complete bipartite graph $K_{s,t}$ with $s \leq t$ we show $\ex^*(n,K_{s,t}) = O(n^{2-1/s})$, which matches the known bounds for $\ex(n,K_{s,t})$ up to a constant. We also study the rainbow Turán problem for even cycles, and in particular prove the bound $\ex^*(n,C_6) = O(n^{4/3})$, which is of the correct order of magnitude.

(Received June 7 2004)
(Revised October 7 2005)



Footnotes

1 Research supported in part by NSF grant DMS-0400812, and by an Alfred P. Sloan fellowship.

2 Research supported in part by NSF grant DMS-0355497, a USA–Israeli BSF grant, and by an Alfred P. Sloan fellowship.