The existence of uniform hypergraphs for which the interpolation property of complete coloring fails (Q2065902)

The authors study the so-called interpolation property for uniform hypergraphs, which concerns complete (vertex) colorings of uniform hypergraphs. The main result of the paper states that for any \(k \geq 3\), there exist \(k\)-uniform hypergraphs that do not have the interpolation property in a strong sense (defined below). A \(k\)-uniform hypergraph \(H\) is a hypergraph whose edges all have cardinality \(k\). A \(t\)-coloring of a hypergraph \(H\) is an assignment of colors to the vertices of \(H\), where the colors come from a collection of \(t\) colors. A coloring is proper if any two vertices that are in an edge receive distinct colors. The chromatic number of \(H\), denoted by \(\chi(H)\), is the minimum number of colors needed to properly color \(H\). A coloring of a \(k\)-uniform hypergraph \(H\) is complete if is proper and every subset of \(k\)-colors appears on at least one edge of \(H\). The achromatic number of \(H\), denoted by \(\psi(H)\) is the largest integer \(t\) such that there is a complete \(t\)-coloring of \(H\). It is known that every graph \(G\) has a complete coloring. A result of \textit{F. Harary} et al. [Port. Math. 26, 453--462 (1967; Zbl 0187.20903)] states that that if \(G\) is a graph, then \(G\) admits a \(t\)-coloring for every \(t\) such that \(\chi(G) \leq t \leq \psi(G)\). In other words, every graph has the interpolation property. On the other hand, \textit{K. Edwards} and \textit{P. Rzążewski} [Discrete Math. 343, No. 2, Article ID 111673, 12 p. (2020; Zbl 1429.05065)] showed that, for all \(k \geq 9\), there exist hypergraphs \(H\) which have complete \(\chi(H)\)-coloring and \(\psi(H)\)-colorings, but no complete \(t\)-coloring for some \(\chi(H) \leq t \leq \psi(H)\). The authors strengthen the result of Edwards and Rzążewski [loc. cit.], and show that for any \(k \geq 3\), there exist hypergraphs \(H\) which have complete \(\chi(H)\)-coloring and \(\psi(H)\)-colorings, but no complete \(t\)-coloring for any \(\chi(H) \leq t \leq \psi(H)\).