This is related to my previous question How to find the automorphism group of the graph mentioned in the question?.
Now the question is very tricky. It says the following:
Problem: Let $n\in \mathbb N$. Let $d_1<d_2<\dots <d_D$ be the set of all positive proper divisors of $n$. Suppose $G$ is any graph on the set of vertices $\{d_1,d_2\dots ,d_D\}$ where $d_i$ is adjacent to $d_j$ if and only if $d_i\mid d_j$ or $d_j\mid d_i$.
We now construct a new graph say $G'$ as the following:
The vertex d_1 in $G$ is replaced by $\overline{K}_{\phi(d_1)}$, the vertex $d_2$ in $G$ is replaced by $\overline{K}_{\phi(d_2)}$, the vertex $d_3$ in $G$ is replaced by $\overline{K}_{\phi(d_3)}$, and so on and then the vertex $d_D$ in $G$ is replaced by $\overline{K}_{\phi(d_D)}$.
All the vertices of $\overline{K}_{\phi(d_i)}$ are adjacent to all those vertices of $\overline{K}_{\phi(d_j)}$ for which $d_i$ is adjacent to $d_j$ in $G$.
Find automorphism group of $G'$ and its order.
My try:
I tried to find the degree of each element of $G'$. It turns out that the degree of any element $x\in \overline{K}_{\phi(d_i)}$ is
\begin{align}
\deg(x)=\sum _{\substack
{k=1\\d_k\mid d_i\; \text{or}\; d_i\mid d_k\\ k\neq i}}^w \phi(d_k).
\end{align}
Can anyone please help me how to proceed from here?
I am completely stuck after this.
Best Answer
Beware that this is not a complete answer but it contains some observations that might help. (Update: a proof is given below. Unfortunately, it's not as concise as I would have hoped.) The number of vertices of $G'$ is $n-\phi(n)$ and the vertices themselves may be identified with the elements of $\{1,2,\ldots,n\}$ that are not relatively prime to $n$. Specifically the vertices of $\overline{K}_{\phi(d_k)}$ may be identified with those elements $i$ of $\{1,2,\ldots,n\}$ satisfying $\gcd(i,n)=\frac{n}{d_k}$. Vertices identified with integers $i$ and $j$ are joined by an edge if either $\gcd(i,n)$ is a proper divisor of $\gcd(j,n)$ or $\gcd(j,n)$ is a proper divisor of $\gcd(i,n)$.
Example ($n=12$):
We have identified the vertex of $\overline{K}_{\phi(1)}$ with $12$, the vertex of $\overline{K}_{\phi(2)}$ with $6$, the vertices of $\overline{K}_{\phi(3)}$ with $4$ and $8$, the vertices of $\overline{K}_{\phi(4)}$ with $3$ and $9$, and the vertices of $\overline{K}_{\phi(6)}$ with $2$ and $10$. It is easy to see that the automorphism group for this graph is the obvious one, $S_1\times S_1\times S_2\times S_2\times S_2$, which is of order $8$. The two copies of $S_1$ act on the sets $\{12\}$ and $\{6\}$, while the three copies of $S_2$ act on the sets $\{4,8\}$, $\{3,9\}$, and $\{2,10\}$. These actions are independent.
One might think that something similar is true for every $n$, that is, that the automorphism group is $$ S_{\phi(d_1)}\times S_{\phi(d_2)}\times\ldots\times S_{\phi(d_D)}, $$ but this is not the case. One exception is when $n$ is a power of $2$, $n=2^k$, with $k\ge2$. Since $\phi(1)=\phi(2)=1$ and both the vertex of $\overline{K}_{\phi(1)}$ and the vertex of $\overline{K}_{\phi(2)}$ are joined to every other vertex, there is an additional generator that exchanges these two vertices. As examples, consider the graphs for $n=8$ and $n=16$:
In the first of these, the extra generator exchanges vertices $4$ and $8$; in the second, it exchanges $8$ and $16$.
A second exception is when $n$ is the product of two distinct primes. If $n=pq$ with $p$ and $q$ both prime, then the graph is a tree with root labeled $n$ that has $\phi(p)+\phi(q)$ children. Hence the automorphism group is $S_1\times S_{\phi(p)+\phi(q)}$. An example is $n=15=3\cdot5$:
I believe these are the only exceptions, but do not yet have a proof.
Proof sketch added later: The restriction to proper divisors doesn't seem particularly important. If we allow $n$ itself as a divisor of $n$ then $G$ becomes slightly easier to describe. It also gets more symmetry, but we will see that that doesn't materially change things. In all but one case the automorphism group of $G'$ just gets a completely predictable extra factor, $S_{\phi(n)}$. (The exception is $n=2$, where the new vertex of $G$ results in a new automorphism exchanging the two vertices, making $n=2$ similar to the higher powers of $2$.) So let's drop the restriction to proper divisors.
Let $V_d$ be the set of $\phi(d)$ vertices of $G'$ that correspond to vertex $d$ of $G$. By construction, any two vertices in $V_d$ have edges to all the same vertices. Conversely, if two vertices of $G'$ have edges to all the same vertices, then they are vertices of the same $V_d$, except in the case that $n=pq$ with $p$, $q$ prime. In that case the vertices of $V_p$ and the vertices of $V_q$ are all connected only to the vertex of $V_1$ and the vertices of $V_n$. The main case follows because if $n$ has more than two (not necessarily distinct) prime factors and if $d$ and $e$ are distinct divisors of $n$, then one of two things must happen: (1) one of $d$, $e$ has a proper divisor that the other does not have or (2) one of $d$, $e$ properly divides a factor of $n$ that the other does not.
As a consequence, except in the case where $n$ is the product of two distinct primes, any automorphism of $G'$ must map all vertices of $V_d$ to some $V_e$ and $e$ must satisfy $\phi(e)=\phi(d)$. Now if that is the case then $$ S_{\phi(d_1)}\times S_{\phi(d_2)}\times\ldots\times S_{\phi(d_D)} $$ is a normal subgroup of the automorphism group of $G'$, and we may therefore form the quotient of $G'$ by this group. The result is the automorphism group of a vertex-colored $G$, where the colors are the values $\phi(d)$. Determining whether this quotient is trivial is the main task. The divisors of $n$ form a poset in which "is divisible by" is the order relation; $G$ is a precise representation of this poset. (Be careful to note that it's not the Hasse diagram, which must be transitively reduced). As a representation of the poset, the vertices of $G$ are labeled by divisors of $n$, but we need to look at the graph obtained by replacing these labels with the values $\phi(d)$. Since $\phi$ may map different divisors to the same value, it is not immediately obvious whether the automorphism group is trivial.
To investigate this question, first recall that the Hasse diagram of our poset is a finite piece of a hypercubic lattice whose dimension is the number of distinct prime factors of $n$. To obtain $G$, all edges implied by transitivity must then be added. Without labels, $G$ has an automorphism that sends the vertex $d$ to $n/d$. (This is true because we have dropped the restriction to proper divisors so that there is now a vertex $n$ to serve as the image of vertex $1$.) This is not an automorphism of our vertex-colored $G$ unless $\phi(d)=\phi(n/d)$ for all divisors of $n$. The only $n$ for which that holds is $n=2$, which means $n=2$ now follows the pattern of the higher powers of $2$ in having an automorphism group with an extra generator.
The question remains whether the vertex colored $G$ has any nontrivial automorphisms for $n>2$, and to answer this we must look in detail at the vertex colors, that is, the values $\phi(d)$. Both the Hasse diagram and the Hasse diagram with edges implied by transitivity added can be considered to be directed graphs. If the arrows can be uniquely added to $G$ using just the vertex-color information, i.e. using just the values $\phi(d)$, then any automorphism of the vertex colored graph will also be an automorphism of the directed version, and this version may be easier to analyze. In fact, we can add the arrows in most cases. To see this, note that $\phi$ satisfies $\phi(m)\le\phi(n)$ whenever $m\mid n$ and that equality only holds when $m$ is odd and $n=2m$. Hence if an edge joins differently colored vertices, we may add an arrow pointed in the direction of the greater color. The more difficult case is when an edge joins same-colored vertices. However, as long $n$ has an odd prime factor, then the arrows can always be unambiguously placed, as the following example shows. The poset for $n=6$ is represented by the directed graph below.
Dropping the arrows and applying the function $\phi$ to the vertices gives the following graph, where blue stands for value $1$ and red for value $2$.
We may immediately restore the arrows along the three edges connecting blue to red, with the arrow in the blue-to-red direction. If we were to place the arrow on the blue-blue edge the "wrong" way, i.e. pointing to the right, then transitivity would imply the existence of an edge joining the leftmost blue vertex to the rightmost red vertex. Since there is no such edge, we are forced to place the arrow so that it points left. Similar considerations apply to the edge joining the red vertices. In larger graphs, the ambiguous edges always appear in subgraphs isomorphic to this example, and therefore the arrows may always be restored in a unique way. The only case in which the ambiguity is unresolvable is when $n$ contains no odd prime factor, i.e. when $n$ is a power of $2$.
So we've reduced the problem of finding automorphisms of the vertex colored version of $G$ to that of finding automorphisms of the corresponding vertex colored directed graph. This graph is acyclic, and therefore has a unique transitive reduction, found by locating all cycles in which all arrows but one point in the same direction, and then deleting the wrong-way arrow in each such cycle. This transitively reduced graph must therefore have the same automorphism group. But now we are just looking at automorphism groups of Hasse diagrams in which the function $\phi$ has been applied to the vertices. As mentioned previously, such Hasse diagrams are finite pieces of hypercubic lattices, shaped like rectangular prisms. The one-dimensional facets of these prisms correspond to the sequences of the different prime powers. Any automorphism must send a one-dimensional facet to another one-dimensional facet, but the labels (colors) make this impossible, since the values of $\phi$ for prime-power sequences of different primes never coincide. (Recall that $\phi(p^k)=(p-1)p^{k-1}$ for $p$ prime and $k\ge1$.) Hence the only automorphism is the trivial one.
Example: The Hasse diagram for $n=180=2^2\cdot3^2\cdot5$ is below.
The vertex colors correspond to different values of $\phi$: $\phi(1)=\phi(2)=1$ red, $\phi(3)=\phi(4)=\phi(6)=2$ orange, $\phi(5)=\phi(10)=\phi(12)=4$ yellow-green, $\phi(9)=\phi(18)=6$ green, $\phi(15)=\phi(20)=\phi(30)=8$ blue-green, $\phi(36)=12$ light blue, $\phi(60)=16$ dark blue, $\phi(45)=\phi(90)=24$ purple, $\phi(180)=48$ magenta. We want to see why the automorphism of this directed graph, with the vertex labels removed but the vertex colors retained, is trivial. There is exactly one red vertex with only outgoing arrows (vertex $1$), so any automorphism must fix this vertex. There are three vertices connected by a single arrow to vertex $1$ (vertices $2$, $3$, and $5$), but they are all colored differently (which is a consequence of the fact that they correspond to different primes), so any automorphism must fix these as well. It is now fairly easy to see that any automorphism fixes every vertex. For example vertices $4$, $9$, $6$, $10$, and $15$ are all connected to vertex $1$ by two arrows, but each in a different way: there is one path to vertex $4$, through vertex $2$, there are two paths to vertex $6$, either through vertex $2$ or vertex $3$, there are two paths to vertex $10$, either through vertex $2$ or vertex $5$, and so on. So each of these vertices must be fixed by any automorphism. Continuing along the same lines, we find that vertices connected to $1$ by three, four, or five arrows must also be fixed by any automorphism.