4
$\begingroup$

For every set $X$, let $[X]^2=\{\{x,y\}: x\neq y\in X\}$.

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$. Note that, thanks to @Wojowu's comment below, the following holds. If $f, g\in \omega^\omega$ have the property that $g\circ f$ has a fixed point, then so does $f\circ g$. So, let $$E = \bigl\{\{f,g\}\in[\omega^\omega]^2: \exists n\in\omega\bigl((g\circ f)(n)=n\bigr)\bigr\}.$$ Then $(\omega^\omega,E)$ is a simple, undirected graph.

Is every finite simple, undirected graph isomorphic to some induced subgraph of $(\omega^\omega,E)$? What if we consider graphs with countable vertex set?

$\endgroup$
5
  • 3
    $\begingroup$ No, since the graph is symmetric: if $(f,g)\in E$, then $(g,f)\in E$. Indeed, if $n$ is a fixed point of $g\circ f$, then $f(n)$ is a fixed point of $f\circ g$. So asymmetric digraphs cannot be induced subgraphs of your graph. $\endgroup$ – Wojowu Dec 17 '20 at 14:39
  • $\begingroup$ Thanks yes, I will remove the question $\endgroup$ – Dominic van der Zypen Dec 17 '20 at 19:10
  • $\begingroup$ Will include the remark of @wojowu in the question $\endgroup$ – Dominic van der Zypen Dec 17 '20 at 20:27
  • $\begingroup$ You forgot to update the title $\endgroup$ – Wojowu Dec 17 '20 at 21:18
  • $\begingroup$ @Wojowu, I got it. $\endgroup$ – LSpice Dec 17 '20 at 21:19
2
$\begingroup$

The answer is "yes", even for countable graphs. To see this, first observe that if $S \subseteq \omega^\omega$ consists of strictly increasing functions then $(S, E \upharpoonright [S]^2)$ is an independent set: for all $f, g \in S$ $\{f, g\} \notin E$. This is because, for any $k < \omega$, we have $f(g(k)) > g(k) > k$ so no $k$ is a fixed point of any $f$ and $g$ in $S$.

Now, fix a countable graph $G = (V_G, E_G)$. Without loss, we may assume that the vertex set of $G$ is $\omega$ (note that, if $G$ is finite we can embed the graph consisting of $G$ alongside a disjoint copy of countably many vertices none of which connect to anything else and we'll have embedded $G$ so there's no loss in assuming $G$ is infinite). More over, we can then think of $E_G \subseteq [\omega]^2$. Fix a bijection $e:\omega \to [\omega]^2$ and a countably infinite set of strictly increasing functions $A = \{f_0, f_1, ...\} \subseteq \omega^\omega$. As noted above, $(A, E \upharpoonright [A]^2)$ is an independent set.

Inductively we will define sets $(A_i)_{i < \omega}$ so that each $A_i$ is equal to $A$ with the exception of finitely many functions that have been modified in finitely many places. For $A_0$, consider whether or not $e(0) = \{i_0, j_0\} \in E_G$. If not, set $A = A_0$. If so, modify $f_{i_0}, f_{j_0}$ so that $f_{i_0}(0) = f_{j_0}(0) = 0$ and leave everything else unchanged. Note that in the latter case we now have that $\{f_{i_0}, f_{j_0}\} \in E$ and there are no other connections in the induced subgraph with domain $A_0$. Now suppose that we have defined $A_k$, which is the same as $A$ with the exception that for every $l \leq k$ if $e(l) = \{i_l, j_l\} \in E_G$ then $f_{i_l}, f_{j_l}$ have been modified so that $f_{i_l}(l) = f_{j_l} (l) = l$. Now, modify $A_{k+1}$ in the same way.

Let $A_\omega$ be the limit of the process in the sense that $A_\omega = \{f^\omega_0, ...\} \subseteq \omega^\omega$ so that for each $n$ and each $k$, if $n \in e(k) \in E_G$ then $f^\omega_n(k) = k$ and otherwise $f^\omega_n(k) = f_n(k)$. I claim that $(A_\omega, E \upharpoonright [A_\omega]^2)$ is isomorphic to $G$ as an induced subgraph of $(\omega^\omega, E)$ (via the mapping $i \mapsto f^\omega_i$). To see this, first note that for each $k < \omega$ if $e(k) = \{i, j\} \in E_G$ then, at stage $k$ we ensured that $f^\omega_i (k) = f^\omega_j(k) = k$ so $f^\omega_i(f^\omega_j(k)) = k$ is a fixed point and hence $\{f^\omega_i, f^\omega_j\} \in E$. Now if for some $k < \omega$ we have $e(k) = \{i, j\} \notin E$ then, by construction the set of fixed points of $f_i^\omega$ and $f^\omega_j$ are disjoint. Thus, for every $n$, at least one of $f_i^\omega(n)$ and $f_j^\omega(n)$ is strictly greater than $n$, say $f_i^\omega(n)$ (the other case is symmetric). Moreover both functions are non decreasing (since we modified strictly increasing functions by adding fixed points) so we have $f^\omega_j(f^\omega_i(n)) \geq f_i^\omega(n) > n$ so $\{f^\omega_i, f^\omega_j\} \notin E$, completing the proof.

As an aside let me say I really like this problem and I wonder when (or if always?) an uncountable graph of size at most continuum is isomorphic to an induced subgraph of $(\omega^\omega, E)$?

$\endgroup$
1
  • $\begingroup$ Beautiful answer - thanks Corey, and interesting follow-up question! $\endgroup$ – Dominic van der Zypen Dec 18 '20 at 3:49

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.