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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .