1
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2

You must log in to answer this question.

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