Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question follows up a previous question, Intersecting group orbits.

Suppose a group $G$ acts transitively on a set $X$ of $n$ elements, where $n$ is even, and consider the induced action on the set $\binom{X}{n/2}$ of subsets of $X$ of size $n/2$.

Question 1: Can there be precisely two orbits? More generally, if there is more than one orbit, how many orbits must there be?

Question 2: Suppose that no set is in the orbit of its complement. How many orbits must there be? Can there be precisely two orbits?

share|improve this question
    
If there are $k$ orbits, then the group has order at least $\binom{n}{n/2}/k$, which is $\Theta(n^{−1/2})n!$ for fixed $k$. This is a very small index in the symmetric group and I'm pretty sure all transitive subgroups of such small index are classified. At this point help from someone who knows more permutation group theory than me, but probably you just need to look at the groups in a small list. –  Brendan McKay Mar 11 '12 at 11:52

3 Answers 3

up vote 3 down vote accepted

There's a cute example with $n=6$. Start with a regular icosahedron; it has 12 vertices and 20 triangular faces. Identify antipodal points. Now you have 6 points and 10 triangles. Let $H$ be the group of those permutations of the vertices that send triangles to triangles; this $H$ has order 60. $H$ is an index-2 subgroup of a group $G$ of permutations of the six vertices such that each of the permutations in $G-H$ sends your 10 triangles to exactly the 10 3-eleemt sets of vertices that aren't among your triangles. So $G$ has exactly 2 orbits on the set of all 20 3-element sets of vertices: the 10 triangles and the 10 other 3-element sets.

It turns out that, in this situation, a 3-element set is one of the 10 triangles iff its complement isn't. So the 3-element sets in one orbit are exactly the complements of the 3-element sets in the other orbit. This is, except for a trivial example with $n=2$, the only example that does what you asked and has this additional complementation property.

As a bonus: It is well known that 6 is the only $n$ for which the symmetric group $S_n$ has outer automorphisms. Under these outer automorphisms of $S_6$, the subgroup $G$ corresponds to the stabilizer of a point.

share|improve this answer
1  
This is another piece of the planned paper that I mentioned in connection with Sean's previous question. Maybe the whole paper will gradually appear on MO this way. It's one way to get it written without my usual delays. –  Andreas Blass Mar 10 '12 at 22:10
1  
I look forward to reading this paper. :) –  Sean Eberhard Mar 10 '12 at 22:37

I am not sure whether this should be left as a a comment, but for larger $n,$ you can see just by considering how many sets of size $\frac{n}{2}$ there are, that for some constant $c(n) >1$, (which approaches $2$ as $ n \to \infty$) we must have $|G| \geq c(n)^{n-1}.$ It is rare for primitive permutation groups (other than alternating or symmetric groups) to get this large, though one probably needs to use the classification of finite simple groups to make this statement precise.

share|improve this answer
    
I did think along these lines initially. See this question: mathoverflow.net/questions/89304/…. I don't actually care about "for all sufficiently large n" statements, so I'm happy to take n even, say, in which case you have a large transitive subgroups such as $S_\frac{n}{2} \wr C_2$. –  Sean Eberhard Mar 10 '12 at 21:37
    
Yes, but I was wondering whether the two orbits condition might force primitivity, though I couldn't imeeditaely see why –  Geoff Robinson Mar 10 '12 at 22:10

In the case that $|X|=4$ or $|X|=5$ and $G$ is cyclic, one does get two orbits for the action on $\binom X2.$ Similarly for the dihedral group, even if you look at ordered (distinct) pairs. This example does not reveal much about larger $n$.

share|improve this answer

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.