2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 11, 2012 at 11:52
  • $\begingroup$ Comment several years later: Question 2 is the subject of something called Isbell's conjecture $\endgroup$ Oct 26, 2020 at 18:06

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 10, 2012 at 22:10
  • 1
    $\begingroup$ I look forward to reading this paper. :) $\endgroup$ Mar 10, 2012 at 22:37
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Mar 10, 2012 at 21:37
  • $\begingroup$ Yes, but I was wondering whether the two orbits condition might force primitivity, though I couldn't imeeditaely see why $\endgroup$ Mar 10, 2012 at 22:10
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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