Is this known? As $p,q\to\infty$, most elements of the power set of $\{1,\dots,p\}\times\{1,\dots,q\}$ are in free $\Sigma_p\times\Sigma_q$-orbits

Question

Let $p,q$ be nonnegative integers. The product of symmetric groups $\Sigma_p\times\Sigma_q$ acts on the power set $P(\{1, \dots ,p\}\times\{1, \dots ,q\})$ in the evident way. You can ask what proportion of the elements of $P(\{1, \dots ,p\}\times\{1, \dots ,q\})$ live in a free $\Sigma_p\times \Sigma_q$-orbit. Write $f(p,q)$ for this proportion.

In a project that I am working on, some problem boils down to needing to know that $f(p,q)$ asymptotically approaches $1$. As $p\rightarrow\infty$, $f(p,q)$ doesn't converge to $1$. By symmetry, as $q\rightarrow\infty$, $f(p,q)$ doesn't converge to $1$. However, I claim that, if you let $p$ and $q$ both go to infinity at the same rate, then $f(p,q)$ indeed converges to $1$.

That is, as $p$ and $q$ both go to infinity, the proportion of subsets of $\{1, \dots ,p\}\times\{1, \dots ,q\}$ which are in a free $\Sigma_p\times \Sigma_q$-orbit converges to $1$. Put another way: as $p$ and $q$ both go to infinity, among the bicolored graphs with $p$ red vertices and $q$ blue vertices, the proportion which have a nontrivial automorphism goes to zero.

My question: was this claim already known to be true? Is it in the literature somewhere, where I can just cite it instead of typing up my own argument? I know very little about combinatorics, so it took me some work to prove the claim. My argument uses Pólya enumeration to count the unlabelled bicolored graphs with $p$ red vertices and $q$ blue vertices (as Harary already did in the 1950s), then a tricky and fairly meticulous estimate to put an upper bound on the number of such graphs as $p,q\rightarrow \infty$. That bound shows that there aren't too many $\Sigma_p\times \Sigma_q$-orbits in $P(\{1, \dots p\}\times \{1, \dots ,q\})$ as $p,q\rightarrow \infty$. Once you know that, you see that lots of orbits have to be as big as possible, i.e., free.

But I wonder if combinatorialists already know such things. I searched the literature but the only results I found on asymptotics of the number of unlabelled bicolored graphs were Harrison's from 1973 and Atmaca and Oruc's from 2018. The bounds I prove are stronger than the ones in those papers, so I wonder if this is something that combinatorialists haven't already done.

Hope this question isn't too naïve about combinatorics, a subject I have basically no background in. Sorry if it is. Thanks for reading.

Answer 1

We'll show that in the regime $q\ge p>(2+\delta)\log_2q$, $p,q\to\infty$, the portion of subsets of $A\times B$ with $|A|=p$, $|B|=q$ that have non-trivial automorphisms is at most $$ O(2^{-p}p^2q^2)\,. $$ With some extra care, one can improve it to $$ \left[2^{-p}\frac{q^2}2+2^{-q}\frac{p^2}2\right](1+o(1))\,, $$ i.e., to show that the lion's share of them comes just from the situation when you have two equal rows or two equal columns in the matrix. However I'll trade precision for simplicity. Note also, that this regime is essentially sharp: if $p=2\log_2 q$, then by the usual "birthday paradox" count, we have two equal columns with probability separated away from $0$.

Consider two fixed permutations $\pi\in \Sigma_p, \sigma\in\Sigma_q$ acting on $A$ and $B$ respectively. Consider their cycle decompositions and let $A=\cup_{i=1}^sA_i$, $B=\cup_{j=1}^r B_j$. If the set $S\subset A\times B$ is $\pi\times\sigma$-invariant, then in each product $A_i\times B_j$ it is enough to know a single row or a single column to recover the full intersection $S\cap(A_i\times B_j)$. Hence, we have at most $$ \prod_{i,j}2^{\min(|A_i|,|B_j|)}\le 2^{\min(pr,qs)} $$ sets with that particular automorphism ($pr$ is obtained if we estimate $\min(|A_i|,|B_j|)$ by $|A_i|$ and $qs$ if we use the bound $|B_j|$ instead.

Now, the number of permutations $\pi$ with $s$ cycles is trivially bounded by ${p\choose s}(p-s)!s^{p-s}=\frac{p!}{s!}s^{p-s}$, meaning that to build a cycle structure, we first choose the leading $s$ elements, then order the rest, and then add each of them to one of the cycles in this order. For instance, if we want $(1,4,3)(2,6)(7,5)$, we start with the set $\{1,2,7\}$, arrange the rest as $4,3,6,5$ and then add 4 and 3 to the cycle with the head 1, 6 to the cycle with the head 2, and 5 to the cycle with the head 7. Of course, we shall get the same permutation from the set $\{4,6,7\}$, the ordering 3,6,5,1 and obvious additions, so it is a rather crude overcount more often than not, but, as I said, we'll value simplicity over precision.

Thus, to bound the portion in question, we need to estimate $$ 2^{-pq}\sum'_{s,r}2^{\min(pr,qs)}\frac{p!}{s!}s^{p-s}\frac{q!}{r!}r^{q-r}\,, $$ where prime on the sum means that we exclude $(s,r)=(p,q)$ (the identity permutation).

Let $\gamma=2^{-p}p^2q^2$, which in our regime is $<\frac 12$ if $p,q$ are large enough. Note that if we increase both $r$ and $s$ by $1$ simultaneously, the corresponding term goes up by at least $\gamma^{-1}$ and if $s=p$ or $r=q$, then the same happens if you increase the other one by $1$. Thus, each term is at most $\gamma^m$ times the term corresponding to $(s,r)=(p,q)$, which (including the front $2^{-pq}$ factor is just $1$, where $m$ is the number of steps needed to reach that pair from the initial pair $(s,r)$ by these incremental steps.

Thus, we get the bound $\sum_{m\ge 1}(2m+1)\gamma^m=O(\gamma)$ as $\gamma\to 0$, as promised. The end :-).