# Does every finite simple graph embed into the “fixed point graph”?

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?

• 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. – Wojowu Dec 17 '20 at 14:39
• Thanks yes, I will remove the question – Dominic van der Zypen Dec 17 '20 at 19:10
• Will include the remark of @wojowu in the question – Dominic van der Zypen Dec 17 '20 at 20:27
• You forgot to update the title – Wojowu Dec 17 '20 at 21:18
• @Wojowu, I got it. – LSpice Dec 17 '20 at 21:19

## 1 Answer

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

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