2
$\begingroup$

Let $C$ be some subset of all the $ \binom{n}{k}$ combinations of $k$ out of $n$ elements. What is the group of permutations $\pi: C \to C$ of the indices of the combinations mapping $C$ to itself, i.e. the automorphisms group $A$ of $C$?

For example, say $n=4$ and $k=2$ and $C=\{(0,1,1,0), (1,1,0,0), (0,1,0,1)\}$, with the combinations written as binary $n$-tuples. In this case, we can map $C$ to itself by any permutation of the indices 1, 3 and 4, and thus $A=\{(1,2,3,4), (1,2,4,3), (3,2,1,4), (3,2,4,1), (4,2,1,3), (4,2,3,1)\}$. I would like to have an algorithm that finds this without testing all $n!$ permutations on all elements of $C$.

I first thought about finding the fixed-points of the permutations, but this is obviously not sufficient (counter example: $\tilde{C}=\{(1,1,0,0), (0,0,1,1)\}$ has no fixed-points, but the automorphism group is not the whole symmetric group $S_4$).

Edit: Maybe automorphism group is not the correct term here, as $C$ is not a group, but a set. If you know a more appropriate name for the thing I'm looking for, please tell me.

$\endgroup$
5
  • $\begingroup$ It is not clear to me. You are writing automorphism group, but there is no apparent group structure on $C$ $\endgroup$
    – Mike
    May 7 '20 at 13:20
  • 1
    $\begingroup$ $C$ is not a group, but the subset of permutations will form a group. I'm not sure whether the term "automorphism group" is correct here, as the set acting on is not a group itself. $\endgroup$
    – emgoz
    May 7 '20 at 13:24
  • $\begingroup$ The notion of automorphisms of a set is usually just that of permutations of that set. If $C$ is finite, as here, that would just give a symmetric group. Clearly you have something else in mind, preserving properties of elements of $C$, but I can't put my finger on it. $\endgroup$
    – hardmath
    May 7 '20 at 21:02
  • $\begingroup$ Can I just check if I understand your question correctly? You have a set $\Omega$ of $n$ elements, and a set $C$ consisting of some $k$-subsets of $\Omega$. You want to know the subgroup $A$ of $S_\Omega$ which preserves $C$? Also, you want some kind of implemented algorithm that can run for decent values of $n$, or you want some kind of theoretical result? $\endgroup$
    – verret
    May 8 '20 at 6:10
  • $\begingroup$ @verret yes this seems to be exactly what I want. I'm interested in an algorithm or procedure that gives me $A$ (or generators of $A$) based on $C$ for larger $n$. $\endgroup$
    – emgoz
    May 8 '20 at 7:31
1
$\begingroup$

If I understood your question correctly, then there are already plenty efficient implementations of this in standard algebra software, such as GAP and magma. Here is how you would run your example in magma, which you can do at http://magma.maths.usyd.edu.au/calc/


Omega:={1,2,3,4};

C:={{2,3},{1,2},{2,4}};

G:=Sym(Omega);

X:=GSet(G,C);

S:=Stabiliser(G,X,C);

S;


And the output gives you the order of the group you are looking for, as well as the generators. (You can of course ask for me.)

$\endgroup$
10
  • $\begingroup$ Very nice, this is indeed helpful. I want however more insight on how this can be computed, i.e. some algorithm. Maybe it's more a CS question than mathematics then. Can you explain what your code does? I never used magma and I don't know what GSet does. $\endgroup$
    – emgoz
    May 8 '20 at 7:39
  • $\begingroup$ Ok, I think I got it now. $G$ is the symmetric group acting on $\Omega$ and $X$ is $G$ acting on all elements in $C$. Then we go over all elements in $X$ and throw out all of them (along with the permutations that created them) that are not in $C$. Of course, doing it like this is computationally infeasible for larger $n$, as then $X$ will be enormous. $\endgroup$
    – emgoz
    May 8 '20 at 10:44
  • $\begingroup$ No this is not it at all. G is the symmetric group on Omega, whereas X is a set containing C on which G has an induced action. (I think it may be the set of all k-subsets in this case.) Then S is the stabiliser subgroup of C in the induced action of G on X. And before you make assumptions about how this works internally and how it will behave for larger n, have you tried running it for larger examples? $\endgroup$
    – verret
    May 8 '20 at 21:54
  • $\begingroup$ Computational group theory is a quite mature field, with many great algorithms, and they seldom run in the naive way that you might think. Many of them can solve problems for permutation groups on millions of points in a routine manner. I am not an expert in the area (but there are some on this website), so I can't tell you much more, but this is definitely part of mathematics (not CS) and if you want to know what the algorithm does internally (rather than just what it's expected output is), it's probably not a one line answer. $\endgroup$
    – verret
    May 8 '20 at 21:57
  • $\begingroup$ I didn't expect a one-line answer, if it's 100 lines I'm also fine with that ;) I have tried for larger examples in magma, and for example for $n=20$ the worst case would be $k=10$ with 20 choose 10 = 184756 elements in $X$. So it doesn't scale too bad, but far from optimal. But how would I do it then algorithmically? How would I find the stabilizer subgroup? $\endgroup$
    – emgoz
    May 9 '20 at 9:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.