Timeline for Sparse "bijection-proof" subsets of $[\mathbb{N}]^2$
Current License: CC BY-SA 4.0
Post Revisions
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2024 at 15:32 | comment | added | Emil Jeřábek | @PietroMajer 1001's example has $|P\cap[n+1]^2|=n$, and a simple counting argument shows that any bijection-proof $P$ has $|P\cap[n+1]^2|\ge n/\sqrt2$, lest a random permutation on $[n+1]$ give a counterexample. Thus, the interesting choice is $\alpha=1/2$. | |
| Jun 10, 2024 at 11:17 | vote | accept | Dominic van der Zypen | ||
| Jun 10, 2024 at 10:35 | comment | added | Pietro Majer | You may consider more generally $$\mu_\alpha(P):=\liminf_{n\to\infty}\frac{\text{card}(P\cap[\mathbb N]^2)}{n^{2\alpha}}$$ for $\alpha>0$ | |
| Jun 10, 2024 at 10:19 | answer | added | 1001 | timeline score: 6 | |
| Jun 10, 2024 at 8:45 | comment | added | Daniel Weber | I suspect randomly choosing pairs with any nonzero probability works, so the infimum is 0, but I'm not sure how to prove this | |
| Jun 10, 2024 at 8:07 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |