2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$.) $\endgroup$ – Todd Trimble Aug 23 '17 at 16:55
  • $\begingroup$ @ToddTrimble You're right, I guess I was. I'll make an edit. Thanks. $\endgroup$ – MTyson Aug 23 '17 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.