Skip to main content
MathOverflow

Return to Answer

deleted 1 character in body
Source Link
Fedor Petrov
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Sorry, I do not remember the appropriate reference.

For the lower bound (for $k\geqslant 3$) we may apply the following argument, which uses much less information that is given and in particular does not depend on $k$. We have $m$ permutations, without loss of generality let the first be identical. For each $i=0,1,2,\dots,m-1$ we inductively construct a set $A_i\subset A_{i-1}\subset A_0:=\{1, \ldots, n-1\} $ such that $|A_i|\geqslant 2^{-i}(n-1)$ and the whole $A_i$ is on the same side of the element $n$ in each of permutations $\pi_1,\dots,\pi_{i+1}$. If $|A_{m-1}|>1$, we get two elements which are never separated by $n$, a contradiction. Therefore $n-1\leqslant 2^{m-1}$.

For the upper bound, choose $m$ permutations at random independently. The probability that a fixed worldword of length $k$ is never realized equals $(1-1/k!)^m$. So the total expected number of not-realized words equals $n(n-1)\dots (n-k+1)(1-1/k!)^m$. If it is less than 1, it happens with positive probability that all words are realized. This is so when $m>k\cdot k! \log n$. Applying Lovasz Local Lemma we probably should slightly improve this bound, but the coefficient is still huge.

Sorry, I do not remember the appropriate reference.

For the lower bound (for $k\geqslant 3$) we may apply the following argument, which uses much less information that is given and in particular does not depend on $k$. We have $m$ permutations, without loss of generality let the first be identical. For each $i=0,1,2,\dots,m-1$ we inductively construct a set $A_i\subset A_{i-1}\subset A_0:=\{1, \ldots, n-1\} $ such that $|A_i|\geqslant 2^{-i}(n-1)$ and the whole $A_i$ is on the same side of the element $n$ in each of permutations $\pi_1,\dots,\pi_{i+1}$. If $|A_{m-1}|>1$, we get two elements which are never separated by $n$, a contradiction. Therefore $n-1\leqslant 2^{m-1}$.

For the upper bound, choose $m$ permutations at random independently. The probability that a fixed world of length $k$ is never realized equals $(1-1/k!)^m$. So the total expected number of not-realized words equals $n(n-1)\dots (n-k+1)(1-1/k!)^m$. If it is less than 1, it happens with positive probability that all words are realized. This is so when $m>k\cdot k! \log n$. Applying Lovasz Local Lemma we probably should slightly improve this bound, but the coefficient is still huge.

Sorry, I do not remember the appropriate reference.

For the lower bound (for $k\geqslant 3$) we may apply the following argument, which uses much less information that is given and in particular does not depend on $k$. We have $m$ permutations, without loss of generality let the first be identical. For each $i=0,1,2,\dots,m-1$ we inductively construct a set $A_i\subset A_{i-1}\subset A_0:=\{1, \ldots, n-1\} $ such that $|A_i|\geqslant 2^{-i}(n-1)$ and the whole $A_i$ is on the same side of the element $n$ in each of permutations $\pi_1,\dots,\pi_{i+1}$. If $|A_{m-1}|>1$, we get two elements which are never separated by $n$, a contradiction. Therefore $n-1\leqslant 2^{m-1}$.

For the upper bound, choose $m$ permutations at random independently. The probability that a fixed word of length $k$ is never realized equals $(1-1/k!)^m$. So the total expected number of not-realized words equals $n(n-1)\dots (n-k+1)(1-1/k!)^m$. If it is less than 1, it happens with positive probability that all words are realized. This is so when $m>k\cdot k! \log n$. Applying Lovasz Local Lemma we probably should slightly improve this bound, but the coefficient is still huge.

Source Link
Fedor Petrov
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Sorry, I do not remember the appropriate reference.

For the lower bound (for $k\geqslant 3$) we may apply the following argument, which uses much less information that is given and in particular does not depend on $k$. We have $m$ permutations, without loss of generality let the first be identical. For each $i=0,1,2,\dots,m-1$ we inductively construct a set $A_i\subset A_{i-1}\subset A_0:=\{1, \ldots, n-1\} $ such that $|A_i|\geqslant 2^{-i}(n-1)$ and the whole $A_i$ is on the same side of the element $n$ in each of permutations $\pi_1,\dots,\pi_{i+1}$. If $|A_{m-1}|>1$, we get two elements which are never separated by $n$, a contradiction. Therefore $n-1\leqslant 2^{m-1}$.

For the upper bound, choose $m$ permutations at random independently. The probability that a fixed world of length $k$ is never realized equals $(1-1/k!)^m$. So the total expected number of not-realized words equals $n(n-1)\dots (n-k+1)(1-1/k!)^m$. If it is less than 1, it happens with positive probability that all words are realized. This is so when $m>k\cdot k! \log n$. Applying Lovasz Local Lemma we probably should slightly improve this bound, but the coefficient is still huge.