IMC 2022 · Day 1 · P4

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

For $k = 1, 2, \dots, n$ denote by $\Omega_k$ the set of all $\binom{n}{k}$ $k$-subsets of $[n]$. For each $k = 1, 2, \dots, n-1$ define a directed graph $G_k$ whose vertices are elements of $\Omega_k$, and edges correspond to elements of $\Omega_{k+1}$ as follows: if $1 \leqslant a_1 < a_2 < \dots < a_{k+1} \leqslant n$, then the edge of $G_k$ corresponding to $(a_1, \dots, a_{k+1})$ goes from $(a_1, \dots, a_k)$ to $(a_2, \dots, a_{k+1})$.

For a directed graph $G = (V, E)$ we call a subset $E_1 \subset E$ admissible, if $E_1$ does not contain a directed path $a - b - c$ of length 2. Define b-index $b(G)$ of the $G$ as the minimal number of admissible sets which cover $E$. As usual, a subset $V_1 \subset V$ is called independent, if there are no edges with both endpoints in $V_1$; a chromatic number of $G$ is defined as the minimal number of independent sets which cover $V$.

A straightforward but crucial observation is the following

Lemma. For all $k = 2, 3, \dots, n$ a subset $A \subset \Omega_k$ is independent in $G_k$ if and only if it is admissible as a set of edges of $G_{k-1}$.

Corollary. $\chi(G_k) = b(G_{k-1})$ for all $k = 2, 3, \dots, n$.

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

Lemma. For a directed graph $G = (V, E)$ we have $$\log_2 \chi(G) \leqslant b(G) \leqslant 2 \lceil \log_2 \chi(G) \rceil.$$ Proof. 1) Denote $b(G) = m$ and prove that $\log_2 \chi(G) \leqslant m$. For this we take a covering of $E$ by $m$ admissible subsets $E_1, \dots, E_m$ and define a color $c(v)$ of a vertex $v \in V$ as the following subset of $[m]$: $c(v) := \{ i \in [m] : \exists vw \in E_i \}$. Note that for any edge $vw \in E$ there exists $i$ such that $vw \in E_i$ which yields $i \in c(v)$ and $i \notin c(w)$, therefore $c(v) \ne c(w)$. So, each color class is an independent set and we get $\chi(G) \leqslant 2^m$ as needed.

2) Denote $\chi(G) = k$ and prove that $b(G) \leqslant 2 \lceil \log_2 k \rceil$. Take a proper coloring $\tau : V \to \{0, 1, \dots, k-1\}$ (that means that $\tau(u) \ne \tau(v)$ for all edges $vu \in E$). For an integer $x \in \{0, 1, \dots, k-1\}$ take a binary representation $x = \sum_{i=0}^{r-1} \varepsilon_i(x) 2^i$, $\varepsilon_i(x) \in \{0, 1\}$, where $r = \lceil \log_2 k \rceil$. Consider the following $2r$ subsets of $E$, two subsets $E_{i,+}$ and $E_{i,-}$ for each $i \in \{0, 1, \dots, k-1\}$: $$\begin{gather*} E_{i,+} = \{ vu \in E : \varepsilon_i(\tau(v)) = 0, \varepsilon_i(\tau(u)) = 1 \}, \\ E_{i,-} = \{ vu \in E : \varepsilon_i(\tau(v)) = 1, \varepsilon_i(\tau(u)) = 0 \}. \end{gather*}$$ Each of them is admissible, and they cover $E$, thus $b(G) \leqslant 2r$.

Note that $\chi(G_1) = n$, thus $b(G_1) \geqslant \log_2 n$. Actually we have $b(G_1) = \lceil \log_2 n \rceil$: indeed, if we define $\tau(v) = v - 1$ for all $v \in [n] = \Omega_1$, then the above sets $E_{i,+}$ cover all edges of $G_1$.

The Lemma above now yields for our number $m = \chi(G_3) = b(G_2)$ the following bounds, which are better than required: $$\begin{gather*} 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{gather*}$$

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