-1
$\begingroup$

If $n\in\mathbb{N}$ is a non-negative integer, we consider it as a cardinal, so $n = \{0, \ldots, n-1\}$. If $X$ is a set, and $\kappa$ is a cardinal, we let $[X]^\kappa$ be the collection of subsets of $X$ having cardinality $\kappa$.

If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, a map $c:V\to \kappa$ is said to be a coloring if the restriction $c\restriction_e$ is non-constant whenever $e\in E$ has more than $1$ element. The smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ is said to be the chromatic number of $H=(V,E)$, and we denote it by $\chi(H)$.

Question. Given integers $n\geq k \geq 3$, what is the value of $\chi(n,[n]^k)$ in terms of $n$ and $k$?

$\endgroup$
3
  • $\begingroup$ I don't think this is the chromatic number and maybe should be called something else in order to avoid confusion. Usually, I think, one requires $c$ restricted to $e$ to be injective rather than non-constant. $\endgroup$ Nov 1, 2021 at 10:39
  • 1
    $\begingroup$ @AbdelmalekAbdesselam what you say reduces to a graph coloring (for a graph which is the union of cliques on the edges), so usually a hypergraph coloring is defined as in OP. $\endgroup$ Nov 1, 2021 at 11:12
  • $\begingroup$ @FedorPetrov: Thanks for correcting me. I guess what I mentioned is the chromatic number of the associated "collinearity graph" as in the paper sciencedirect.com/science/article/pii/S0021869315005657 $\endgroup$ Nov 1, 2021 at 11:51

1 Answer 1

2
$\begingroup$

It is $\lceil \frac{n}{k-1}\rceil$, simply since every color class must contain at most $k-1$ elements.

$\endgroup$

Your Answer

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

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