Skip to main content
Made the title more informative, thus facilitating future searches. Added the technical term 'rank', with a reference. Added a note that equal cardinalities of the edges are not required.
Source Link
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

Weak Strong and strong hypergraph coloringsweak chromatic number of infinite hypergraphs of finite rank

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

Weak and strong hypergraph colorings

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. Is it possible that $\chi_w(H) < \aleph_0$ but $\chi_s(H) \geq \aleph_0$?

Strong and weak chromatic number of infinite hypergraphs of finite rank

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

Source Link

Weak and strong hypergraph colorings

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. Is it possible that $\chi_w(H) < \aleph_0$ but $\chi_s(H) \geq \aleph_0$?