Let $V$ be a set and let $V^V$ denote the set of all functions $f:V\to V$. Suppose that $F\subseteq V^V$. Let $[V]^2 = \big\{\{x,y\}: x, y\in V \land x\neq y\big\}$. We say $E\subseteq [V]^2$ is *$F$-compatible* if all members of $F$ are [graph homomorphisms](https://en.wikipedia.org/wiki/Graph_homomorphism) from $(V,E)$ to itself.


Trivially, if $F\subseteq V^V$, the empty set $E = \emptyset$ is the smallest $F$-compatible set. Is there always a largest $F$-compatible set (containing all $F$-compatible sets)?



Graph structures compatible with a collection of functions
Yes.


Each $f:V\to V$ induces a map $\bar f:V^2\to V^2$ in the natural way.


Suppose an edge $e\in [V]^2$ appears in an $F$-compatible graph $(V,E)$. Then for all $f\in F$, $\bar f(e)$ must be in $E$ as well, as must $(\bar f\circ\bar f)(e)$ and so on. The sequence $(\bar f^{\circ n}(e))\_n$ either eventually squashes down to a vertex (i.e. enters the diagonal of $V^2$) or stays in $[V]^2$. So an edge $e=(x,y)\in [V]^2$ can be in an $F$-compatible graph if and only if for every $f\in F$, $(\bar f^{\circ n}(e))\_n$ never leaves $[V]^2$. That is, iff $f^{\circ n}(x)\neq f^{\circ n}(y)$ for all $n\ge 1$. The set of all such edges forms the maximal $F$-compatible graph.


