A Caltech Library Service

Rainbow Turán Problems

Keevash, Peter and Mubayi, Dhruv and Sudakov, Benny and Verstraëte, Jacques (2007) Rainbow Turán Problems. Combinatorics, Probability, and Computing, 16 (1). pp. 109-126. ISSN 0963-5483. doi:10.1017/S0963548306007760.

See Usage Policy.


Use this Persistent URL to link to this item:


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

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:Copyright © 2006 Cambridge University Press. Reprinted with permission. Received 7 June 2004; revised 7 October 2005. [Published online 4 September 2006] We thank an anonymous referee for suggestions that improved the presentation of this paper, and for drawing certain references to our attention, including the construction of Maamoun and Meyniel used in Section 2. [D.M.] Research supported in part by NSF grant DMS-0400812, and by an Alfred P. Sloan fellowship. [B.S.] Research supported in part by NSF grant DMS-0355497, a USA–Israeli BSF grant, and by an Alfred P. Sloan fellowship.
Issue or Number:1
Record Number:CaltechAUTHORS:KEEcpc07
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7555
Deposited By: Archive Administrator
Deposited On:03 Mar 2007
Last Modified:08 Nov 2021 20:43

Repository Staff Only: item control page