0
$\begingroup$

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 map $c:V\to \kappa$.

Is there a hypergraph $H=(V,E)$ with $V$ infinite, $|E|<|V|$ and $\chi(H) = |V|$?

$\endgroup$

1 Answer 1

2
$\begingroup$

EDIT: My original answer (below) is correct but not really optimal. This is easier: simply well-order the set of vertices and greedily color them using the well-ordering. More precisely, if you reach a vertex $v$ and have already colored all vertices appearing before $v$ in the well-ordering, color $v$ with the smallest ordinal that does not create a monochromatic edge with what has been done before. Since $v$ is contained in at most $|E|$ edges, there are at most $|E|$ forbidden colors, so the range of this coloring is at most $|E| + 1$. Thus, $\chi(H) \leq |E| + 1$ (or, sometimes better, the maximum degree of the hypergraph plus 1).

Original answer: No, this is impossible. It is always the case that $\chi(H) \leq |E|$ (or at least $\chi(H) \leq 2|E|$ if $E$ is finite). To see this, note that it's easy to define an injective partial function $c_0$ from a subset of $V$ to $|E|$ (or $2|E|$ if $E$ is finite) such that, for all $e \in E$, we have $|\mathrm{dom}(c_0) \cap e| \geq 2$ (simply enumerate the edges in order type $|E|$ and take care of them one at a time). Then any extension of $c_0$ to a function $c:V \rightarrow |E|$ will be a hypergraph coloring of $H$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .