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}∪{w|w∈V∋△uvw 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>2402/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}∪{w∣w∈V∋△uvwhas 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∉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?