Coloring chains for compression with uncertain priors (Q668010)

A chain of length $k$ and size $t$ is a nested sequence of sets $A_0\subseteq A_0\subseteq\cdots \subseteq A_{k}\subseteq [N]=\{1,\dots,N\}$ where $|A_0|=1$ and $|A_{k}|=t$ and $N$ is a natural number. Such chains are denoted by $\left\langle \alpha, A_1,\dots,A_{k}\right\rangle$ where $A_0=\{\alpha\}$. Graph $U(N,t,k)$ contains as vertices all chains of length $k$ and size at most $t$. Two vertices $\left\langle \alpha, A_1,\dots,A_{k}\right\rangle$ and $\left\langle \beta, B_1,\dots,B_{k}\right\rangle$ of $U(N,t,k)$ are adjacent if $\alpha\neq\beta$, $A_i\subseteq B_{i+1}$ and $B_i\subseteq A_{i+1}$ for every $i\in\{0,\dots,k-1\}$. \par The chromatic number of $U(N,t,k)$ is strongly connected with a certain problem of transmitting a message between two persons. This work brings an improved upper and lower bounds on $\chi(U(N,t,k))$.