4
$\begingroup$

If $G=(V,E)$ is a simple, undirected graph and $S\neq T\subseteq V$ are subsets (not necessarily disjoint), we say that $S,T$ are connected to each other if there is $e\in E$ with $$e\cap S\neq \varnothing \neq e\cap T.$$

Question. Is there a graph $G_0=(\omega, E_0)$ where $E_0\subseteq {\omega\choose 2}$ with the following property?

Whenever $G = ({\frak c}, E)$ is a graph on ${\frak c}=2^{\aleph_0}$, then there is ${\cal S}\subseteq {\cal P}(\omega)$ and a bijection $\varphi: {\frak c}\to {\cal S}$ such that for $x\neq y \in {\frak c}$ we have that $$\{x,y\}\in E \text{ if and only if } \varphi(x), \varphi(y) \text{ are connected to each other in } G_0.$$

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ My gut feeling is that if there is a $G_0$ that works it better be the random graph, however if $G$ is a disjoint union of $\mathfrak c$-many complete graphs on $\mathfrak c$ vertices each this seems problematic, although I didn't think very hard about it $\endgroup$ Commented May 27 at 21:54
  • $\begingroup$ @bof - Yes, by $e\cap S\neq \varnothing \neq e \cap T$ I mean to say that both $e\cap S$ and $e\cap T$ are non-empty and I vow to brush up on my notation. $\endgroup$ Commented May 28 at 6:10
  • $\begingroup$ Thanks @bof - perfect! $\endgroup$ Commented May 30 at 6:49
  • $\begingroup$ @DominicvanderZypen But you never clarified the definition of the power graph. For $e=\{a,b\}\in E_0$ did you really want $S$ joined to $T$ whenever $S\cap e$ and $T\cap e$ are both nonempty, whether $S\cap e=\{a\}$ and $T\cap e=\{b\}$, or $S\cap e=\{a\}$ and $T\cap e=\{a,b\}$, or $S\cap e=T\cap e=\{a,b\}$, or $S\cap e=T\cap e=\{a\}$? If that's what you meant it should be stated clearly in the question. How are we to guess that $e\cap S\ne\varnothing\ne e\cap T$ means "$e\cap S\ne\varnothing$ and $e\cap T\ne\varnothing$" when $S\ne T\subseteq V$ does not mean "$S\ne T$ and $T\subseteq V$"? $\endgroup$ Commented May 30 at 20:12
  • 3
    $\begingroup$ I think bof's concern and reasoning are quite valid: (i) I have seen something like $i\ne j\ne k$ (especially in subscripts) to mean that $i,j,k$ are pairwise distinct. With this in mind, I think writing things such as $A\ne\emptyset\ne B$, especially without an explanation, should be avoided. (ii) As it is written, a formula such as $m\ne n\in\Bbb N$ can only be read as "$n\in\Bbb N$ and $m\ne n$ (whatever $m$ might be)", even if some people use this formula in a different sense. I even dislike things like $a,b\in A$ instead of "$a$ and $b$ in $A$". We should write using correct syntax. $\endgroup$ Commented Jun 1 at 12:56

1 Answer 1

Reset to default
8
$\begingroup$

Rephrasing for clarity: you want to know if there is a graph $G_0=(\omega,E_0)$ such that every graph on $\mathfrak c=2^{\aleph_0}$ vertices is isomorphic to an induced subgraph of the powerset graph $\operatorname{Pow}(G_0)$. That powerset graph has vertex set $\mathcal P(\omega)$, and two vertices $X,Y\subseteq\omega$ are adjacent iff $\{a,b\}\in E_0$ for some $a\in X\setminus Y$ and some $b\in Y\setminus X$. We prove the negative answer by showing that any induced subgraph $\operatorname{Pow}(G_0)[\mathcal S]$ has a special property: for any uncountable set of nonisolated vertices, some vertex has uncountably many neighbors in that set.

For $a,b\in\omega$ let $\mathcal E_{a,b}=\{X\subseteq\omega:a\in X,\,b\notin X\}$.

Consider a set $\mathcal S\subseteq\mathcal P(\omega)$ and suppose $\mathcal S_0\subseteq\mathcal S$ is an uncountable set of nonisolated vertices in $\operatorname{Pow}(G_0)[\mathcal S]$. For each $X\in\mathcal S_0$ choose $a_X,b_X\in\omega$ so that $\{a,b\}\in E_0$, $a\in X$, $b\notin X$, and $\mathcal S\cap\mathcal E_{b,a}\ne\varnothing$. Since $\mathcal S_0$ is uncountable, there exist $a,b\in\omega$ and an uncountable set $S_1\subseteq S_0$ such that $a_X=a$ and $b_X=b$ for all $X\in\mathcal S_1$. Choose $Y\in\mathcal S\cap\mathcal E_{b,a}$; then every member of $\mathcal S_1$ is adjacent to $Y$.

P.S. Maybe I misinterpreted the definition of the graph on $\mathcal P(\omega)$. In a comment the OP seems to say that $S,T\in\mathcal P(\omega)$ are adjacent iff "both $e\cap S$ and $e\cap T$ are non-empty" for some $e\in E_0$; thus $\{X\in\mathcal P(\omega):X\cap e\ne\varnothing\}$ is a clique for $e\in E_0$. In that case, if the subgraph induced by $\mathcal S$ is a tree, then $\mathcal S$ must be countable; but there are only $\mathfrak c$ countable subsets of $\mathcal P(\omega)$ while there are $2^\mathfrak c$ nonisomorphic trees on $\mathfrak c$ vertices.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.