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?

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

3 Answers 3

Reset to default
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.

Improve this answer
$\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$
    – Andreas Blass
    Commented Mar 10, 2012 at 22:10
  • 1
    $\begingroup$ I look forward to reading this paper. :) $\endgroup$
    – Sean Eberhard
    Commented 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.

Improve this answer
$\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$
    – Sean Eberhard
    Commented 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$
    – Geoff Robinson
    Commented 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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .