4
$\begingroup$

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}))$?

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Aug 10 '20 at 6:03
  • 1
    $\begingroup$ @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? $\endgroup$ – Noah Schweber Aug 10 '20 at 6:24
  • $\begingroup$ @DominicvanderZypen Well even if I'm right, my comment doesn't answer the question. $\endgroup$ – Noah Schweber Aug 10 '20 at 6:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Haim Aug 11 '20 at 5:33
  • 2
    $\begingroup$ @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. $\endgroup$ – Haim Aug 11 '20 at 12:37
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – bof Aug 12 '20 at 5:34
  • $\begingroup$ 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. :) $\endgroup$ – Haim Aug 12 '20 at 5:38
  • $\begingroup$ And I suppose "mad" families are related somehow to "happy" families, which I've heard of before though I don't remember the definition. $\endgroup$ – bof Aug 12 '20 at 5:39
  • 1
    $\begingroup$ @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). $\endgroup$ – Haim Aug 12 '20 at 5:52

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.