For any set $X$ and positive integer $k$ denote by $[X]^k$ the set of subsets $S\subseteq X$ such that $|S|=k$.

Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the restriction $c|_e$ is not constant. By $\chi(H)$ we denote the smallest cardinal $\kappa$ such that there is a coloring $c:V\to \kappa$.

Given any positive integer $n$, we consider it as a finite cardinal $n = \{0,\ldots,n-1\}$. It is easy to see that if $a, b$ are positive integers with $a < b \leq 2a$ then $\chi\big((2a, [2a]^b)\big) = 2$: color the even members of $2a$ with $0$, and the odd members with $1$.

Given a fixed positive integer $k>2$, is there always $n>2k-2$ such that $\chi\big((n, [n]^k)\big) = n$?

  • 2
    $\begingroup$ $\chi((n,[n]^k))=\lceil n/(k-1)\rceil$ $\endgroup$ Jan 31, 2019 at 15:46

1 Answer 1


Notice that a map $c : n \to \kappa$ is a coloring of $(n,[n]^k)$ iff no element of $\kappa$ has $k$ distinct preimages. Hence by the pigeonhole principle $\chi((n,[n]^k)) = \lceil\frac{n}{k-1}\rceil$.

Now for any $k \geq 3$ and $n > 2k-2$ we have $n > 2$, so $\frac{n}{n-1} < 2 \leq k-1$, implying $\frac{n}{k-1} < n-1$.

Thus $\chi((n,[n]^k)) = \lceil\frac{n}{k-1}\rceil < n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.