Let $G$ be a simple graph. A set $S\subset V(G)$ is said to be determining set of $G$, if for any two Automorphisms $f,g \in Aut(G)$ whenever $f(s)=g(s)$ for all $s\in S$, then $f=g$. That is, an automorphism can be determined by its images in $S$.

If $G$ is an infinite graph and $Aut(G)$ is infinite. Can $G$ have a finite determining set. If possible find a counterexample?


First, let's look at the infinite graph $G$ such that $V(G)=\mathbb{N}$, $E(G)=\{(n,n+1)|n\in \mathbb{N}\}$.
It's clear that $G$ does not have any non-trivial automorphisms.
Now we can take infinitely many copies of this graph, namely the graph $G=(V^{'},E^{'})$ with $V^{'}=\mathbb{N}\times \mathbb{N},E=\{((i,j), (i,j+1)|i,j\in\mathbb{N}\}$.
As we don't have non-trivial automorphisms inside any connectivity component, we have that the automorphisms are exactly permutations that permute the connectivity classes while keeping them intact, and so $\text{Aut}(G)\cong S_{\mathbb{N}}$ where $S_X$ is the group of all permutations on $X$.

But, it doesn't seem like it helps much, as we just said that the automorphisms are just like permutations of $\mathbb{N}$, we can't reconstruct a permutation by the images of any finite set.

So, let's add the vertices $V^{''}=\{v_{\sigma} |\sigma\in S_{\mathbb{N}}\}$ and $E^{''}=\{(v_{\sigma}, (i,j)) |v_\sigma\in V^{''}, j\le\sigma^{-1}(i) \}$.
Basically, what we do here is add a new vertex to correspond to each permutation on $\mathbb{N}$, and for each such vertex we order the connectivty components (by $\sigma(1),\sigma(2),...$) and connected this vertex to the $i$'th components with $i$ links, where the links go to the "first" vertices in the connectivity class.

Now we have a problem, as we made the graph way more complex, and we may have just introducted many more automorphisms, so we need to fix that.

Intoduce the (last) $V^{'''},E^{'''}$ such that $V^{'''}=\{u,u^{'}\}, E^{'''}=\{(u,u^{'})\}\cup\{(u,v)|v\in V^{''}\}$. So we created a new vertex and connected it to all of the $v_\sigma$'s and then yet a new vertex to connect to that vertex.

Finally, define $G=(V,E)$ where $V=V^{'}\cup V^{''} \cup V^{'''}, E=E^{'}\cup E^{''} \cup E^{'''}$.

Now, let $\psi$ be an automorphism of $G$. as $u^{'}$ is the only vertex of degree $1$, $\psi(u^{'})=u^{'}$, and thus also $\psi(u)=u$.
As $N(u)=V^{''}$, $\psi[N(\psi(u)]=V^{''}\rightarrow\psi[V^{''}]=V^{''}$ and we got that $$w\in V^{''}\leftrightarrow \psi(w)\in V^{''},w\in V^{'} \leftrightarrow \psi(w)\in V^{'}$$

Now it should be easy to see that $\psi$ again permutes connectivity classes - indeed, if $\psi(i,1)=(i^{'},j)$ such that $j > 1$ , then $\psi(i,1)$ has $2$ neightbors in $V^{'}$ but from the property we have established, it means $(i,1)$ has $2$ neightbors in $V^{'}$ which is not true, so $\psi(i,1)=\psi(i^{'},1)$ for some $i^{'}\in \mathbb{N}$ and it easily follows by induction that $\psi(i,j)=\psi(i^{'},j^{'})\rightarrow j=j^{'}$.

So we got that every automorphism permutes connectivity classes, so if we will look at the automorphisms reduced to the domain $V^{'}$, we will get a group that is $\cong S_\mathbb{N}$, as we have mentioned at the start.

Let $\sigma \in S_\mathbb{N}$, and $\psi$ the corresponding automorphism, and let's see how it can be extended to an automorphism on $G$.

As the number of links from $v_\phi \in V^{''}$ to $G_i$ (where $G_i$ is the subgraph of $(V^{'},E^{'})$ by taking only the vertices $\{(i,j)|j\in \mathbb{N} \}$) must be the same as the number of links between $\psi(v_\phi)$ and $G_{\sigma(i)}$ we are left no choice but to set $\psi(v_\phi)=v_{\sigma \circ \phi}$.

We got that again $\text{Aut}(G)\cong S_\mathbb{N}$, and notice that the automorphism matching to $\sigma \in S_\mathbb{N}$, $\psi$, maps $v_{id}$ to $v_\sigma$. That is, every automorphism of $G$, can be represneted uniquely by a $\sigma \in S_\mathbb{N}$, and the vertex $v_{id} \in V^{''} \subset V$ has the unique image $v_\sigma$.
So, by the definition of determining sets, $S=\{v_{id}\}$ is a determining set of $G$. $$\square$$

The argument below works for every vertex $v_\sigma \in V^{''}$, so we actually got infinitely many determining sets of size $1$.

| cite | improve this answer | |

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.