Consider $9$ points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $\,n\,$ such that whenever exactly $\,n\,$ edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.
Problem
Source: IMO 1992, Day 1, Problem 3
Tags: combinatorics, Ramsey Theory, graph theory, IMO, IMO 1992, Coloring, Extremal combinatorics
15.02.2008 06:20
Answer is $ 33$. Suppose we can color $ 33$ edges and have no monochromatic triangle. Then look at any vertex, $ X$. If $ X$ has $ 5$ blue edges coming from it, then, calling them $ A_{1} ... A_{5}$ - if any edge $ A_{i}A_{j}$ is colored, then it must be colored red, since otherwise $ XA_{i}A_{j}$ is a blue triangle. But within $ 5$ points, if more than $ \frac {5^2}{4}$ are colored red, then we will have a red triangle (since if we have more than $ \frac {n^2}{4}$ edges in a graph with $ n$ edges, there must be a triangle). That means at most $ 6$ of the $ 10$ vertices $ A_{i}A_{j}$ are colored, so there are at least $ 4$ uncolored edges - contradiction, since we have $ 33$ edges. Thus $ X$ has at most $ 4$ blue edges and at most $ 4$ red edges. Suppose it has $ 8$ edges emanating from it - then it has exactly $ 4$ blue edges, connecting to points $ B_{1} ... B_{4}$, and exactly $ 4$ red edges, connecting to points $ R_{1} ... R_{4}$. To prevent triangles, all edges $ B_{i}B_{j}$, if colored, must be red. In $ 4$ points, if more than $ \frac {4^2}{4} = 4$ of them are colored, there will be a red triangle (since if we have more than $ \frac {n^2}{4}$ edges in a graph with $ n$ edges, there must be a triangle). Thus there are least $ 2$ uncolored edges amongst $ B_{i}$, and similarly, there are at least $ 2$ uncolored edges amongst $ R_{i}$, so there are at least $ 4$ uncolored edges, a contradiction again. Thus no vertex can have degree $ 8$, so each vertex has degree at most $ 7$. But then, there are at most $ \frac {9 * 7}{2}$ edges, so there are at most $ 31$ edges, which is a final contradiction. To prove it is possible to have $ 32$ edges without a triangle: Consider one vertex $ V$, suppose it has $ 4$ blue edges to $ B_{1}, B_{2}, B_{3}, B_{4}$ ; and $ 4$ red edges to $ R_{1}, R_{2}, R_{3}, R_{4}$. Color edges $ B_{i}B_{i+1}$ red, and $ R_{i}R_{i+1}$ blue, for $ i=1,2,3,4$ (and $ B_{5} = B_{1}, R_{5}=R_{1}$). Color $ B_{i}R_{j}$ blue iff $ i+j$ is odd. Now we have graph with $ 32$ edges, which we easily verify contains no monochromatic triangles.
26.11.2010 22:27
A simpler way to establish that 33 is the answer: Same example for 32. Suppose that we can color 33 edges with no monochromatic triangles. Now, we are done if we prove that there are 6 points such that all the possible segments connecting them are drawn (because R(3,3)=6). Consider the complementary of the original graph, that is, the graph with only 3 lines. It's obvious that each of these lines only does the job of disallowing 2 vertices connected to be in those 6 points mentioned above together. That means that 3 lines can ''put away'' at most 3 points, but 9-3=6. It's now trivial.
14.06.2014 15:24
14.06.2014 17:07
Precisely; that is what Bugi has done - prove TurĂ¡n for this particular case ...
11.08.2024 09:08
posting for storage
21.08.2024 20:30
My solution is basically similar to the proof in the post #2. I use more details, including pictures and I try to present the solution as elementary as possible. I made a single significant change: $\textbf{epitomy01}$ wrote relative to monochromatic edges: "since if we have more than $ \dfrac {n^2}{4}$ edges in a graph with $ n$ vertices, there must be a triangle". I use a weaker inequality, very easy to prove, enough to solve our problem. The complete solution is in attachment.
Attachments:
Red and blue edges.pdf (211kb)