Timeline for Shrinking and expanding pairs in bijections $\varphi:\mathbb{N}\to\mathbb{N}$
Current License: CC BY-SA 4.0
10 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jun 4 at 13:43 | comment | added | Dominic van der Zypen | @IlyaBogdanov Can you elaborate on your point, maybe in an additional answer? | |
Jun 4 at 13:24 | comment | added | Ilya Bogdanov | It seems that the minimal number of non-strictly shrinking (or expanding) pairs for a permutation from $S_n$ is $\Theta(n^{3/2}$, so that the numerator in the $\liminf$ can be taken to any power less than $4/3$ without changing the result, but not further. | |
Jun 3 at 17:49 | vote | accept | Dominic van der Zypen | ||
Jun 3 at 16:07 | answer | added | Saúl RM | timeline score: 7 | |
Jun 3 at 11:56 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
added 221 characters in body
|
Jun 3 at 9:12 | comment | added | Emil Jeřábek | Shrinking pairs seem more difficult to handle But as a start, for the inverse of the $\phi$ above, about $1/4$ of the pairs are shrinking. | |
Jun 3 at 9:10 | comment | added | Emil Jeřábek | Yeah, I’ve just realized the image of $\phi$ misses nontrivial powers of $2$. But that’s easy to fix: e.g., make $\phi(2^{2k})=2^{k+1}$, $\phi(2^{2k+1})=2k+1$. | |
Jun 3 at 9:08 | comment | added | HenrikRüping | @EmilJeřábek I dont think this is a bijection. What is the preimage of 4? | |
Jun 3 at 8:50 | comment | added | Emil Jeřábek | It’s quite trivial to make almost all pairs expanding: e.g., let $\phi(n)=2n$ unless $n$ is a power of $2$, in which case $\phi(n)=2\log_2n+1$. | |
Jun 3 at 8:42 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |