For fixed positive integers $r, k$ and $ell$ with $1 leq ell < r$ and an $r$-uniform hypergraph $H$, let $kappa (H, k,ell)$ denote the number of $k$-colorings of the set of hyperedges of $H$ for which any two hyperedges in the same color class intersect in at least $ell$ elements. Consider the function $KC(n,r,k,ell)=max_{Hin{mathcal H}_{n}} kappa (H, k,ell) $, where the maximum runs over the family ${mathcal H}_n$ of all $r$-uniform hypergraphs on $n$ vertices. In this paper, we determine the asymptotic behavior of the function $KC(n,r,k,ell)$ for every fixed $r$, $k$ and $ell$ and describe the extremal hypergraphs. This variant of a problem of ErdH{o}s and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the ErdH{o}s--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {bf 12} (1961), 313--320].
Download