The possible partition into some parts

Solution IMO 2015 (combinatoric shortlist )

Problem 7:

In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least 3, and it is possible to arrange all its members around a round table so that every two neighbours are enemies. Given that there are at most 2015 unsociable groups, prove that it is possible to partition the company into 11 parts so that no two enemies are in the same part.

Also Read:

Solution 1.

Let G = (V, E) be a graph where V is the set of people in the company and E is the set of the enemy pairs — the edges of the graph. In this language, partitioning into 11 disjoint enemy-free subsets means properly coloring the vertices of this graph with 11 colors.

We will prove the following more general statement.

Claim. Let G be a graph with chromatic number k\geqslant 3. Then G contains at least 2k-1 – k unsociable groups.

Recall that the chromatic number of G is the least k such that a proper coloring

exists. In view of 211 – 12 > 2015, the claim implies the problem statement.

Let G be a graph with chromatic number k. We say that a proper coloring (1) of G is leximinimal, if the k-tuple (|V1|. |V2|…..|Vk|) is lexicographically minimal; in other words, the following conditions are satisfied: the number n1 = |v1| | is minimal; the number n2 = |v2| is minimal, subject to the previously chosen value of n1;……: the number nk-1 = |vk-1| is minimal, subject to the previously chosen values of n1,…,nk-2.

The following lemma is the core of the proof.

Lemma 1.

Suppose that G = (V, E) is a graph with odd chromatic number k e 3, and let (1)

be one of its leximinimal colorings. Then G contains an odd cycle which visits all color classes v1, v2, …,vk.

Proof of Lemma 1. Let us call a cycle colorful if it visits all color classes. Due to the definition of the chromatic number, V1 is nonempty. Choose an arbitrary vertex v\in V. We construct a colorful odd cycle that has only one vertex in V1, and this vertex is v.

We draw a subgraph of G as follows. Place v in the center, and arrange the sets V2, V3, …, Vk in counterclockwise circular order around it. For convenience, let Vk+1 = V2. We will draw arrows to add direction to some edges of G, and mark the vertices these arrows point to. First we draw arrows from v to all its neighbors in Vi+1, and mark all those neighbors. If some vertex u\in V_i with i\in {2, 3, . . ., k} is already marked, we draw arrows from u to all its neighbours in Vi+1 which are not marked yet, and we mark all of them. We proceed doing this as long as it is possible. The process of marking is exemplified in Figure 1.

Notice that by the rules of our process, in the final state, marked vertices in Vi cannot have unmarked neighbors in Vi+1. Moreover, v is connected to all marked vertices by directed paths.

Now move each marked vertex to the next color class in circular order (see an example in Figure 3). In view of the arguments above, the obtained coloring V_1\sqcup W_2\sqcup...\sqcup W_k is proper. Notice that v has a neighbor w\in W_2, because otherwise

would be a proper coloring lexicographically smaller than (1). If w was unmarked, i.e., w was an element of V2, then it would be marked at the beginning of the process and thus moved to V3, which did not happen. Therefore, w is marked and w\in V_k.

Since w is marked, there exists a directed path from v to w. This path moves through the sets V2,…,Vk in circular order, so the number of edges in it is divisible by k – 1 and thus even. Closing this path by the edge w\rightarrow v, we get a colorfull odd cycle, as required.

Proof of the claim. Let us choose a leximinimal coloring (1) of G. For every set C\subseteq {1,2,..,k} such that |C| is odd and greater than 1, we will provide an odd cycle visiting exactly those color classes whose indices are listed in the set C. This property ensures that we have different cycles for different choices of C, and it proves the claim because there are 2k-1 – k choices for the set C.

Let V_c=\bigcup _{c\in C}V_c, and let GC be the induced subgraph of G on the vertex set Vc. We also have the induced coloring of Vc with |C| colors; this coloring is of course proper. Notice further that the induced coloring is leximinimal: if we had a lexicographically smaller coloring \left ( W_c \right )_{c\in C} of Gc, then these classes, together the original color classes Vi for i\notin C, would provide a proper coloring which is lexicographically smaller than (1). Hence Lemma 1, applied to the subgraph Gc and its leximinimal coloring \left ( V_c \right )_{c\in C}, provides an odd cycle that visits exactly those color classes that are listed in the set C.

Also Read : Combinatoric Shortlist Problem in IMO 2015

×

Like us on Facebook

%d bloggers like this: