For any set $X$ and cardinal $\kappa$, we denote by $[X]^\kappa$ the collection of subsets of $X$ having cardinality $\kappa$.

If $H=(V,E)$ is a hypergraph, and $\kappa$ is a cardinal, we say that a map $c:V\to \kappa$ is a coloring if for every $e\in E$ with $|e|\geq 2$ the restriction $c|_e$ is non-constant. By $\chi(H)$ we denote the minimum cardinal such that there is a coloring $c:V\to \kappa$.

Let cardinals $\kappa\geq \omega$ and $\alpha,\beta$ with $2< \alpha, \beta \leq \kappa$ be given.

Is there necessarily $E \subseteq [\kappa]^\beta$ such that $\chi(\kappa,E) = \alpha$? (There is an easy positive answer for either $\alpha$ or $\beta$ equal to $2$.)

  • 1
    $\begingroup$ Could you confirm that you mean non-constant rather than injective? For example, if I have a 3-edge with {a,b,c}, then I can color both a and c red, and b blue? $\endgroup$ – Joel David Hamkins Jan 3 at 15:44
  • 1
    $\begingroup$ @JoelDavidHamkins it is standard terminology in the hypergraph colorings theory $\endgroup$ – Fedor Petrov Jan 4 at 15:54
  • 1
    $\begingroup$ @FedorPetrov Thanks very much. $\endgroup$ – Joel David Hamkins Jan 4 at 17:01
  • 3
    $\begingroup$ "Injective on edges" is the wrong generalisation of proper colouring to hypergraphs because it reduces to graph colouring by replacing hyperedges by graph cliques, whereas "non-constant" is more expressive. $\endgroup$ – Ben Barber Jan 5 at 15:15
  • 1
    $\begingroup$ For $\kappa=\beta=\aleph_\omega$, no subgraph of $[\kappa]^\beta$ has chromatic number greater than $\omega$, since we can color $\gamma\in\kappa$ with $n$ if $\aleph_{n-1}\leq\gamma<\alpha_n$, taking $\alpha_{-1}=0$ for convenience. I suspect the answer might be positive whenever $\alpha\leq cf(\kappa)$. $\endgroup$ – Wojowu Jan 6 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.