The number of orbits of a permutation action - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T05:03:57Z http://mathoverflow.net/feeds/question/70813 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70813/the-number-of-orbits-of-a-permutation-action The number of orbits of a permutation action Victor Miller 2011-07-20T14:09:09Z 2011-08-03T07:20:54Z <p>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.</p> <p>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 <em>signature</em>: Let $U$ denote the <em>multiset</em> 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.</p> <p>[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]</p> http://mathoverflow.net/questions/70813/the-number-of-orbits-of-a-permutation-action/70817#70817 Answer by Torsten Ekedahl for The number of orbits of a permutation action Torsten Ekedahl 2011-07-20T14:38:12Z 2011-07-20T14:38:12Z <p>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.</p>