# Does every maximal almost disjoint family have the same chromatic number?

If $$H=(V,E)$$ is a hypergraph such that $$V\neq\varnothing\neq E$$ and $$|e| > 1$$ for all $$e\in E$$, and $$\kappa\neq\varnothing$$ is a cardinal, we say that a map $$c:V\to\kappa$$ is a coloring if the restriction $$c\restriction_e: e\to \kappa$$ is non-constant for each $$e\in E$$. We denote by $$\chi(H)$$ the smallest cardinal $$\kappa$$ such that there is a coloring $$c:V \to \kappa$$.

Assume the Axiom of Choice. If $${\cal A, B}$$ are infinite maximal almost disjoint families on $$\omega$$, do we necessarily have $$\chi((\omega, {\cal A}))=\chi((\omega,{\cal B}))$$?

• If I understand the definitions here, the members of the MAD family are the hyperedges, and the vertices are integers. So clearly there is a coloring in $\aleph_0$ colors, so it's really about asking it you can have a MAD family with finite chromatic number, which to me sounds like that it's impossible. – Asaf Karagila Aug 10 '20 at 6:03
• @AsafKaragila I think it does happen - in fact, any MAD family can be turned into one with chromatic number $2$. Suppose $\mathfrak{X}\subset\mathcal{P}(\omega)$ is MAD; I claim that the new family $$\mathfrak{X}[2]:=\{\{2a: a\in A\}\cup\{2a+1: a\in A\}: A\in\mathfrak{X}\}$$ is also mad. Suppose $Y\subseteq\omega$ is an infinite set such that $Y\not\in\mathfrak{X}[2]$ but $Y\cap B$ is finite for each $B\in\mathfrak{X}[2]$. One of $Y\cap\{Evens\}$ and $Y\cap\{Odds\}$ is infinite; WLOG, it's the former. Then $\{x: 2x\in Y\}$ is a counterexample to the MADness of $\mathfrak{X}$. Or did I mess up? – Noah Schweber Aug 10 '20 at 6:24
• @DominicvanderZypen Well even if I'm right, my comment doesn't answer the question. – Noah Schweber Aug 10 '20 at 6:27
• It looks like a completely separable mad family can’t have a finite chromatic number: otherwise, there is a color n such that the set X of integers getting that color is in the coideal generated by the family, and by complete separability, X contains a monochromatic member of the mad family. – Haim Aug 11 '20 at 5:33
• @bof I'll hopefully find some time later today or tomorrow to have a closer look at the Erdos-Shelah paper. Regardless of their paper, the following seems like an interesting question to me: does the non-existence of a 2-coloring imply complete separability? the definitions look very close to each other, and a positive answer will imply the equivalence of complete separability, the non-existence of a 2-coloring and the non-existence of a finite coloring. – Haim Aug 11 '20 at 12:37

A negative answer to the question follows by the proof of Theorem 1.1 in the following paper of Erdős and Shelah, where for every $$n<\omega$$ they construct a mad family that is $$(n+1)$$-colorable but not $$n$$-colorable:
It should also be noted that a completely separable mad family can't have a finite chromatic number: given any finite coloring, there is a color $$n$$ such that the set $$x$$ of integers getting that color belongs to the coideal generated by the mad family. By complete separability, $$x$$ contains a monochromatic member of the family. I won't be surprised if there are also $$ZFC$$ constructions of such families, but I haven't thought about it enough.
• Suppose you partition $\omega$ into infinitely many infinite sets $A_n$ and on each $A_n$ you construct a MAD family with chromatic number $n$, then the union will be an AD family with chromatic number $\aleph_0$, and if you extend it to a maximal AD family, the chromatic number won't get any smaller, isn't that right? – bof Aug 12 '20 at 5:34