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$ – Alessandro Codenotti May 7 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$ – Andreas Blass May 7 at 17:34

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, privacy policy and cookie policy

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