Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. Let $$E = \big\{\{A,B\}: A,B \in [\omega]^\omega \text{ and } |A\cap B| \text{ is finite}\big\}.$$

We consider the graph $G=([\omega]^\omega,E)$. Maximal cliques in $G$, also known as maximal almost disjoint families, are uncountable, and it is consistent that every clique in $G$ has cardinality $< 2^{\aleph_0}$.

Is it consistent that $\chi(G) < 2^{\aleph_0}$?

  • 6
    $\begingroup$ What is consistent is that $\mathfrak a<2^{\aleph_0}$ but surely there are MAD families of cardinality $2^{\aleph_0}$, here is one: fix a bijection $f:\omega\to \Bbb Q$ and for every $r\in\Bbb R\setminus\Bbb Q$ fix a sequence $(q^r_i)$ of rational numbers converging to $r$. Take preimages through $f$ of those sequences and extend to a maximal family to have a MAD family of cardinality continuum. $\endgroup$ Commented May 7, 2021 at 13:52
  • 2
    $\begingroup$ @AlessandroCodenotti Since your correction immediately provides a negative answer to the question, it would be good to convert your comment to an answer, so that the software doesn't think the question is unanswered. $\endgroup$ Commented May 7, 2021 at 17:34

1 Answer 1


No, $\chi(G)=\mathfrak c$, in fact $G$ contains a complete subgraph on $\mathfrak c$ vertices.

A simple way to construct one is by fixing a bijection $f\colon\Bbb Q\to\omega$ and fixing, for every $r\in\Bbb R\setminus\Bbb Q$, a sequence $(q^r_i)_{i\in\omega}$ of rationals numbers converging to $r$. Taking the images through $f$ of those sequences gives an almost disjoint family of cardinality $\mathfrak c$ (which can be extended to a mad family of the same cardinality by Zorn's lemma but that's not even needed).

The consistency result is that $\mathfrak a$ can be strictly between $\aleph_0$ and $\mathfrak c$, that is there can be some mad family of cardinality less than continuum.


Your Answer

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

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