MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A permutation group $G \lt S_n$ is called generously transitive, if for each $i,j$ there exists a permutation that interchanges them. Is there a reasonable classification of such (finite) groups?

share|cite|improve this question
    
@oeter franek: The problem is that the parser interprets < as an HTML marker; use \lt for < and \gt for >. I've fixed the question. – Arturo Magidin Feb 28 '13 at 15:54

I believe the answer is No, there is no good classification of these things. It might be helpful for you to know that a "generously transitive permutation group" is the same as a 2-star transitive group. (See for instance the introduction to "The k-star Property for Permutation Groups" by Clough, Praeger, Schneider.) I can email you a copy of this paper if you need it.

share|cite|improve this answer

Clearly every generously transitive permutation group $G < {\rm S}_n$ acts primitively on $\{1,\dots,n\}$. Therefore we can find all generously transitive permutation groups of degree $n$ by searching through the primitive groups of degree $n$. The latter are available in the Primitive Permutation Groups Library of GAP, for all $n \leq 2500$. The following GAP function tests whether a given group is generously transitive:

IsGenerouslyTransitive := function ( G )

  local  n, i, j;

  n := LargestMovedPoint(G);
  if   not IsTransitive(G,[1..n]) or not IsPrimitive(G,[1..n])
  then return false; fi;
  if Transitivity(G,[1..n]) >= 2 then return true; fi;
  for i in [1..n] do
    for j in [i+1..n] do
      if   RepresentativeAction(G,[i,j],[j,i],OnTuples) = fail
      then return false; fi;
    od;
  od;
  return true;
end;

Now let's check how many of the primitive groups of degree $\leq 100$ are even generously transitive:

gap> List([1..100],NrPrimitiveGroups); 
[ 0, 1, 2, 2, 5, 4, 7, 7, 11, 9, 8, 6, 9, 4, 6, 22, 10, 4, 8, 4, 9, 4, 
  7, 5, 28, 7, 15, 14, 8, 4, 12, 7, 4, 2, 6, 22, 11, 4, 2, 8, 10, 4, 10, 
  4, 9, 2, 6, 4, 40, 9, 2, 3, 8, 4, 8, 9, 5, 2, 6, 9, 14, 4, 8, 74, 13, 
  7, 10, 7, 2, 2, 10, 4, 16, 4, 2, 2, 4, 6, 10, 4, 155, 10, 6, 6, 6, 2, 
  2, 2, 10, 4, 10, 2, 2, 2, 2, 2, 14, 4, 2, 38 ]
gap> Sum(last); # total number of primitive groups of degree <= 100
946
gap> List([1..100],n->Number(AllPrimitiveGroups(DegreeAction,n),
>                            IsGenerouslyTransitive));
[ 0, 1, 1, 2, 4, 4, 5, 7, 11, 9, 6, 6, 7, 4, 6, 22, 9, 4, 5, 4, 9, 4, 5, 
  5, 26, 7, 11, 14, 6, 4, 8, 7, 4, 2, 6, 21, 8, 4, 2, 8, 8, 4, 6, 4, 9, 
  2, 4, 4, 38, 9, 2, 3, 6, 4, 7, 9, 5, 2, 4, 9, 10, 4, 7, 74, 13, 7, 6, 
  7, 2, 2, 6, 4, 13, 4, 2, 2, 4, 5, 6, 4, 150, 10, 4, 6, 6, 2, 2, 2, 8, 
  4, 8, 2, 2, 2, 2, 2, 12, 4, 2, 38 ]
gap> Sum(last); # number of generously transitive groups among them
867

Hence over $90$ percent of the primitive groups of degree $\leq 100$ are even generously transitive. -- Therefore, perhaps rather than asking for a classification of generously transitive groups, one might ask for a classification of those primitive permutation groups which are not generously transitive.

share|cite|improve this answer
1  
I have edited and undeleted this answer from 2013. -- I originally deleted it about 20 minutes after posting because the code formatting looked somewhat ugly in MO 1.0, in the browser I was using. – Stefan Kohl Apr 18 at 16:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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