# Graph structures compatible with a collection of functions

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

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.
• Are you assuming graphs are finite? It seems you are, since for $V = \mathbb{N}$ and $E= \{(n, n+1): n \in V\}$, the successor function $s: \mathbb{N} \to \mathbb{N}$ has no induced cycles. (Of course the fix is obvious: an edge $(x, y)$ belongs to the maximal $F$-compatible graph iff for all $f \in F$ and all $n \in \mathbb{N}$ we have $f^n(x) \neq f^n(y)$.) – Todd Trimble Aug 23 '17 at 16:55