3
$\begingroup$

This is a variation of an older question in a more general setting.

Let $V$ denote the set of all functions $f:\omega\to \omega$. We say $f,g\in V$ share a point if there is $x\in X$ such that $f(x) = g(x)$ and set $$E = \big\{\{f,g\}: f\neq g\in V\text{ and } f,g \text{ share a point}\big\}.$$ So $G:=(V,E)$ is a simple, undirected graph on $2^\omega$ vertices.

Question. If $G' = (2^\omega, E')$ is an uncountable simple undirected graph, is it isomorphic to some induced subgraph of $G$?

$\endgroup$

2 Answers 2

5
$\begingroup$

Let H be an uncountable independent set. Let G be the graph formed by joining every vertex of some small enough graph F to every vertex of H. (So F could be a singleton, and G could be bipartite if F were independent.) Suppose we could embed G into your shared point graph. Then no two vertices in H share a point, and so the set of points that a vertex f in F shares with an h in H is disjoint from that set shared by f and a distinct point h' in H. This would imply an uncountable nontrivial partition on $\omega$. So you can't have a vertex connected to all members of an uncountable independent set in such an embedded graph.

Gerhard "Reminds Me Of Math 274" Paseman, 2018.02.22

$\endgroup$
1
  • $\begingroup$ Math 274 was a graduate level seminar on interpretability, where I started with a paper of Zamjatin, showing something like the elementary theory of rings was undecidable by embedding the theory of graphs into that theory by means of a structural interpretation. Gerhard "In Case Someone Was Wondering" Paseman, 2018.02.22. $\endgroup$ Commented Feb 22, 2018 at 22:39
5
$\begingroup$

Gerhard has pointed out that your sharing-a-point graph is not universal for uncountable graphs, since any uncountable collection of functions on $\omega$ must have many of them sharing a point. So the graph with uncountably many points and no edges is not realized as an induced subgraph of your graph.

Meanwhile, since I find it interesting, let me point out that your graph is universal for countable graphs. That is, every simple graph on countable index set is realized as an induced subgraph. The reason is that we can build a copy of the countable random graph inside your graph, and the countable random graph is universal for countable graphs.

To build the countable random graph inside your graph, we successively choose functions $f_0$, $f_1$, $f_2$ and so on, in such a way that we realize every finite connection pattern. At stage $n$, we want to choose $f_n$ so that it is connected exactly to a certain finite set of previous $f_i$ and not to the others. By induction, we may assume that the previous functions are pairwise eventually pointwise unequal. So I may place finitely points into $f_n$ so as to realize the desired connectivity, and otherwise define $f_n(k)$ with totally new values. In this way, $f_n$ realizes exactly the desired connectivity to the previous functions. By iterating this and considering all possible finite connectivity patterns, the resulting graph will fulfill the finite pattern property. Since a back-and-forth argument shows that this property in a countable graph uniquely determines the countable random graph up to isomorphism, it follows that we have found a copy of the countable random graph in your graph.

This copy of the countable random graph has the further nice property that two functions have at most one point in common and that common point is not used again by any other function. Thus, no three functions have a point in common.

$\endgroup$
1
  • 1
    $\begingroup$ Indeed, there is no uncountable independent set in Dominic's graph, and further any uncountable subgraph has uncountably many edges (doh!). Do you think you can embed the random graph in Dominic's older graph (see his linked question on endomorphisms)? Gerhard "Looks Like It Could Work" Paseman, 2018.02.22. $\endgroup$ Commented Feb 22, 2018 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .