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


1 Answer 1


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


Your Answer

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

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