Let $G$ be the complete graph on $2015$ vertices. Each edge of $G$ is dyed red, blue or white. For a subset $V$ of vertices of $G$, and a pair of vertices $(u,v)$, define \[ L(u,v) = \{ u,v \} \cup \{ w | w \in V \ni \triangle{uvw} \text{ has exactly 2 red sides} \}\]Prove that, for any choice of $V$, there exist at least $120$ distinct values of $L(u,v)$.
Problem
Source: China Team Selection Test 3 Day 2 P2
Tags: graph theory, combinatorics
26.03.2015 01:28
Why is the graph tricolored(the only thing important is edge red or not )???? Suppose opposite. However,here is an outline:First,if $V$ has less than $2000$ elements,than $G/V$ will have at least $16$ elements and for any pair such that both of his elements are in $G/V$ $L(u,v)$ where $u,v$ are in $G/V$ will have a difirent value(cause every $u,v$ can only contain vertices from $V$),so then we trivialy have $120$ distinct pairs,so assume $V$ has more or equal $2000$ elements.Now,consider a vertex $u$.If it has more than $119$ non-red edges,than we have at least $120$ values(cause every $L(u,v)$ where $uv$ is a non-red edge will contain all $w$ $uw$ is red),so suppose every vertex has less than $120$ edges.Now,consider $V$ independently.By our assumption,it has at least $d=2000*1999/2-60*2000$ red edges and from our assumption at least $d/119$ pairs have the same value.Now,if the value contains at least $241$ elements then we pick some red edge $uv$ for which we obtain this value and for every $w$ in this set exactly one of the edges $uw$ and $vw$ will be non red,so by pigenhole we have a vertex which has at least $120$ non red edges which is a contradiction.So assume this value has at most $240$ elements and $d/119$ edges for which we have this value.Now,we have that $d/119>240^2/4+1$,so by Turan's theorem we get that the value has a triangle,but this is an obvious contradiction.
26.03.2015 01:32
Just a typo,I assume that value has $d/119$ edges(I can't edit on phone).
26.03.2015 20:03
I'm a bit confused on this "$120$ distinct values" part. Are the "values" the sets $\{u, v\} \cup \{w \mid w \in V \ni \triangle uvw \; \text{has exactly 2 red sides}\}$? And if this is the case, are we then supposed to show that there are at least $120$ distinct sets that can be obtained by choosing the initial two vertices, or what does "distinct values" mean?
26.03.2015 20:41
dibyo_99 wrote: Prove that, for any choice of $V$, there exist at least $120$ distinct values of $L(u,v)$. It says for any choice of $V$,so it is more logic that you fix $V$ and go throug all pairs $u,v$. Also,if we fix $u,v$ then color one edge red and other edges arbritaly blue or white.It is obvious that we don't have a triangle $uvw$ which has $2$ red edges,so for fixed $u,v$ for any choice of $V$ $L(u,v)$ will be $(u,v)$.
26.03.2015 20:48
Sorry for the bad translation folks. Yes, I believe it does mean $120$ distinct sets. Also, I don't know why 3 colors are used. These are just crude Google translations of the questions.
27.03.2015 11:34
The original problem is 2 colors used.
03.04.2015 19:49
I'll assume we're looking for 120 distinct sets $ L(u, v). $ First note that every set $ L(u, v) $ where $ u, v \notin V $ is distinct from one another so if $ |V| < 2000 $ then the number of distinct sets $ L(u, v) $ is at least $ \binom{2015 - |V|}{2} \ge \binom{16}{2} = 120, $ so assume that $ |V| \ge 2000. $ Now consider a vertex $ v \in G $ and the vertices $ v_1, v_2, \dots v_m $ that are connected to it by a non-red edge. It is clear that $ L(v, v_i) $ are distinct for all $ i \in \{1, 2, \dots, m\} $ (since $ L(v, v_i) $ doesn't contain $ v_j $ for all suitable $ i \ne j $). Therefore we can assume that every vertex in $ G $ has less than $ 120 $ non-red edges. Considering the complete subgraph formed by the vertices in $ V, $ we must have that it contains at least $ \binom{2000 - 119}{2} $ red edges. Let $ E $ be the set of these red edges and define $ L(e) $ to be equivalent to $ L(u, v) $ for any edge $ e \in E $ that is incident to the vertices $ u $ and $ v. $ Now, assume for the sake of contradiction that there are less than $ 120 $ distinct values of $ L(u, v). $ Then by the pigeonhole principal there are edges $ e_1, e_2, \dots, e_r \in E $ such that $ L(e_1) = L(e_2) = \dots = L(e_r) $ where $ r \ge \frac{\binom{2000 - 119}{2}}{119} > 120^2 + 1. $ Therefore the number of red edges between vertices in $ L(e_1) $ is at least $ 120^2 + 1. $ Note that for every $ w \in L(e_1) - \{u_1, v_1\} $ (where $ u_1, v_1 \in V $ and $ e_1 = u_1v_1 $) we have that one of the edges $ u_1w $ and $ v_1w $ is non-red so by the pigeonhole principle, If $ |L(e_1)| > 240 $ then one of the vertices that $ v_1 $ or $ w_1 $ is incident to at least $ 120 $ non-red edges, which by an earlier result means we are done. Therefore assume that $ |L(e_1)| \le 240. $ Since the number of red edges between vertices in $ L(e_1) $ is greater than $ 120^2 + 1 $ we have by Turan's Theorem that there it contains a red triangle, contradiction. Therefore we are done.
07.04.2015 16:37
Why are we all using Turan's theorem here? Here's a very very silly solution using nothing remotely high tech. First, if $|V| < 2000,$ then this is done similar as above: $\binom{2015-|V|}{2} \ge \binom{16}{2} = 120.$ (The $\binom{16}{2}$ comes from choosing any pair of vertices not in $|V|$.) So assume that $|V| \ge 2000$. Let $v_1, v_2, \dots, v_{2000}$ be vertices in $V$. Consider the sets $L(v_1, v_2), L(v_1, v_3), L(v_1, v_4), \dots, L(v_1, v_{2000})$, so $1999$ sets. Assume that they determine less than $120$ distinct ones. Therefore, at least $\lceil 1999/119 \rceil = 17$ of the sets are the same. WLOG that $L(v_1, v_2), L(v_1, v_3), \dots, L(v_1, v_{18})$ are all the same. In particular, any triangle of the form $v_1v_iv_j$ for $2 \le i, j \le 18$ must have exactly 2 red sides. In particular, at most one of the edges $v_1v_i$ for $2 \le i \le 18$ is white. (If you have $2$ white edges, then the triangle with those two edges has at most 1 red edge) So you have $16$ red edges. Since every triangle has 2 red sides, the points with the red edges to them form a $K_{16}$ of white edges. But of course any pair of vertices in this $K_{16}$ determines a unique set $L(u, v)$, and $\binom{16}{2} = 120$ again, so we're done. Note: In fact I don't believe that I even need $|V| \ge 2000$ for this to work, as in my proof never really has to use that $v_1, v_2, \dots, v_{2000}$ are indeed in $V$. But since I did find that, I'll just leave it here.
05.08.2022 11:20
During the test, the genius Jiyang Gao (高继扬, IMO 2014&2015 Gold Medalist) pointed out that 120 can be improved to 1007.
06.10.2022 18:38
JG666 wrote: During the test, the genius Jiyang Gao (高继扬, IMO 2014&2015 Gold Medalist) pointed out that 120 can be improved to 1007. How did he do that?