# Turán's theorem with colors (2006)

Originators: Ajit Diwan and Dhruv Mubayi    (presented by Jane Butterfield - REGS 2008)

Definitions: For a graph F, let ex(n;F) denote the maximum number of edges in an n-vertex graph that does not contain F (as a subgraph). A red/blue graph is a graph G with two edge subsets R (red) and B (blue) such that E(G)=R∪B; note that edges may have both colors. For a red/blue graph G, let mRB(G)=min{|R|,|B|}.

A 2-colored graph is a graph together with an assignment of red or blue to each edge. A red/blue graph G contains a 2-colored graph F if some subgraph of G isomorphic to F as a graph respects the 2-coloring of F. For this purpose, an edge in R∩B may be viewed as having either color.

Background: Turán [T] determined ex(n;Kr+1) and showed furthermore that the unique largest n-vertex graph avoiding Kr+1 is the complete r-partite graph whose part-sizes differ by at most 1 (this graph is the Turán graph Tn,r). Of course, ex(n;Kr+1) edges also force the appearance of every subgraph of Kr+1. The present problem studies analogous conditions on red/blue graphs that force 2-colored subgraphs to appear.

Definitions: When F is a 2-colored graph, one could define an analogue of the Turán problem by letting ex2(n;F) be the minimum m such that every red/blue graph G with n vertices and mRB(G)>m contains F. When H is an uncolored graph, let ex2(n;H) be the maximum of ex2(n;F) over 2-colored graphs F that are obtained by 2-coloring the edges of H. (This generalizes in a natural way to ext(n;H), for which Diwan [D] used the notation ex(n;H;t).

An uncolored graph H is visible if ex2(n;H)=ex(n;H) for all n. That is, every red/blue graph G with mRB(G)>ex(|V(G)|;H) contains every 2-edge-coloring of H as a 2-colored subgraph.

Question 1: Which graphs are visible? Also, given H, which 2-colored graph F with underlying uncolored graph H produces the maximum value of ex2(n;F)?

Comments: Diwan [D] proved that matchings are visible. Visible graphs are those where the 2-colored problem is no harder than the ordinary Turán problem. In contrast, the second question asks for how bad the 2-colored version can be (and when it is worst). Surprisingly, the conjecture is that for complete graphs it cannot be much worse than the original Turán problem, with some small exceptions. (Roughly speaking, Diwan [D] showed also that if H=(n/2)K2, then ext(n;H)=ex(n;H), making matchings in a sense "t-visible". Diwan also explored bounds involving vertex degrees rather than the number of edges.)

Conjecture 2 (Diwan-Mubayi [DM]): If n>k and F is a 2-colored complete graph with k+1 vertices, then ex2(n;F)≤½(1-1/k)n² unless k+1∈{4,6,8} and F is a "blue-balanced" 2-colored graph (defined below). Except in that case, the statement says that every red/blue graph G with mRB(G)>ex(n;Kk+1) contains F. (A 2-colored graph is blue-balanced if the subgraph consisting of the blue edges is a spanning subgraph whose components are complete bipartite graphs with equal part-sizes).

Comments: Conjecture 2 is essentially the statement that complete graphs are visible and strengthens Turán's Theorem for complete graphs of even order. Diwan and Mubayi also conjectured upper bounds on the value of ex2(n;F) in the exceptional cases of Conjecture 2. These upper bounds are (3n²-2n)/8 when k+1=4, (2√2-2+o(1))(n\choose2) when k+1=6, and (√3/2+o(1))(n\choose2) when k+1=8.

Diwan and Mubayi proved the upper bound in Conjecture 2 for 2-colored complete graphs of special forms. In particular, it holds when F contains a monochromatic copy of Kk and at least one edge of the other color, and it holds when k+1≤5. Also, there exist infinitely many red/blue graphs other than colorings of the Turán graph that prove the sharpness of the proposed bound by not avoiding particular 2-colorings of E(Kk+1).

It is also natural to allow more colors. For example, a red/blue/green graph is a graph G with E(G)=R∪B∪G, and we let mRBG(G)=min{|R|,|B|,|G|}.

Question 3: How large must m be so that every n-vertex red/blue/green graph G with mRBG(G)≥m contains a triangle with distinct colors on its edges?

References:
[D] A. Diwan, Colored matchings in edge-colored graphs, Technical Report, Department of Computer Science and Engineering, I.I.T. Bombay, 2005. Available on Diwan's website.
[AD] A. Diwan, D. Mubayi, Turán's theorem with colors, submitted. Available on Mubayi's website.