Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak coloring if for all $e \in E$ the restriction $c|_e$ is not constant. We call $c$ a strong coloring, if for all $e \in E$ the restriction $c|_e$ is injective. We let $\chi_w(H)$ be the smallest cardinal such that there is a weak coloring to that cardinal, and we define $\chi_s(H)$ similarly for strong colorings.

Suppose all $e\in E$ have finitely many elements. (I.e., $H$ has finite rank(*).) We do not require that $H$ be uniform. Is it possible that $\chi_w(H) < \aleph_0$ but $\chi_s(H) \geq \aleph_0$?


(*) Cf. e.g. page 2 in [C. Berge, Hypergraphs, North Holland, 1989, ISBN 0 444 87489 5].


Since the OP did not require that the rank of the hypergraph be bounded, the answer to the question is 'obviously yes'. An example is any hypergraph $H$ which is(*) the

disjoint union of $\aleph_0$-many hyperedges of increasing cardinality.

Then $\chi_w(H)=2$ but $\chi_s(H)=\aleph_0$. This answers the question.


(*)Formally,let $\{v_{i,j}\colon (i,j)\in\omega^2\}$ be a set of $\aleph_0$-many pairwise distinct indeterminates, and let $H:=(\omega,\{\{ v_{i,j}\mid\ j\in i \}\mid\ i\in\omega\})$.


Your Answer

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

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