Uniquely colorable hypergraphs

Abstract

An $r$-uniform hypergraph is uniquely $k$-colorable if there exists exactly one partition of its vertex set into $k$ parts such that every edge contains at most one vertex from each part. For integers $k\ge r\ge 2$, let ${\Phi }_{k,r}$ denote the minimum real number such that every $n$-vertex $k$-partite $r$-uniform hypergraph with positive codegree greater than ${\Phi }_{k,r}\cdot n$ and no isolated vertices is uniquely $k$-colorable. A classic result by of Bollobás\cite{Bol78} established that ${\Phi }_{k,2}=\frac{3k-5}{3k-2}$ for every $k\ge 2$. We consider the uniquely colorable problem for hypergraphs. Our main result determines the precise value of ${\Phi }_{k,r}$ for all $k\ge r\ge 3$. In particular, we show that ${\Phi }_{k,r}$ exhibits a phase transition at approximately $k=\frac{4r-2}{3}$, a phenomenon not seen in the graph case. As an application of the main result, combined with a classic theorem by Frankl--Füredi--Kalai, we derive general bounds for the analogous problem on minimum positive $i$-degrees for all $1\le i<r$, which are tight for infinitely many cases.

29 pages, 10 figures, comments are welcome