$k$ is a positive integer, $R_{n}={-k, -(k-1),..., -1, 1,..., k-1, k}$ for $n=2k$ $R_{n}={-k, -(k-1),..., -1, 0, 1,..., k-1, k}$ for $n=2k+1$. A mechanism consists of some marbles and white/red ropes that connects some marble pairs. If each one of the marbles are written on some numbers from $R_{n}$ with the property that any two connected marbles have different numbers on them, we call it nice labeling. If each one of the marbles are written on some numbers from $R_{n}$ with the properties that any two connected marbles with a white rope have different numbers on them and any two connected marbles with a red rope have two numbers with sum not equal to $0$, we call it precise labeling. $n\geq{3}$, if every mechanism that is labeled nicely with $R_{n}$, could be labeled precisely with $R_{m}$, what is the minimal value of $m$?
Problem
Source: Turkey TST 2019 Day 2 P6
Tags: combinatorics, graph theory
27.03.2019 05:58
First I'll rephrase this in terms of graph theory since marbles are kind of confusing. The existence of a nice labeling with $R_n$ is simply equivalent to $\chi(G) \le n,$ with $\chi(G)$ denoting chromatic number. The existence of a precise labeling on $R_n$ is now equivalent to the assertion that we can first color $G$'s edges red and white, and then label the vertices with the integers in $R_n$ so that any white edge doesn't contain two equal numbers, and any two vertices connected by a red edge don't have their labels summing to zero. We are given a graph which has chromatic number $n$, for some $n \ge 3,$ and we're asked to determine the minimal $m$ so that there's a precise labelling on $R_m$ for this graph, no matter what the initial graph. We claim that the answer is $2n-1.$ Firstly, it's clear that this works by simply labelling the vertices with $0, 1, 2, \cdots, n-1$ so that no edge has two similarly-labelled vertices (guaranteed by the fact that $\chi(G) \le n$). This works since $\{0, 1, 2, \cdots, n-1\} \subseteq R_{2n-1}.$ Now, we will exhibit a construction to show that for any $m < 2n-1$, there cannot be a precise coloring on $R_m.$ To show this, it suffices to exhibit a graph where, when the vertices are labelled "precisely" on $\mathbb{Z},$ there must exist at least $n$ different absolute values among the labels of the vertices. This would imply the result, since $R_m$ for $m < 2n-1$ spans at most $n-1$ different absolute values. To do this, let's first fix an arbitrarily large positive integer $C$ (to be specified later), and construct $n$ groups of $C$ vertices each. Let's label the groups $g_1, g_2, \cdots, g_n,$ and denote the vertices in group $g_i$ by $v_{i, 1}, v_{i, 2}, v_{i, 3}, \cdots, v_{i, C}.$ Now, we will connect any two vertices $v_{i, k}, v_{j, k}$ by a white edge for $i \neq j, 1 \le k \le C.$ Otherwise, let's connect any pair of unconnected vertices in different groups by a red edge. Define the $\mathbf{type}$ of a vertices $g_{i, j}$ to be $j.$ We claim that for any absolute value $r \ge 0,$ there are at most $C+2$ vertices which are labeled with $\pm r.$ Call such vertices labeled with $\pm r$ $\mathbf{good}.$ Note that it is immediate that there cannot exist a cycle consisting of good vertices such that an odd number of the edges along the cycle are white. If there are at least $C+3$ good vertices, then since there are only $C$ different types of vertices, there must be two good vertices of the same type, WLOG assume that they are $g_{1,1}$ and $g_{2, 1}.$ Now, observe that any other good vertices $g_{i, j}$ for $i \neq 1, 2$ cannot possibly be $\pm r,$ by looking at the triangle formed by $g_{1,1}, g_{2, 1}, g_{i, j}$ and noting that it has an odd number of white edges in this triangle ($1$ or $3$). Hence, all good vertices are among $g_{1,1}, g_{1, 2}, \cdots, g_{1, C}, g_{2, 1}, g_{2, 2}, \cdots, g_{2, C}.$ Now, notice that since there are at least $C+3$ good vertices, there are at least $2$ numbers, say $a, b \neq 1$ for which $g_{1, a}, g_{1,b}$ are good, and also $2$ numbers, say $c, d \neq 1$ for which $g_{2, c}, g_{2, d}$ are good. Therefore, we can clearly assume that $a \neq c,$ and so hence $g_{1, 1} g_{2, c} g_{1, a} g_{2, 1}$ is a cycle with an odd number of white edges, contradiction. As a result of this, we can conclude that there are at least $\frac{nC}{C+2}$ different absolute values among the labels of the $nC$ vertices, and so hence selecting a $C > 2n-2$ would give a construction for which there are at least $n$ absolute values. $\square$