Sufficient condition for a non-empty intersection of two graph automorphism sets

Question

I hope the title wasn't confusing because I wasn't able to summarize it without providing the details. The problem I'm trying to solve is the following:

• We are given a graph $G=(V,E)$
• We know that it contains an automorphism that maps $a \rightarrow b$ and another one that maps $c \rightarrow d$ where $a \neq b \neq c \neq d$ and $a,b,c,d \in V$.

I'm interested in finding out what sufficient conditions are there between $a$, $b$, $c$ and $d$ which implies the existence of an automorphism that simultaneously maps $a \rightarrow b$ and $c \rightarrow d$.

Or to put it in another way: if $S_1$ is the set of automorphisms that map $a \rightarrow b$ and $S_2$ is the set of automorphisms that map $c \rightarrow d$ we are asking what sufficient conditions should $a$, $b$, $c$ and $d$ satisfy so that $S_1 \cap S_2 \neq \emptyset$

My research on this problem didn't yield any results probably because it was hard to narrow down to non-generic search terms and my lack of deep understanding of graph theory. I'd appreciate any pointers to papers/books that discuss this or closely related problems.

Thank you!

Answer 1

Check out the Grohe--Neuen paper, specifically the appendix on canonization (https://arxiv.org/abs/1901.10330).

One may check that Weisfeiler--Leman produces an isomorphism-invariant coloring of the $k$-tuples of vertices. We may now ask the converse: suppose that $\chi_{\infty}((g, \ldots, g)) = \chi_{\infty}((h, \ldots, h))$. Is there an automorphism that sends $g \mapsto h$? (Here, $\chi_{\infty}$ is the stable coloring). We refer to this condition as identifying orbits.

The key idea is this. Let $\mathcal{C}$ be a class of (colored) graphs. If $k$-WL identifies every graph $G \in \mathcal{C}$, then $(k+1)$-WL identifies orbits. We may use this to compute a canonical form as follows:

• Run $(k+1)$-WL
• Pick a vertex with the smallest color class and individualize that (color that vertex on an uncolored copy of the graph).
• Run $(k+1)$-WL on the updated graph and repeat.

You could modify the canonization procedure above as follows. Take two copies of $G$: $G_{1}, G_{2}$:

• Run $(k+1)$-WL (where $k$-WL identifies $G$)
• Check whether $a$ and $b$ receive the same color, and check whether $c$ and $d$ receive the same color.
• Suppose the above check returns true. In $G_{1}$, record the colors of (individualize) $a$ and $c$. In $G_{2}$, record the colors of (individualize) $b$ and $d$.
• Now proceed with the canonization procedure as usual.

There exists an automorphism $\varphi : (a, c) \mapsto (b, d)$ iff the final coloring from the above procedure induces an isomorphism.

Note that in the worst case, you may need $\Theta(|V|)$-WL. So this is not in general an efficiently computable test. You might be able to get a better runtime by leveraging Babai's quasipolynomial canonization procedure. I have not looked closely at that to get a sense of how to adapt it to this situation, but I would imagine the changes are similar to what I described here.