Finding automorphisms is a hard problem in general, but I am studying some simple subgroups of automorphisms, which are easy to find.
I have some r-ary relation R on a finite set U (if it was a binary relation, it would be a graph, but I am considering any general relation).
Let A2 be automorphisms $(a/b)(c/d)$ consisting of exactly two disjoint transpositions, such that none of these transposition is an automorphism by itself. Let's call one transposition to be a witness of another one. There is a relation L2 on U, such that $L2(a,b)$ iff the transposition (a/b) is a part of some automorphism in A2.
I need to represent the subgroup $G$ of automorphisms generated by A2. I am making an algorithm, which gets a relation R, then gets a permutation P and has to decide, if $P \in G$.
We draw a transposition as a two-sided black arrow between two circles. A witness is a yellow line between two transpositions. I have proven two theorems:
- L2 is transitive: Let L2(u1,u2), L2(u2,u3). Then L2(u1,u3). There are three ways such automorphisms can interact (with 1, 2 or 3 common values). Composing such automorphisms multiple times gives us new automorphisms of A2 containing (u1/u3).
- If $(a/b)(c/d), (c/d)(e/f)$ are automorphisms, then $(c/d)$ is an automorphism.
The second theorem actually tells us, that each transposition can have at most one witness (otherwise a single transposition would be an automorphism, which violates the definition of A2). This means, that automorphisms of A2 can not interact as shown in a) - (u1/u3) is a second witness of (a/b), neither c) - (v1/v2) has two witnesses. They can interact only as shown in b).
L2 splits U into equivalence classes. These classes group into pairs of the same size, such that every two elements of one class have some witness transposition in another class.
To check, if $P \in G$, I first check, if P keeps each element inside its L2-equivalency class.
I thought, that composing elements of A2 creates "ladders", that there is 1-to-1 mapping F between two L2-equivalence classes ($F(u1)=v1, F(u2)=v2, F(u3)=v3$) and it will be enough to check, that $P(a)=b \implies P(F(a)) = F(b)$, i.e. that automorphisms in $G$ can shuffle the elements in any way possible, as long as each element remains in its L2-equivalency class and the same shuffling is performed on the other side of the ladder.
But what if there is $(u0/u1)(v0/v2) \in A2$, which will break the ladder structure, and then the map F makes no sense? I can not disprove it. Can you see any other useful properties, which can help me decide, if $P \in G$?
Example: $R = \{(0,2,3), (1,3,2)\}$, the automorphism is $(0/1)(2/3)$, however, the map F is not unique (you can match 0 with 2, 1 with 3, or 0 with 3 and 1 with 2). But I think, that when L2-classes are larger than 2 (taller ladder), F will be unique.
