0
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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