uniolympiads Ελληνικά

IMC 2022, Day 1, Problem 4

Let n>3n > 3 be an integer. Let Ω\Omega be the set of all triples of distinct elements of {1,2,…,n}\{1, 2, \dots, n\}. Let mm denote the minimal number of colours which suffice to colour Ω\Omega so that whenever 1≤a<b<c<d≤n1 \le a < b < c < d \le n, the triples {a,b,c}\{a, b, c\} and {b,c,d}\{b, c, d\} have different colours. Prove that

1100log⁡log⁡n≤m≤100log⁡log⁡n.\frac{1}{100} \log\log n \le m \le 100 \log\log n.
Original from the official PDFLet n > 3 be an integer. Let Ω be the set of all triples of distinct elements of {1, 2, . . . , n}. Let m denote the minimal number of colours which suffice to colour Ω so that whenever 1 ≤ a < b < c < d ≤ n, the triples {a, b, c} and {b, c, d} have different colours. Prove that 1 log log n ⩽ m ⩽ 100 log log n. 100

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Danila Cherkashin, St. Petersburg)

Hint: Define two graphs, one on Ω\Omega and another graph on pairs (2-element sets).

Solution. For k=1,2,…,nk = 1, 2, \ldots, n denote by Ωk\Omega_k the set of all (nk)\binom{n}{k} kk-subsets of [n][n]. For each k=1,2,…,n−1k = 1, 2, \ldots, n-1 define a directed graph GkG_k whose vertices are elements of Ωk\Omega_k, and edges correspond to elements of Ωk+1\Omega_{k+1} as follows: if 1⩽a1<a2<…<ak+1⩽n1 \leqslant a_1 < a_2 < \ldots < a_{k+1} \leqslant n, then the edge of GkG_k corresponding to (a1,…,ak+1)(a_1, \ldots, a_{k+1}) goes from (a1,…,ak)(a_1, \ldots, a_k) to (a2,…,ak+1)(a_2, \ldots, a_{k+1}).

For a directed graph G=(V,E)G = (V, E) we call a subset E1⊂EE_1 \subset E admissible, if E1E_1 does not contain a directed path a−b−ca - b - c of length 2. Define b-index b(G)b(G) of the GG as the minimal number of admissible sets which cover EE. As usual, a subset V1⊂VV_1 \subset V is called independent, if there are no edges with both endpoints in V1V_1; a chromatic number of GG is defined as the minimal number of independent sets which cover VV.

A straightforward but crucial observation is the following

Lemma. For all k=2,3,…,nk = 2, 3, \ldots, n a subset Ak⊂ΩkA_k \subset \Omega_k is independent in GkG_k if and only if it is admissible as a set of edges of Gk−1G_{k-1}.

Corollary. χ(Gk)=b(Gk−1)\chi(G_k) = b(G_{k-1}) for all k=2,3,…,nk = 2, 3, \ldots, n.

Now the bounds for numbers χ(Gk)\chi(G_k) follow by induction using the following general

Lemma. For a directed graph G=(V,E)G = (V, E) we have

log⁡2χ(G)⩽b(G)⩽2⌈log⁡2χ(G)⌉.\log_2 \chi(G) \leqslant b(G) \leqslant 2\lceil \log_2 \chi(G) \rceil.

Proof. 1) Denote b(G)=mb(G) = m and prove that log⁡2χ(G)⩽m\log_2 \chi(G) \leqslant m. For this we take a covering of EE by mm admissible subsets E1,…,EmE_1, \ldots, E_m and define a color c(v)c(v) of a vertex v∈Vv \in V as the following subset of [m][m]: c(v):={i∈[m]:∃vw∈Ei}c(v) := \{i \in [m] : \exists vw \in E_i\}. Note that for any edge vw∈Evw \in E there exists ii such that vw∈Eivw \in E_i which yields i∈c(v)i \in c(v) and i∉c(w)i \notin c(w), therefore c(v)≠c(w)c(v) \ne c(w). So, each color class is an independent set and we get χ(G)⩽2m\chi(G) \leqslant 2^m as needed.

  1. Denote χ(G)=k\chi(G) = k and prove that b(G)⩽2⌈log⁡2k⌉b(G) \leqslant 2\lceil \log_2 k \rceil. Take a proper coloring τ ⁣:V→{0,1,…,k−1}\tau\colon V \to \{0, 1, \ldots, k-1\} (that means that τ(u)≠τ(v)\tau(u) \ne \tau(v) for all edges vu∈Evu \in E). For an integer x∈{0,1,…,k−1}x \in \{0, 1, \ldots, k-1\} take a binary representation x=∑i=0r−1εi(x)2ix = \sum_{i=0}^{r-1} \varepsilon_i(x) 2^i, εi(x)∈{0,1}\varepsilon_i(x) \in \{0, 1\}, where r=⌈log⁡2k⌉r = \lceil \log_2 k \rceil. Consider the following 2r2r subsets of EE, two subsets Ei,+E_{i,+} and Ei,−E_{i,-} for each i∈{0,1,…,k−1}i \in \{0, 1, \ldots, k-1\}:
    Ei,+={vu∈E ⁣:εi(τ(v))=0,εi(τ(u))=1},Ei,−={vu∈E ⁣:εi(τ(v))=1,εi(τ(u))=0}.\begin{aligned} E_{i,+} &= \{vu \in E\colon \varepsilon_i(\tau(v)) = 0, \varepsilon_i(\tau(u)) = 1\}, \\ E_{i,-} &= \{vu \in E\colon \varepsilon_i(\tau(v)) = 1, \varepsilon_i(\tau(u)) = 0\}. \end{aligned}

Each of them is admissible, and they cover EE, thus b(G)⩽2rb(G) \leqslant 2r.

Note that χ(G1)=n\chi(G_1) = n, thus b(G1)⩾log⁡2nb(G_1) \geqslant \log_2 n. Actually we have b(G1)=⌈log⁡2n⌉b(G_1) = \lceil \log_2 n \rceil: indeed, if we define τ(v)=v−1\tau(v) = v - 1 for all v∈[n]=Ω1v \in [n] = \Omega_1, then the above sets Ei,+E_{i,+} cover all edges of G1G_1.

The Lemma above now yields for our number m=χ(G3)=b(G2)m = \chi(G_3) = b(G_2) the following bounds, which are better than required:

b(G2)⩾log⁡2χ(G2)=log⁡2b(G1)=log⁡2⌈log⁡2n⌉b(G2)⩽2⌈log⁡2χ(G2)⌉=2⌈log⁡2b(G1)⌉=2⌈log⁡2⌈log⁡2n⌉⌉.\begin{aligned} b(G_2) &\geqslant \log_2 \chi(G_2) = \log_2 b(G_1) = \log_2 \lceil \log_2 n \rceil \\ b(G_2) &\leqslant 2\lceil \log_2 \chi(G_2) \rceil = 2\lceil \log_2 b(G_1) \rceil = 2\lceil \log_2 \lceil \log_2 n \rceil \rceil. \end{aligned}

Remark. Actually the upper bound in the Lemma may be improved to (1+o(1))log⁡2χ(G)(1 + o(1)) \log_2 \chi(G) that yields m=(1+o(1))log⁡2log⁡2nm = (1 + o(1)) \log_2 \log_2 n.

Transcribed from the official solutions, page 4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?