Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T14:22:50.891Z 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: [email protected])
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois, Chicago, IL 60607 (e-mail: [email protected])
BENNY SUDAKOV
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08544 (e-mail: [email protected])
JACQUES VERSTRAËTE
Affiliation:
Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, N2V2K7 (e-mail: [email protected])

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.)