Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$.

A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal, such that for every $e\in E$ with $|e|\geq 2$ the restriction $c|_e$ is non-constant. We denote the minimal cardinal $\kappa$ such that there is a coloring $c: V\to \kappa$ by $\chi(H)$ and call it the chromatic number of $H$

If $A\subseteq [\omega]^\omega$ is finite or countable, then the chromatic number of $(\omega, A)$ equals $2$. This motivates the following cardinals: for any integer $n\geq 2$ let ${\bf k}_n$ be the minimum cardinality of a set $A\subseteq [\omega]^\omega$ such that $\chi(\omega, A) > n$.

Is it consistent in ${\sf ZFC}$ that $${\bf k}_n < {\bf k}_{n+1} < 2^{\aleph_0}$$ for all integers $n\geq 2$?


The cardinals $\bf k_n$ ($2\le n\lt\omega$) are all equal.

Lemma. Let $\kappa$ be an infinite cardinal. Given a set $A\subseteq[\omega]^\omega$ with $|A|=\kappa$ and $\chi(\omega,A)\gt n$, we can construct a set $B\subseteq[\omega]^\omega$ with $|B|=\kappa$ and $\chi(\omega,B)\gt n^2$.

Proof. For each $a\in A$ choose a collection $B_a\subseteq[a]^\omega$ so that the hypergraph $(a,B_a)$ is isomorphic to $(\omega,A)$, and let $B=\bigcup_{a\in A}B_a$.

Let $(\omega,B)$ be colored with $n^2$ colors; let $[n]\times[n]$ be the set of colors, and let $x\mapsto(f(x),g(x))$ be the coloring. Since $\chi(\omega,A)\gt n$, there is a set $a\in A$ such that $f$ is constant on $a$. Then, since $\chi(a,B_a)\gt n$, there is a set $b\in B_a$ such that $g$ is constant on $b$.

Corollary. If there is a set $A\subseteq[\omega]^\omega$ with $|A|=\kappa$ and $\chi(\omega,A)\gt2$, then there is a set $B\subseteq[\omega]^\omega$ with $|B|=\kappa$ and $\chi(\omega,B)=\aleph_0$.

  • $\begingroup$ Wonderful @bof - and happy new year! - Do you happen to know whether ${\bf k}_2 < 2^{\aleph_0}$ is consistent? $\endgroup$ – Dominic van der Zypen Jan 3 at 17:26
  • $\begingroup$ I was wondering whether ${\bf k}_2 \in \{{\frak r}, {\frak s}\}$, denoting the reaping and splitting numbers respectively, could be proved, but I haven't had time to check this. $\endgroup$ – Dominic van der Zypen Jan 3 at 17:44
  • 4
    $\begingroup$ $\mathbf k_2=\mathfrak r$. The only difference between the definitions is that the former is about splitting into two nonempty sets where the latter is about splitting into two infinite sets. But that doesn't affect the cardinality because you can adjoin to any hypergraph $A$ all those sets that differ only finitely from members of $A$, and this won't increase the cardinality of $A$. $\endgroup$ – Andreas Blass Jan 4 at 0:11
  • $\begingroup$ Thank you @AndreasBlass - and happy new year. $\endgroup$ – Dominic van der Zypen Jan 4 at 8:04

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.