Timeline for 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
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 22 at 0:18 | vote | accept | user509184 | ||
| May 21 at 13:33 | comment | added | fedja | P.S. I noticed a small discrepancy between your subset and graph formulations of the problem. However it doesn't matter for my solution: if you count non-isomorphic graphs only, then their total number is at least $2^{pq}/|\Gamma|$ where $\Gamma=\Sigma_p\times\Sigma_q$ while the sum I wrote bounds the number of pairs $(S,\pi)$ where $\pi$ is a non-trivial automorphism of $S$, i.e., $\sum_S(|\Gamma_S|-1)\ge\frac 12\sum_{S:|\Gamma_S|>1}|\Gamma_S|$. The number of non-isomorphic graphs with non-trivial automorphisms is $\left[\sum_{S:|\Gamma_S|>1}|\Gamma_S|\right]/|\Gamma|$, so we are still fine. | |
| May 21 at 3:35 | history | edited | LSpice | CC BY-SA 4.0 |
Fitting `\dots` in the title
|
| May 21 at 2:20 | answer | added | fedja | timeline score: 10 | |
| May 21 at 1:26 | comment | added | user509184 | @fedja Great, thanks! | |
| May 21 at 1:24 | comment | added | fedja | I think I do. I'll post it today; just give me an hour or so: I'm typing rather slowly. | |
| May 21 at 1:04 | comment | added | user509184 | @fedja By "at the same rate" I mean simply the case where $p$ and $q$ both go to infinity but where the difference $p-q$ stays constant, i.e., you repeatedly add $1$ to both $p$ and to $q$. I find it extremely believable that I am overthinking it! Do you see some simpler way to do this? | |
| May 21 at 0:36 | comment | added | fedja | If so, and if all you want is that $f(p,q)\to 1$, then, judging from your description of your proof, you are overthinking it by a wide margin. But, perhaps, you meant something else :-) | |
| May 20 at 23:48 | comment | added | fedja | When you say "at the same rate", do you mean that the ratio $p/q$ stays bounded away from both $0$ and $\infty$ or something else? | |
| May 20 at 18:14 | history | edited | Sam Hopkins |
edited tags
|
|
| May 20 at 18:10 | history | asked | user509184 | CC BY-SA 4.0 |