Hostname: page-component-7c8c6479df-995ml Total loading time: 0 Render date: 2024-03-29T08:14:28.742Z Has data issue: false hasContentIssue false

Rainbow Turán Problems

Published online by Cambridge University Press:  04 September 2006

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

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.

Type
Paper
Copyright
© 2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)