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:

  1. 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).
  2. 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.

  • $\begingroup$ What do you mean by the notation $(a/b)$? $\endgroup$ – Pat Devlin Dec 5 '16 at 5:26
  • $\begingroup$ $(a/b)$ is a transposition of a and b. $\endgroup$ – IvanKuckir Dec 5 '16 at 9:06

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.