Let \(\pi ^{(1)},\dots ,\pi ^{(2r-1)}\)  be \(2r-1\)  permutations of \([m]\) . For \(i\in [m]\)  and \(J\subset \binom{[2r-1]}{r}\) , let \(\ell (i,J)\)  be the length of the longest common sub-permutation of permutations \(\pi ^{(j)}\) , \(j\in J\) , which ends at element \(i\) . Define a vector function \(f:[m]\rightarrow [m]^R\)  by
\(f(i)=\left(\ell (i,J): J\subset \binom{[2r-1]}{r}\right).\) 
Observe that \(f\)  is an injection. Indeed, for \(i\ne j\) , by the the pigeonhole principle there is a set of indices \(J\subset \binom{[2r-1]}{r}\)  such that either in all permutations with superscripts in \(J\) , \(i\)  precedes \(j\) , or in all these permutations \(j\)  precedes \(i\) . (This is the reason why we set \(R\)  to be \(\binom{2r-1}{r}\) .) In the former case, \(\ell (i,J)<\ell (j,J)\) , while in the latter one, it is the other way around.
Suppose to the contrary that for all \(i\in [m]\)  and \(J\subset \binom{[2r-1]}{r}\) , we have \(\ell (i,J)<m^{1/R}\) . But then, the number of distinct values available for function \(f\)  is less than
\(\left(m^{1/R}\right)^R=m\) , a contradiction to \(f\)  being an injection. \(\Box \)
The proof of the lower bound on \(t^{(r)}(n)\)  is based on concatenation of \(r\) -twins. Here we reveal sufficient conditions under which two \(r\) -twins can be merged into one. Let \((x^{(j)}_{1},\dots ,x^{(j)}_{s})\) , \(j=1,\dots ,r\) , and \((y^{(j)}_{1},\dots ,y^{(j)}_{t})\) , \(j=1,\dots ,r\) , be two disjoint \(r\) -twins in a permutation \(\pi \) . Their full concatenation, resulting in \(r\) -twins of length \(s+t\) , is possible if

the rightmost element of the first \(r\) -twins is to the left of the leftmost element of the second \(r\) -twins, and

for each \(1\le i\le s\)  and \(1\le i^{\prime }\le t\) ,
\( \text{either} \qquad \max _{1\le j\le r}y^{(j)}_{i^{\prime }}<\min _{1\le j\le r}x^{(j)}_{i} \qquad \text{ or } \qquad \min _{1\le j\le r}y^{(j)}_{i^{\prime }}>\max _{1\le j\le r}x^{(j)}_{i}.\) 

Example 0.4 Let \(r=2\) , \(N=30\) , and
\(\pi =(&\colorbox {cyan}{26},16,28,29,\colorbox {cyan}{10},5,\colorbox {pink}{24},\colorbox {cyan}{27},1,22,11,\colorbox {pink}{8},2,23,15,\\&19,\colorbox {pink}{25},21,20,\colorbox {RoyalBlue}{13},9,30,\colorbox {RoyalBlue}{17},\colorbox {red}{12},\colorbox {red}{18},7,\colorbox {RoyalBlue}{3},14,\colorbox {red}{4},6)\) 

be a permutation of \([30]\) . Here we marked by blue and pink the first pair of twins of length 3 (similar to \((2,1,3)\) ), and by indigo and red the second one (similar to \((2,3,1)\) ). Both above conditions hold. Indeed, all blue and pink elements are to the left of 13, the leftmost indigo or red element. Moreover, all nine required inequalities hold, e.g., for \(i=2\) , \(i^{\prime }=1\) , we have \(\min \lbrace 13,12\rbrace =12>\max \lbrace 10,8\rbrace =10\) . Thus, their concatenation forms a (bluish-reddish) pair of twins of length six, namely: \((26, 10,27,13,17,3)\)  and \((24,8,25,12,18,4)\) , both similar to \((5,2,6,3,4,1)\) .
If we only knew the first twins and were after the second ones, we could, obviously, help ourselves by searching only to the right of 25, and by eliminating from our search all elements whose values are “squeezed” between the given twins. (In our example this step excludes only 9, as 25 and 26 are already excluded.) But most importantly, the second pair of twins should be “narrow” in a sense that would guarantee the second bulleted condition above. (In our example, we chose consecutive values: \(13,12\)  and \(17,18\)  and \(3,4\) .)

To facilitate the idea mentioned in the above example, we introduce the notion of narrow twins as follows. The width of a set of integers \(A\)  is defined as \(\max A-\min A\) . For a positive integer \(w\)  we call \(r\) -twins \((x^{(1)}_1,\dots ,x^{(1)}_k),\dots ,(x^{(r)}_1,\dots ,x^{(r)}_k)\)  \(w\) -narrow if for all \(i=1,\dots ,k\) , the sets \(\lbrace x^{(j)}_i: 1\le j\le r\rbrace \)  have width at most \(w\) .
Throughout the paper we will sometimes use notation \([a,b]=\lbrace a,\dots ,b\rbrace \) .
Lower bound
The proof of the lower bound is based on that for \(r=2\)  given in [1]}. The main idea therein is to utilize Lemma REF  in a clever way.
Set
\(M=n^{(R-1)/(2R-1)}\quad \mbox{and}\quad N=n/M=n^{R/(2R-1)}.\) 
Our goal is, for a given permutation \(\pi \)  of \([n]\) , to gradually pick from it \(O(M)\) -narrow \(r\) -twins of length \(\Omega (N/M)\) , and remove them together with all “in-between” elements (plus some more), allowing concatenation of obtained pieces into one set of \(r\) -twins of length \(\Omega (N)\) . To achieve this goal, we need to iterate this procedure \(\Omega (M)\)  times, meaning that the number of discarded each time elements should not exceed \(O(N)\) . Now come the details.
Let \(A\subset \binom{[n]}{(2r-1)N}\) , \(A=\lbrace a_1<a_2\cdots <a_{(2r-1)N}\rbrace \) , and let \(\pi \)  be a permutation of \(A\) . For any \(a\in A\)  we denote by \(\pi ^{-1}(a)\)  the position of \(a\)  in \(\pi \) . E.g., if \(A=\lbrace 1,3,4,6\rbrace \)  and \(\pi =(3,1,6,4)\) , we have \(\pi ^{-1}(1)=2\) , \(\pi ^{-1}(3)=1\) , \(\pi ^{-1}(4)=4\)  and \(\pi ^{-1}(6)=3\) .
We split the set \(A\)  into \(N\)  blocks of \(2r-1\)  consecutive elements:
\(A=A_0\cup \cdots \cup A_{N-1},\quad \mbox{where}\quad A_i=\lbrace a_{i(2r-1)+1},\dots ,a_{(i+1)(2r-1)}\rbrace ,\quad i=0,\dots ,N-1.\) 
A crucial observation is that if, for some \(2\le k\le N\)  and \(1\le j_1<j_2\le 2r-1\) , there exists a sequence of distinct indices \((i_1,\dots ,i_k)\in \lbrace 0,\dots ,N-1\rbrace ^k\)  such that
\(\pi ^{-1}(a_{i_1(2r-1)+j_1})<\cdots <\pi ^{-1}(a_{i_k(2r-1)+j_1})\quad \mbox{and}\quad \pi ^{-1}(a_{i_1(2r-1)+j_2})<\cdots <\pi ^{-1}(a_{i_k(2r-1)+j_2}),\) 
then sub-permutations \((a_{i_1(2r-1)+j_1},\dots ,a_{i_k(2r-1)+j_1})\)  and \((a_{i_1(2r-1)+j_2},\dots ,a_{i_k(2r-1)+j_2})\)  of \(\pi \)  form 2-twins of length \(k\) . By the same token, if all the above is true for \(r\)  indices \(1\le j_1<j_2<\cdots < j_r\le 2r-1\) , then we obtain \(r\) -twins of length \(k\)  in \(\pi \) .
Example 0.5 Let \(A=[30]\) , \(r=3\) , \(N=6\) , and, same as before,
\(\pi =(&26,16,28,29,10,5,24,27,1,22,11,8,2,23,15,\\&19,25,21,20,13,9,30,17,12,18,7,3,14,4,6).\) 

Here \(A_0=[1,5]\) , \(A_1=[6,10]\) , \(A_2=[11,15]\) , \(A_3=[16,20]\) , \(A_4=[21,25]\)  and \(A_5=[26,30]\) .
By inspection, one can see that for \(k=3\) , \(i_1=5\) , \(i_2=3\) , \(i_3=0\) , and \(j_1=1\) , \(j_2=3\) , \(j_3=4\) , the above conditions are satisfied.
Indeed, the first element of \(A_5\)  (26 in \(\pi \) ) is to the left of the first element of \(A_3\)  (16) which, in turn, is to the left of the first element of \(A_0\)  (1), and similar order holds for the third elements of \(A_5\) , \(A_{3}\) , \(A_0\)  (28, 18, 3), as well as, for the fourth elements (29, 19, 4).
This reveals 3-twins similar to \((3,2,1)\)  and indicated by colors below:
\(\pi =(&\colorbox {cyan}{26},\colorbox {cyan}{16},\colorbox {pink}{28},\colorbox {red}{29},10,5,24,27,\colorbox {cyan}{1},22,11,8,2,23,15,\\&\colorbox {red}{19},25,21,20,13,9,30,17,12,\colorbox {pink}{18},7,\colorbox {pink}{3},14,\colorbox {red}{4},6).\) 
An equivalent but somewhat easier way to see what is going on here is to define 5 disjoint sub-permutations \(\pi ^{(j)}\)  of length 6, by including in \(\pi ^{(j)}\)  all elements of \(\pi \)  of the form \(a_{i(2r-1)+j}\)  (in the order they appear in \(\pi \) ): \(\pi ^{(1)}=(26,16,1,11,21,6)\) , \(\pi ^{(2)}=(27,22,2,17,12,7)\) , \(\dots \) , etc. Next replace them by similar permutations of \(\lbrace 0,1,2,3,4,5\rbrace \) : \((5,3,0,2,4,1)\) , \((5,4,0,3,2,1)\) , \(\dots \) , etc. Now, what we are after, are long common sub-permutations in at least three of these permutations. We found \((5,3,0)\)  as common in the 1st, 3rd, and 4th permutation, but one could have also picked \((5,3,1)\)  in the 1st, 2nd, and 4th (and there is at least one more alternative). By inspection, one may realize, however, that there are no longer common sub-permutations in at least three of these five permutations.

In the above example, we dealt with consecutive integers in \(A\) , so the width of each subset \(A_i\)  was the same (and equal to 4), but in general this may not be the case. To make sure that the \(r\) -twins generated by the above approach are \(O(M)\) -narrow, we focus only on the subsets \(A_i\)  of width at most, say, \(2M\) .
Clearly, as \(A\subset [n]\) , at least \(N/2\)  of these sets have, indeed, the width at most \(2n/N=2M\) . Let
\(I=\lbrace 0\le i\le N-1:\; A_i \text{ has width at most } 2M\rbrace .\) 
So, \(|I|\ge N/2\) . Next, define \(2r-1\)  disjoint sub-permutations \(\pi ^{(j)}\)  of \(\pi \) , \(j=1,\dots , 2r-1\) , of length \(|I|\) , by including in \(\pi ^{(j)}\)  all elements of \(\pi \)  of the form \(a_{i(2r-1)+j}\)  (in the order they appear in \(\pi \) ). To place them on a common ground, we replace each element \(a_{i(2r-1)+j}\)  by integer \(i\in I\) , obtaining a set of new permutations \(\bar{\pi }^{(j)}\) , \(j=1,\dots , 2r-1\) , of the same set \(I\) .
We apply Lemma REF  to permutations \(\bar{\pi }^{(j)}\) , \(j=1,\dots , 2r-1\) , and, as a result, find \(r\)  of them with a common sub-permutation of length at least
\(|I|^{1/R}\ge (N/2)^{1/R}=2^{-1/R} n^{1/(2R-1)}\ge 2^{-1/3}\frac{N}{M},\) 
where the latter inequality follows from \(R=\binom{2r-1}{r}\ge \binom{3}{2}=3\) .
Let \(\bar{\pi }^{(j_1)},\dots , \bar{\pi }^{(j_r)}\) , where \(1\le j_1<\cdots <j_r\le 2r-1\) , be these \(r\)  permutations and
let \(I_0\subset I\subset \lbrace 0,\dots , N-1\rbrace \)  be the set of the elements of a common sub-permutation in \(\bar{\pi }^{(j_1)},\dots , \bar{\pi }^{(j_r)}\)  of length \(k=|I_0|=\lceil 2^{-1/3}\tfrac{N}{M}\rceil \) . Upon returning to permutations \(\pi ^{(j_1)},\dots , \pi ^{(j_r)}\) , it can be seen, guided by the above example, that \(I_0\)  generates in their union, and thus in \(\pi \) , \(2M\) -narrow \(r\) -twins of length \(k\) .
It remains to incorporate the above procedure into an iteration loop and make sure that obtained \(r\) -twins can be concatenated into a long one.
Let \(\pi \)  be a permutation of \([n]\) . In the first step of the procedure, take \(A^1\)  to be the set of first \((2r-1)N\)  elements of \(\pi \)  and let \(\pi ^1\)  be the sub-permutation of \(\pi \)  consisting of the first \(|A^1|\)  elements. By the above described argument we find \(2M\) -narrow \(r\) -twins \((x_1^{(j)},\dots ,x_k^{(j)})\) , \(j=1,\dots ,r\)  of length \(k\)  in \(\pi ^1\) . We then remove from \([n]\)  the set
\(A^1\cup \bigcup _{i=1}^k[\min _{1\le j\le r} x_i^{(j)},\min _{1\le j\le r} x_i^{(j)}+2M-1].\) 
Note that this set has size at most \((2r-1)N+k(2M)\le 2rN\) .
Now, we consider the truncation of \(\pi \)  to the remaining elements and the set \(A^2\)  of its leftmost \((2r-1)N\)  elements. Repeating the above procedure mutatis mutandis, we obtain another \(2M\) -narrow \(r\) -twins \((y_1^{(1)},\dots ,y_k^{(r)})\) , which, owing to the truncation, satisfy the conditions for proper concatenation with \((x_1^{(j)},\dots ,x_k^{(j)})\) , \(j=1,\dots ,r\) , spelled out in Subsection REF . This procedure can be continued as long as there are at least \((2r-1)N\)  elements left, that is, it can be repeated at least \(n/(2rN)=M/(2r)\)  times, yielding at the conclusion \(r\) -twins in \(\pi \)  of length a least
\(\frac{M}{2r}\times k \ge \frac{M}{2r}\times 2^{-1/3}\frac{N}{M} \ge \frac{N}{3r}.\) 
section1.7plus.5§Proof of Theorem  REF

Upper bound
For the upper bound we use the first moment method. Let \(\Pi =\Pi _n\)  be a random permutation chosen uniformly from the set of all \(n!\)  permutations of \([n]\) . Let \(k\)  be a fixed positive integer and let \(X\)  be a random variable counting all \(r\) -twins of length \(k\)  in \(\Pi \) . Furthermore, for a family of \(r\)  pairwise disjoint subsets \(A_1,\dots ,A_r\)  of \([n]\) , each of length \(k\) , let \(X_{A_1,\dots ,A_r}\)  be an indicator random variable equal 1 if there are \(r\) -twins in \(\Pi \)  on positions determined by the subsets \(A_1,\dots ,A_r\) . So, \(X=\sum _{A_1,\dots ,A_r} X_{A_1,\dots ,A_r}\)  and by the linearity of expectation
\({E}X=\sum _{A_1,\dots ,A_r}{E}X_{A_1,\dots ,A_r}=\sum _{A_1,\dots ,A_r}{P}(X_{A_1,\dots ,A_r}=1).\) 
Since
\({P}(X_{A_1,\dots ,A_r}=1)=\frac{\binom{n}{k}\binom{n-k}{k}\cdots \binom{n-(r-2)k}{k}\cdot (n-(r-1)k)!\cdot 1}{n!}=\frac{1}{k!^{r-1}}\) 
and the number of unordered \(r\) -tuples \(\lbrace A_1,\dots , A_r\rbrace \)  in \([n]\)  is
\(\binom{n}{rk} \frac{(rk)!}{k!^r r!} =\frac{n!}{k!^r r!(n-rk)!},\) 
it follows that
\({E}X=\frac{n!}{k!^r r!(n-rk)!} \times \frac{1}{k!^{r-1}}=\frac{n(n-1)\dots (n-rk+1)}{r!(k!)^{2r-1}}.\) 
Using the inequality \(k!>\frac{k^k}{e^k}\)  we obtain
\({E}X<\frac{n^{rk}e^{(2r-1)k}}{r!k^{(2r-1)k}}<\left(\frac{n^re^{2r-1}}{k^{2r-1}}\right)^k.\) 
It follows that for \(k \ge 2en^{r/(2r-1)}\) ,
\({P}(X\ge 1)\le {E}X<2^{-(2r-1)k}\rightarrow 0\) 
as \(n\rightarrow \infty \) .
This completes the proof of the upper bound.

Concentration
In the proof of the lower bound we are going to use the Azuma-Hoeffding inequality for random permutations (see, e.g., Lemma 11 in [2]} or Section 3.2 in [3]}):
Theorem 0.6 
Let \(h(\pi )\)  be a function of \(n\) -permutations such that, for some constant \(c>0\) , if permutation \(\pi _2\)  is obtained from permutation \(\pi _1\)  by swapping two elements, then \(|h(\pi _1)-h(\pi _2)|\le c\) .
Then, for every \(\eta >0\) ,
\({P}(|h(\Pi _n)-{E}[h(\Pi _n)]|\ge \eta )\le 2\exp (-\eta ^2/(2c^2n)).\) 

At one point, we will need a more refined, Talagrand-type concentration inequality which follows from some more general results in [4]}. Here is a slightly simplified version from [5]} (see also [6]}).
Theorem 0.7 (Luczak and McDiarmid [5]}) 
Let \(h(\pi )\)  be a function of \(n\) -permutations which, for some positive constants \(c\)  and \(p\) , satisfies

 if \(\pi _2\)  is obtained from \(\pi _1\)  by swapping two elements, then \(|h(\pi _1)-h(\pi _2)|\le c\) ;

 for each \(\pi \)  and \(s>0\) , if \(h(\pi )=s\) , then in order to show that \(h(\pi )\ge s\) , one needs to
specify only at most \(ps\)  values \(\pi (i)\) .

Then, for every \(\varepsilon >0\) ,
\({P}(|h(\Pi )-m|\ge \varepsilon m)\le 4 \exp (-\varepsilon ^2 m/(32pc^2)),\) 
where \(m\)  is the median of \(h(\Pi )\) .

Moreover, it follows (see for example [4]}, Lemma 4.6, or [6]}, page 164) that
\(|{E}h(\Pi )-m|=O(\sqrt{m}).\) 

Lower bound
For a constant \(C\ge 1000r!\) , set
\(a=C^{1/(2r-1)}n^{(r-1)/(2r-1)},\) 
assume for convenience that \(a\)  divides \(n\) , and partition \([n]\)  into \(n/a\)  consecutive blocks of equal size, that is, set
\([n]=A_1\cup \cdots \cup A_{n/a},\) 
where \(A_1=\lbrace 1,\dots ,a\rbrace \) , \(A_2=\lbrace a+1,\dots ,2a\rbrace \) , etc.
For fixed \(1\le i,j\le n/a\) ,
let \(X=X_{ij}\)  be the number of elements from the set \(A_j\)  which \(\Pi \)  puts on the positions belonging to the set \(A_i\) . We construct an auxiliary \(n/a\times n/a\)  bipartite graph \(B\)  with vertex classes \(U=\lbrace 1,\dots ,n/a\rbrace \)  and \(V=\lbrace 1,\dots , {n/a}\rbrace \) , where \(ij\in B\)  if, and only if, \(X_{ij}\ge r\) .
Let \(M=\lbrace i_1j_1,\dots , i_mj_m\rbrace \) , \(i_1<\cdots <i_m\) , be a matching in \(B\)  of size \(|M|=m\) . For every \(ij\in M\) , let \(s^{(i)}_1,s^{(i)}_2,\dots ,s^{(i)}_r\)  be some \(r\)  elements of \(A_i\)  such that \(\Pi (s^{(i)}_1),\dots ,\Pi (s^{(i)}_r)\in A_j\) . Then, sub-permutations
\((\Pi (s^{(i_1)}_1),\dots ,\Pi (s^{(i_m)}_1)),\ (\Pi (s^{(i_1)}_2),\dots ,\Pi (s^{(i_m)}_2)),\dots ,\;(\Pi (s^{(i_1)}_r),\dots ,\Pi (s^{(i_m)}_r))\) 
form \(r\) -twins. Indeed, if, say, \(\Pi (s^{(i_1)}_1)<\Pi (s^{(i_2)}_1)\) , then \(j_1<j_2\) , and so, \(\Pi (s^{(i_1)}_t)<\Pi (s^{(i_2)}_t)\)  for each \(t=2,\dots ,r\) , as \(\Pi (s^{(i_1)}_t)\in A_{j_1}\) , while \(\Pi (s^{(i_2)}_t)\in A_{j_2}\) .
Hence, it remains to show that a.a.s. there is a matching in \(B\)  of size \(m=\Omega \left(n^{r/(2r-1)}\right)\) . To this end, we are going to use the obvious fact, coming from a greedy algorithm, that in every graph \(G\)  there is a matching of size at least
\(|E(G)|/(2\Delta (G))\) ,
where \(\Delta (G)\)  is the maximum vertex degree in \(G\) .
We apply this, actually, to a suitably chosen subgraph \(B^{\prime }\)  of \(B\) .
Let \(\nu (B)\)  be the size of a largest matching in \(B\) . Note that \(\Delta (B)\le a/r\) . Further, let \(Z_k\)  be the number of vertices of degree \(k\)  in \(B\) , \(k=0,\dots ,a/r\) , and set
\(C^{\prime }=\lceil e^2 C/r! \rceil +1.\) 
Then, for the subgraph \(B^{\prime }\)  of \(B\)  obtained by deleting all vertices of degree at least \(C^{\prime }\) , we get
\(\nu (B)\ge \nu (B^{\prime })\ge \frac{|E(B^{\prime })|}{2\Delta (B^{\prime })}\ge \frac{|E(B)|-\sum _{k=C^{\prime }}^{a/r}kZ_k}{2C^{\prime }}.\) 
Taking the expectation on both sides, we arrive at
\({E}[\nu (B)]\ge \frac{1}{2C^{\prime }}\left({E}[|E(B)|]-\sum _{k=C^{\prime }}^{a/r}k{E}Z_k\right).\) 
Quite conveniently, both expectations on the R-H-S above can be expressed in terms of the same random variable.
For each \(i\in U\cup V\) , let
\(Y_i=\sum _{j=1}^{n/a}\mathbb {I}(X_{ij}\ge r)\) 
be the degree of vertex \(i\)  in \(B\) . Since \(Y_i\) 's have the same distribution, we further use only one of them, say, \(Y=Y_1\) .
Noticing that \({E}Z_k=(2n/a){P}(Y=k)\)  and, very crudely, \({E}[|E(B)|] \ge \frac{n}{a} {P}(Y\ge 1)\)  we infer that
\({E}[\nu (B)]\ge \frac{n}{2C^{\prime }a}\left({P}(Y\ge 1)-2\sum _{k=C^{\prime }}^{a/r}k{P}(Y=k)\right).\) 
In order to estimate \({P}(Y\ge 1)\) , we need to pinpoint \({E}Y\)  first. This boils down to estimating the probability of the presence of an edge in \(B\) , that is, \({P}(X_{ij}\ge r)\) .
Fact 0.8  For every \(r\ge 2\) , we have
\({P}(X_{ij}\ge r) \sim \frac{a^{2r}}{r! n^r}.\) 

Let \(0\le s \le r-1\)  be an integer. Observe that
\({P}(X_{ij}=s)=\frac{1}{n!}\binom{n-a}{a-s}\binom{a}{s}^2 s! (a-s)!(n-a)!\sim \frac{a^{2s}}{s! n^s} \cdot \frac{\binom{n-a}{a}}{\binom{n}{a}}.\) 
Since \(\binom{m}{k} \sim \frac{m^k}{k!}\)  if \(k^2 = o(m)\) , we obtain
\(\frac{\binom{n-a}{a}}{\binom{n}{a}}\sim \left(\frac{n-a}{n}\right)^a= \left(1-\frac{a}{n}\right)^a\sim \exp (-a^2/n)\) 
and hence
\(\sum _{s=0}^{r-1} {P}(X_{ij}=s)&\sim \exp (-a^2/n) \sum _{s=0}^{r-1} \frac{a^{2s}}{s! n^s}\\&\sim \exp (-a^2/n) \left(\exp (a^2/n) - \frac{a^{2r}}{r! n^r} + o\left(\frac{a^{2r}}{n^r} \right)\right)\sim 1-\frac{a^{2r}}{r! n^r},\) 

which is equivalent to the statement of Fact REF .
By Fact REF  (with \(a\)  set in (REF )),
\({E}Y=\sum _{j=1}^{n/a}{P}(X_{1j}\ge r)\sim \frac{n}{a}\cdot \frac{a^{2r}}{r! n^r}=\frac{a^{2r-1}}{r! n^{r-1}}=\frac{C}{r!}\ge 1000.\) 
Observe that \(Y=Y(\Pi )\)  satisfies assumptions REF  and REF  in Theorem REF  with \(c=1\)  and \(p=r\) , respectively. Indeed, swapping two elements of \(\Pi \)  changes \(\mathbb {I}(X_{1j}\ge r)\)  for at most one value of \(j\) . Moreover, to exhibit the event \(Y\ge s\) , it is sufficient to reveal \(rs\)  values of \(\Pi \) . Let \(m\)  be the median of \(Y\) . Then, by Theorem REF ,
\({P}(|Y-m|\ge m/2)\le 4\exp (-m/256),\) 
so, by (REF ),
\({P}(|Y-{E}Y|\ge (2/3){E}Y)\le 4\exp (-{E}Y/300).\) 
In particular, we get
\({P}(Y=0) \le {P}(|Y-{E}Y|\ge (2/3){E}Y)\le 4\exp (-{E}Y/300)<\frac{1}{2}.\) 
Now we estimate \({P}(Y=k)\)  for \(k\in \lbrace C^{\prime },\dots ,a/r\rbrace \) . Observe that, by using inequalities \(\binom{m}{p} \le \frac{m^p}{p!}\)  and \(\tfrac{n}{n-rk}\le \exp \lbrace rk/(n-rk)\rbrace \) ,
\({P}(Y = k) \le \binom{\frac{n}{a}}{k} \binom{a}{r}^k \binom{a}{rk} \frac{(rk)! (n-rk)!}{n!}\le \frac{a^{2rk-k}e^{(rk)^2/n}}{r!^k n^{rk-k} k!}.\) 
Consequently, since \((rk)^2=O(a^2)=o(n)\) , \(k-1\ge C^{\prime }-1 \ge 2e C/r!\) , and \(a^{2r-1}=Cn^{r-1}\) ,
\(k{P}(Y = k)\le \frac{a^{2rk-k}(1+o(1))}{r!^k n^{rk-k} (k-1)!} &\le \frac{2a^{2rk-k}}{r!^k n^{rk-k} ((k-1)/e)^k}\\ &\le \frac{2a^{2r-1}}{r!n^{r-1}}\left( \frac{ea^{2r-1}}{r!(k-1) n^{r-1} } \right)^{k-1}\le \frac{4C}{r!}2^{-k}.\) 

Thus, since \(C^{\prime } \ge 5C/(r!) + 1\) , \(C\ge 1000r!\) , and \(2^{5x}\ge 32x\)  for \(x\ge 1\) ,
\(\sum _{k=C^{\prime }}^{a/r}k{P}(Y=k) \le \frac{4C}{r!}\sum _{k=C^{\prime }}^{\infty }2^{-k} = \frac{8C}{r!} 2^{-C^{\prime }}\le \frac{4C}{r!}2^{-5C/r!}\le \frac{1}{8}.\) 
Returning to (REF ), we conclude that
\({E}[\nu (B)]\ge \frac{n}{2C^{\prime }a}\left(\frac{1}{2} - 2\cdot \frac{1}{8} \right)=\frac{n^{r/(2r-1)}}{8C^{\prime }C^{1/(2r-1)}} = \Omega (n^{r/(2r-1)}).\) 
Since \(t(\Pi _n)\ge \nu (B)\) , to complete the proof of Theorem REF  it remains to show that \(h(\Pi )=\nu (B)\)  is highly concentrated about its mean.
First note that if \(\pi _2\)  is obtained from a permutation \(\pi _1\)  by swapping some two of its elements, then at most two edges of \(B\)  can be destroyed, and at most two edges can be created, so \(|h(\pi _1)-h(\pi _2)|\le 2\) .
Consequently, Theorem REF  applied with \(h(\pi )\)  and \(\eta =n^{2r/(4r-1)}\)  implies
\({P}\left(|h(\Pi _n)-{E}[h(\Pi _n)]|\ge n^{2r/(4r-1)}\right)=o(1),\) 
finishing the proof.
section1.7plus.5§Concluding Remarks
We conclude the paper with two conjectures. The first one is a natural generalization of Gawron's conjecture [10]} concerning the asymptotic order of the function \(t^{(2)}(n)\) .
Conjecture 0.9 For every \(r\geqslant 2\) , we have \(t^{(r)}(n) = \Theta (n^{r/(2r-1)})\) .

This means that we believe that every permutation contains \(r\) -twins of length \(\Omega (n^{r/(2r-1)})\) . While this statement is wide open for every \(r\geqslant 2\) , notice that, as \(r\)  tends to \(\infty \) , the difference of the exponents in the upper and lower bounds in Theorem REF  tends to 0 (since both converge to \(1/2\) ).
Throughout the paper we have kept \(r\)  fixed, that is, independent of \(n\) . However, in the next conjecture we allow \(r=r(n)\) .
We call \(r\) -twins of length \(r\)  an \(r\) -square.
The question is how large a square is contained in every permutation.
Let \(s(\pi )\)  denote the largest integer \(r\)  such that \(\pi \)  contains an \(r\) -square and let \(s(n)\)  be the minimum of \(s(\pi )\)  over all \(n\) -permutations.
Conjecture 0.10 We have \(n-(s(n))^2=o(n)\) .

In other words, we believe that every permutation is almost entirely filled by a square.
Notice that a repeated application of the Erdős-Szekeres Theorem ([11]}) implies that every \(n\) -permutation contains an \(\Omega (\sqrt{n})\) -square. Clearly, the components of this square are monotone. It is, therefore, natural to expect even larger squares with components of an arbitrary pattern.
Finally, let us mention that in [12]} we devoted a subsection to pairs of twins with forbidden patterns. For a given permutation \(\tau \)  we say that a permutation \(\pi \)  is \(\tau \) -free if no subsequence of \(\pi \)  is similar to \(\tau \) . Let \(t^{(r)}(n,\tau )\)  denote the longest length of \(\tau \) -free \(r\) -twins guaranteed in every \(n\) -permutation. It turns out that, regardless of \(r\) , the threshold \(t^{(r)}(n,\tau )=\Theta (\sqrt{n})\)  remains valid for any non-monotone pattern \(\tau \) .
