4
$\begingroup$

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]

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Someone
    Jul 20, 2011 at 14:38
  • $\begingroup$ 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. $\endgroup$ Jul 20, 2011 at 15:10

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Torsten, Thanks. You are right. I found this link mathworld.wolfram.com/SimpleGraph.html $\endgroup$ Jul 20, 2011 at 16:19
  • 1
    $\begingroup$ Counting them exactly is quite hard, but asymptotics are easy, since a general graph has trivial automorphism group. $\endgroup$
    – Igor Rivin
    Jul 20, 2011 at 17:21

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.