Skip to main content
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