6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Does $G$ contain the linear graph on $\mathfrak c$ vertices? In other words is there a family of sets $A_\alpha\subseteq\omega,\,\alpha<\mathfrak c$ such that for ever $n\in\mathfrak c$ there are exactly two $m_1,m_2\in\mathfrak c$ with $|A_n\cap A_{m_i}|<\infty$? $\endgroup$ May 15 at 8:00
  • $\begingroup$ @AlessandroCodenotti You mean a $2$-regular graph on $\mathfrak c$ vertices? Why is that called "linear" graph and why "the" if it's not unique? Anyway, good question. $\endgroup$
    – bof
    May 15 at 9:05
  • $\begingroup$ @bof good point, I was thinking about a path of length $\mathfrak c$ but I guess there can be many, disjoint union of finite cycles, of countable chains, etc. $\endgroup$ May 15 at 9:29
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can I summarize it this way? Suppose $G=(V,E)$ is a graph with $|V|=\aleph_1$; then we can define by transfinite induction sets $A_v\in[\omega]^\omega$ so that $A_v\cap A_w$ is finite whenever $\{v,w\}\in E$, and $$\left|\bigcap_{v\in X}A_v\setminus\bigcup_{v\in Y}A_v\right|=\aleph_0$$ whenever $X,Y$ are disjoint finite subsets of $V$ and $X$ is an independent set in $G$? $\endgroup$
    – bof
    May 15 at 19:04
  • $\begingroup$ @bof: Yes, that's pretty much the idea. $\endgroup$
    – Will Brian
    May 15 at 19:14
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ Thanks - this is already very helpful! I'll wait for a couple of days to see whether someone can answer for graphs with $|V|> \aleph_0$ and $|V|\leq 2^{\aleph_0}$ and then accept yours if it remains the only one. Hope that is ok with you. $\endgroup$ May 14 at 19:33
  • 2
    $\begingroup$ I think $|V| \leq \aleph_1$ should always be possible (building the graph recursively, using the fact that $\mathcal P(\omega) / \mathrm{fin}$ is countably saturated). So (if I'm right) a yes answer should at least be consistent. But I don't see how to get all graphs of size $\leq 2^{\aleph_0}$ when CH fails. $\endgroup$
    – Will Brian
    May 14 at 21:07
  • $\begingroup$ @WillBrian I don't understand that "saturated" business, could you illustrate with a simple concrete example? How would you embed $K_{\aleph_1}\cup K_{\aleph_1}$, the union of two vertex-disjoint uncountable complete graphs? (Kicking myself in advance, as I'm sure I'm missing something obvious.) $\endgroup$
    – bof
    May 15 at 8:47
  • $\begingroup$ @bof: Hopefully my answer clears things up. It's a good question whether we can realize $K_{\aleph_1} \cup K_{\aleph_1}$ with a really "simple" family of sets (instead of using some kind of recursion). $\endgroup$
    – Will Brian
    May 15 at 13:31

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.