5
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 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
    Commented Jan 3, 2020 at 15:44
  • 1
    $\begingroup$ @JoelDavidHamkins it is standard terminology in the hypergraph colorings theory $\endgroup$
    – Fedor Petrov
    Commented Jan 4, 2020 at 15:54
  • 1
    $\begingroup$ @FedorPetrov Thanks very much. $\endgroup$
    – Joel David Hamkins
    Commented Jan 4, 2020 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
    Commented Jan 5, 2020 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
    Commented Jan 6, 2020 at 15:34

0

Reset to default

You must log in to answer this question.