Sign up ×

Let $G$ be a finite group acting on a finite set $\Omega$. A general question is to determine the sequence $o_k(\Omega)$, where $o_k(\Omega)$ is the number of orbits on $G$ for the natural action of $G$ on the set of $k$-subsets of $\Omega$. It's well-known that if $G=S_n$ and the action on $\Omega =[n] := \{1, \ldots, n \}$ is the standard permutation action, that $o_k(\Omega) = 1$ (i.e. since $S_n$ is $n$-fold transitive the induced action on $k$-sets is transitive). I'm interested in being able to figure out the sequence $o_k(\Omega_r)$ where $G=S_n$, but where $\Omega$ is the set of all $r$-subsets of $[n]$, say for $r=2$ or $3$. I had hesitated asking this question since I thought that the answer must be well-known, but after a little while looking around I haven't been able to find it.

What I have been able to figure out is the following: if $A$ is a set of $r$-subsets of $[n]$ I'll define its signature: Let $U$ denote the multiset which is the multiset union of the elements of $A$ -- i.e. the multiplicity of an element $x \in U$ is the number of elements of $A$ which contain $x$. The signature of $A$ is the multiset of multiplicities in $U$. Then the action of $S_n$ is transitive on sets of a fixed signature. So the answer to my question is to count the number of possible signatures.

[Addition: if $s$ is the signature of a set $A$ of $k$-subsets of the set of $r$-subsets of $[n]$, then the sum of the elements (with multiplicity) of $s$ is $r k$. Thus a signature is a partition of of $rk$ into $\le n$ parts. However, it's not clear to me that all such partitions actually occur as signatures]

share|cite|improve this question
Are you sure about the transitivity of $S_n$ on the sets of fixed signature? For $r=2$ - using the shortcut $ab$ for the set $\{a, b\}$ - the two sets $A = \{12, 23, 13, 45, 56, 46\}$ and $B = \{12, 23, 34, 45, 56, 16\}$ have the same signature, but I doubt that they are both in the same orbit of $S_n$. I'd expect $\omega_k(\Omega_2)$ to be the number of isomorphic classes of (unordered) graphs with $k$ edges on $n$ vertexes. – Someone Jul 20 '11 at 14:38
I'll have to think about this. I had thought that I could use the $n$-transitivity of $S_n$ to move all of the elements with the same multiplicity to each other. – Victor Miller Jul 20 '11 at 15:10

1 Answer 1

up vote 4 down vote accepted

For $r=2$ a $k$-subset can be thought of as a graph with vertices $[n]$ and $k$ edges. Hence the number of orbits is equal to the number of isomorphism classes of graphs on $n$ vertices and $k$ edges. Counting them seems like a fairly intractable problem.

share|cite|improve this answer
Torsten, Thanks. You are right. I found this link – Victor Miller Jul 20 '11 at 16:19
Counting them exactly is quite hard, but asymptotics are easy, since a general graph has trivial automorphism group. – Igor Rivin Jul 20 '11 at 17:21

Your Answer


