The last problem in 2022 IMC Day 1 strongly correlates with graph theory. In its official solution, the fundamental approach can be rephrased as follows.



> 
> Give a digraph $G=(V,E)$. We call a subset of $E$ *admissible* such that it doesn't contain any directed paths of length $2$. Let $b(G)$ denote the minimal number of admissible sets that cover $E$.
> 
> 
> 


The comment stated that $b(G) = \left( 1 + o \left( 1 \right) \right) \log\_2 \chi(G)$, where $\chi(G)$ is the chromatic number of $G$.


The lower bound is easy. Given an admissible cover $\mathcal{E}$, for each vertex, we convert the information on whether $E\_i$ in $\mathcal{E}$ contains an edge incident to $v$ into a binary string. Now color $V$ according to their corresponding string. Hence we conclude that $2^{b(G)} \geqslant \chi(G)$.


However, the upper bound is intractable. In its solution, it only states that $b(G) \leqslant 2\left \lceil \log\_2 \chi(G) \right \rceil$. I searched a lot but failed to find any context about $b(G)$. Talking about the chromatic number of digraphs, I can reflect no more than the Gallai-Roy theorem, which states that there must be a path of length larger than $\chi(G)$. But it seems rare to consider covers splitting path into pieces and I don't know enough tools to solve this sort of problem.


So my question is, how can I prove the upper bound of $b(G)$ is also $\left( 1 + o \left( 1 \right) \right) \log\_2 \chi(G)$? Thanks.



Minimal digraph covering with no 2-path edge sets is of size $\left( 1 + o \left( 1 \right) \right) \log_2 \chi(G)$
This is beautiful application of Sperner theorem on antichains. Consider a bijection between the vertices and the family $\binom{[n]}{n/2}$, which realizes the maximum in the mentioned theorem.
Element $i$ from 1 to $n$ are the palette. One may color a vertex in any color containing in the corresponding set. The antichain property implies that the coloring is proper.


P. S. In a folklore it is related with a Nero Wolfe, who have deal with $m$ people, there are a murderer and a witness among them. Each day Nero asks Archi to collect some of these people and Nero succeeds iff he has the witness and does not have the murderer in th set. What is the smallest number of days, Nero needs to win?


