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](https://mathoverflow.net/questions/379134/does-any-finite-directed-graph-embed-into-the-fixed-point-graph#comment962346_379134) 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?



Does every finite simple graph embed into the "fixed point graph"?
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)$?


