Induced subgraphs of the almost-disjointness graph

Question

Let $[\omega]^\omega$ denote the collection of infinite subsets on $\omega$, and let $$E=\big\{\{a, b\}:a,b\in [\omega]^\omega \text{ and } |a\cap b| \text{ is finite}\big\}.$$ Is every simple, undirected graph $G=(V,E)$ with $V\leq 2^{\aleph_0}$ isomorphic to an induced subgraph of $([\omega]^\omega, E)$? If not, what if $|V|\leq \aleph_0$?

Answer 1

I claim that every graph with $\leq \aleph_1$ vertices can be embedded in $[\omega]^\omega$ in the manner Dominic described. This means that we have a consistent answer to Dominic's question: the answer is yes assuming that the Continuum Hypothesis holds.

Recall that $\mathcal P(\omega) / \mathrm{fin}$ denotes the Boolean algebra of all subsets of $\omega$ modulo the ideal of finite sets. I'm going to write my answer in terms of $\mathcal P(\omega) / \mathrm{fin}$, because I think that's a good way to think about the problem. (To translate: a subset of $\omega$ is infinite iff its equivalence class in $\mathcal P(\omega) / \mathrm{fin}$ is nonzero, two sets are almost disjoint iff their equivalence classes in $\mathcal P(\omega) / \mathrm{fin}$ are incompatible.)

To prove the claim, we'll use something called the countable saturation of $\mathcal P(\omega) / \mathrm{fin}$. This means:

Suppose $\{a_n :\, n \in \omega\}$ is a countable subset of $\mathcal P(\omega) / \mathrm{fin}$, and let $x$ be a variable. Suppose we have countably many statements (in the first-order language of Boolean algebras) involving $x$ and the $a_n$'s, and no finite subset of these statements is inconsistent. Then there is, in $\mathcal P(\omega) / \mathrm{fin}$, a solution to this infinite system of equations: i.e., there is a value we can assign to $x$ in order to make all the statements true simultaneously.

(For example, if $a_n$ is (the equivalence class of) $\{2^nk :\, k \in \omega\}$ for each $n$, then we could have a countable sequence of statements asserting $0 \neq x < a_n$ for each $n$. No finite subset of these statements is inconsistent (indeed, the first $n$ statements are all satisfied by $x=a_{n+1}$). So countable saturation tells us that these statements are simultaneously satisfiable (e.g., by $\{2^k :\, k \in \omega\}$).)

For a proof that $\mathcal P(\omega) / \mathrm{fin}$ has this property, I'll refer you to van Mill's article in the Handbook of Set Theoretic Topology (link), corollary 1.1.5. The proof is what you might imagine: a delicate diagonalization with lots of bookkeeping.

Now suppose we have a graph $(V,E)$ with $|V| = \aleph_1$. Enumerate $V$ in type $\omega_1$, say $V = \{v_\alpha :\, \alpha < \omega_1 \}$. We'll build, by recursion, a sequence of $a_\alpha$'s such that the mapping $v_\alpha \mapsto a_\alpha$ is an embedding of $(V,E)$ into $\mathcal P(\omega) / \mathrm{fin}$.

For the base case, let $a_0$ be any member of $\mathcal P(\omega) / \mathrm{fin}$ other than $0$ or $1$ (the equivalence classes of $\emptyset$ and $\omega$). At stage $\alpha > 0$, we've obtained a countable collection of members of $\mathcal P(\omega) / \mathrm{fin}$, namely $\{a_\beta :\, \beta < \alpha \}$. Let $x$ be a variable, and consider the following system of equations: $$x \neq 0,1 \quad \qquad \qquad \qquad \qquad \qquad$$ $$\qquad \quad x - \vee F \neq 0 \qquad \text{for any finite } F \subseteq \{a_\beta :\, \beta < \alpha\}$$ $$\qquad \quad x \vee (\vee F) \neq 1 \qquad \text{for any finite } F \subseteq \{a_\beta :\, \beta < \alpha\}$$ $$x - a_\beta \neq 0 \qquad \text{ for any } \beta < \alpha \qquad \ \quad$$ $$a_\beta \wedge x = 0 \qquad \text{whenever } \{ v_\beta,v_\alpha \} \in E$$ $$a_\beta \wedge x \neq 0 \qquad \text{whenever } \{ v_\beta,v_\alpha \} \notin E$$ This is a countable system of equations, and it's easy to check that any finite number of them are simultaneously satisfiable. By the countable saturation of $\mathcal P(\omega) / \mathrm{fin}$, there is some value we can assign to $x$ to satisfy all these equations simultaneously. This is our choice of $a_\alpha$.

This recursion can continue through all countable ordinals. Once the recursion is done, it is easy to see that $a_\alpha \wedge a_\beta = 0$ if and only if $\{\alpha,\beta\} \in E$ for all $\alpha,\beta < \omega_1$.

To translate this back into the language of Dominic's question: for each $\alpha < \omega_1$, let $A_\alpha$ be any representative of the equivalence class $a_\alpha$. Then $A_\alpha \cap A_\beta$ is finite if and only if $\{\alpha,\beta\} \in E$ for all $\alpha,\beta < \omega_1$.

Finally, let me point out that a system of $\aleph_1$ equations like this is not generally satisfiable in $\mathcal P(\omega) / \mathrm{fin}$. That is, $\mathcal P(\omega) / \mathrm{fin}$ is not $\kappa$-saturated for any larger cardinals $\kappa$, not even consistently. The witness to this is Hausdorff gaps, which can be translated to a finitely satisfiable, unsatisfiable system of $\aleph_1$ equations in $\mathcal P(\omega) / \mathrm{fin}$. So to get an outright yes answer to Dominic's question, or even the consistency of a yes with the negation of CH, some new idea will be required.

Answer 2

If $G=(V,E)$ is a countable graph, you can partition $\omega$ into disjoint infinite sets $A_x$ indexed by $x\in\binom V1\cup\binom V2$ and define an injective map $f:V\to[\omega]^\omega$ by $$f(v)=\bigcup\{A_{\{v,w\}}:w\in V\setminus N_G(v)\}\supseteq A_{\{v\}};$$ then $f(v)\cap f(w)=\varnothing$ if $\{v,w\}\in E$ and $f(v)\cap f(w)=A_{\{v,w\}}$ otherwise.

Answer 3

My first thought for the case where $|V|\leq \aleph_0$ is that surely the Rado graph can be constructed as an induced subgraph of $([\omega]^{\omega}, E)$ (since the Rado graph contains a copy of every finite or countably infinite graph, you are then done). Indeed, this is shown in "Existential closure of block intersection graphs of infinite designs having infinite block size" by Horsley, Pike, Sanaei (see the comment after Lemma 2.4).