Does every finite simple graph embed into the "fixed point graph"?

Question

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?

Answer 1

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