# Determining set and Automorphism group of a graph

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$$

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