Rainbow Turan problems

被引:53
作者
Keevash, Peter [1 ]
Mubayi, Dhruv
Sudakov, Benny
Verstraete, Jacques
机构
[1] CALTECH, Dept Math, Pasadena, CA 91125 USA
[2] Univ Illinois, Dept Math Stat & Comp Sci, Chicago, IL 60607 USA
[3] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
[4] Univ Waterloo, Fac Math, Dept Combinator & Optimizat, Waterloo, ON N2V 2K7, Canada
关键词
D O I
10.1017/S0963548306007760
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
For a fixed graph H, we define the rainbow Turin 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) Turin 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)) = 0(n(2-1/s)), which matches the known bounds for ex(n,K(s,t)) up to a constant. We also study the rainbow Turin problem for even cycles, and in particular prove the bound ex* (n, C(6)) = 0(n(4/3)), which is of the correct order of magnitude.
引用
收藏
页码:109 / 126
页数:18
相关论文
共 33 条