# Coloring a complete regular hypergraph

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$$?

• $\chi((n,[n]^k))=\lceil n/(k-1)\rceil$ – Fedor Petrov Jan 31 '19 at 15:46

## 1 Answer

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$$.