# 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}:=\{\{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}$ but $Y\cap B$ is finite for each $B\in\mathfrak{X}$. 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

## 1 Answer

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:

Erdős, Paul; Shelah, Saharon, Separability properties of almost-disjoint families of sets, Isr. J. Math. 12, 207-214 (1972). ZBL0246.05002.

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
• Oops! I corrected the answer now. Yes, the Erdos-Shelah construction is done in ZFC. I didn't read the entire paper, but just going through the statements of the theorems (and keeping in mind that we don't know what n-separability is), it doesn't look like they construct a mad family with an infinite chromatic number (the more I think about it, the less trivial it seems. Even a consistency result would be nice). One of the reasons that I write "mad" is to reflect the fact that we use the Hebrew word for "mad/crazy" when we talk about those families. :) – Haim Aug 12 '20 at 5:38
• And I suppose "mad" families are related somehow to "happy" families, which I've heard of before though I don't remember the definition. – bof Aug 12 '20 at 5:39
• @bof It looks like your suggested construction works. Indeed, mad families are related to happy families: the coideal corresponding to an infinite almost disjoint family is a happy family. Both terms were introduced by Mathias (though, sadly, he chose to write "MAD" instead of "mad" in his "Happy families" paper). – Haim Aug 12 '20 at 5:52