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



Induced subgraphs of the almost-disjointness graph
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](https://staff.fnwi.uva.nl/j.vanmill/papers/papers1984/handbook.pdf)), 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.


