<p>Here are loose lower and upper bounds. </p>

<p>Fix $d \le n$ as in the post.  Let $k^*$ denote the largest possible value of $k$ meeting the conditions in the post.  We show that $k^* = \exp(\Theta(d\log d)$) for $d\ge 3\sqrt n$, but $k^* \le 2$ for $d\le n^{1/3}$.  I suspect the latter bound can be strengthened (e.g. shown for larger $d$).</p>

<p><strong>Lemma 1.</strong> $d!/{n\choose d} \le k^* \le d!$</p>

<p><em>Proof.</em> The upper bound $k^*\le d!$ holds simply because each chosen permutation induces a distinct permutation on the $d$-subset $\{1,\ldots,d\}$.  For the lower bound, say that two permutations of $[n]$ <em>conflict</em> if, for some $d$-subset $T$ of $[n]$, they induce the same relative order on $T$.  A given permutation $\sigma$ induces a relative order on $n\choose d$ such $d$-subsets.  Each $d$-subset $T$ and relative order on $T$ is induced by $n!/d!$ permutations of $[n]$.  It follows that any given permutation $\sigma$ conflicts with at most $c = {n\choose d} \times n!/d!$ other permutations.  So, any maximal set of pairwise non-conflicting permutations must have size at least $n! / c = d!/{n\choose d}$.  $\diamond$</p>

<p><strong>Corollary 1.</strong> <em>If $d\ge 3\sqrt n$, then $k^* = \exp(\Theta(d\log d))$.</em></p>

<p><em>Proof.</em> By Lemma 1 and calculation from Stirling's approximation,
$$k^* \ge d!/{n\choose d} = \frac{d^{2d+1}\exp(d^2/2n - 2d+O(1))}{n^d} = \exp(\Omega(d\log d))$$ for $d\ge 3\sqrt n$. 
For the upper bound, note $k^*\le d!= \exp(O(d\log d))$.  $~~~~\diamond$</p>

<p><strong>Lemma 2.</strong> <em>If $2\le d\le n^{1/3}$, then $k^* = 2$.</em></p>

<p>We give two proofs.</p>

<p><em><strong>Proof 1.</strong></em>
Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse.<br>
To finish we show $k^*\le 2$. </p>

<p>Fix any three permutations $\sigma_1, \sigma_2, \sigma_3$. Assume WLOG that $\sigma_1$ is the identity permutation: $\sigma_1(k) = k$ for $k\in [n]$. We show that some $d$-subset of $[n]$ is not distinguishable by some pair of the three permutations.</p>

<p>If $\sigma_2$ has an increasing subsequence of length $d$, then that subsequence induces the same permutation on its $d$-subset $T$ that $\sigma_1$ does, so $T$ is indistinguishable by $\sigma_1$ and $\sigma_2$, and we are done.</p>

<p>Otherwise, by the <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem" rel="nofollow noreferrer">Erdős–Szekeres Theorem</a>, $\sigma_2$ has a decreasing subsequence of length $n/d \ge d^2$ on some subset, say $T'$, of $[n]$. On $T'$, $\sigma_1$ is increasing and $\sigma_2$ is decreasing.  </p>

<p>Applying the theorem to $\sigma_3$ restricted to $T'$, $\sigma_3$ has either an increasing subsequence of length $\sqrt{d^2} = d$ on some $d$-subset $T''$ within $T'$, or a decreasing subsequence of that length on some $d$-subset $T''$ within $T'$.  In the first case, $\sigma_1$ and $\sigma_3$ don't distinguish $T''$.  In the second case, $\sigma_2$ and $\sigma_3$ don't distinguish $T''$.$~~\diamond$</p>

<p>Here's an alternate proof of Lemma 2, by adapting the proof of the <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem" rel="nofollow noreferrer">Erdős–Szekeres Theorem</a>, for those who are interested in the details.</p>

<p><em><strong>Proof 2.</strong></em> Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse.  To finish we show $k^*\le 2$. </p>

<p>Fix any three permutations $\sigma_1, \sigma_2, \sigma_3$. Assume WLOG that $\sigma_1$ is the identity permutation: $\sigma_1(k) = k$ for $k\in [n]$. Assume for contradiction that every $d$-subset $T$ of $[n]$ is distinguishable by each pair of these three permutations. </p>

<p>For each pair $i, j$ with $1\le i &lt; j \le 3$, define $I_{ij}(k)$ to be the maximum size of any subset $T\subseteq [k]$ that <em>contains $k$</em> such that the order imposed on $T$ by both $\sigma_i$ and $\sigma_j$ is monotonically <em>increasing</em>.  Define $D_{ij}(k)$ to be the maximum size of any subset $T\subseteq \{1,\ldots,k\}$ that contains $k$ such that the order imposed on $T$ by both $\sigma_i$ and $\sigma_j$ is monotonically <em>decreasing</em>.  Define 3-tuple 
$$s(k) = \big(I_{12}(k),\,I_{13}(k),\,D_{23}(k)\big),$$
 and $S = \{s(k) : k\in[n]\}.$</p>

<p><strong>Claim 1.</strong> <em>For every $k,\ell$ with $1\le k&lt;\ell \le n$, we have $s(k) \ne s(\ell)$.</em></p>

<p>Before we prove the claim, note that it implies the lemma as follows. The claim implies that $|S| = n$. Each of the three values in any 3-tuple $s(k)$ is in $[d-1]$ (because, for example, there is a subset of $[n]$ of size $I_{12}(k)$ that is not distinguishable by $\sigma_1$ and $\sigma_2$). So $S\subseteq [d-1]^3$, so $n = |S|\le(d-1)^3$, implying that $d&gt;n^{1/3}$, contradicting that $d\le n^{1/3}$ and proving the lemma.</p>

<p>To prove the claim, consider any $k,\ell\in[n]$ with $k&lt;\ell$. Consider the relative order that each of the three permutations induces on the pair $k, \ell$: for each $i\in[3]$, either $\sigma_i(k) &lt; \sigma_i(\ell)$ or $\sigma_i(k) &gt; \sigma_i(\ell)$.  Since $\sigma_1$ is the identity, $\sigma_1(k) &lt; \sigma_1(\ell)$.</p>

<p>First consider the case that $\sigma_2(k) &lt; \sigma_2(\ell)$. By definition of $I_{12}$, there is a subset $T$ of $[k]$ that contains $k$ such that $|T| = I_{12}(k)$ and $\sigma_1$ and $\sigma_2$ are monotonically increasing on $T$.  So $T' = T\cup\{\ell\}$ is a subset of $[\ell]$ that contains $\ell$ such that $|T'| = I_{12}(k)+1$ and $\sigma_1$ and $\sigma_2$ are monotonically increasing on $T'$.  It follows that $I_{12}(\ell) \ge |T'| &gt; I_{12}(k)$.  It follows that $s(\ell) \ne s(k)$ in this case.</p>

<p>For the case when $\sigma_3(k) &lt; \sigma_3(\ell)$, by the same argument $I_{13}(\ell) &gt; I_{13}(k)$, so $s(\ell)\ne s(k)$ in that case.
In the remaining case, $\sigma_2(\ell) &lt; \sigma_2(k)$ and $\sigma_3(\ell) &lt; \sigma_3(k)$.  By a similar argument $D_{23}(\ell) &gt; D_{23}(k)$.  So $s(\ell)\ne s(k)$ in all cases, proving the claim.  $\diamond$</p>

<p><strong>EDIT:</strong> <em>Comment on the tightness of the proof of Lemma 2.</em> The proof of Lemma 2 shows the existence of a $d$-subset $T$ which is indistinguishable by two of the permutations <em>and</em> that has the following stronger property: <em>the two permutations are both increasing or both decreasing</em> over $T$.  Given this, I believe the bound of $\Theta(n^{1/3})$ on $d$ is best possible.  That is, I believe that for, say, $d\ge 2n^{1/3}$, choosing appropriate random permutations w.h.p. yields $\exp(\Theta(d\log d))$ permutations such that, for every pair $\sigma$ and $\sigma^*$ of the permutations, there is no $d$-subset $T$ on which $\sigma$ and $\sigma^*$ are both increasing, or both decreasing.  (The argument is similar to the proof of Lemma 1 above, with the additional observation that, for a random permutation, w.h.p. there are only about ${n\choose d}/d!$ $d$-subsets on which the permutation is increasing or decreasing.)</p>

<p>So, to strengthen the lemma, the proof would have to somehow consider indistinguishable subsets on which the two permutations are not monotonic.</p>

CC BY-SA 3.0
2018-04-18T16:28:01.563Z
2018-04-19T22:49:16.513Z
2018-04-19T22:49:16.513Z
Neal Young
<p>Given integers $d&lt;n$, find the largest $k$ such that there exists a set of $k$ permutations $\sigma_1,\cdots,\sigma_k$ on $[n]$, such that any size-$d$ subset $T\subseteq [n]$ is ``distinguishable'' by the permutations. </p>

<p>Here we say that a set $T$ is NOT distinguishable by two permutation $\sigma,\sigma^*$ if we view both permutations as arrangements of $[n]$ into a sequence, and the restricted orders on $T\subseteq [n]$ in both arrangements are the same, otherwise it is distinguishable by $\sigma$ and $\sigma^*$. We say that a subset $T\subseteq [n]$ is distinguished by a collection of permutations if it is distinguishable by every pair of permutations in the collection.</p>

<p>Probably it is hard to express $k$ in terms of $n$ and $d$, so we shoot for asymptotic lower or upper bounds on $k$. Actually I am more interested in the case where $d$ is small (let's say $d=O(\sqrt{n})$). Any previous results or relevant ideas are appreciated. </p>

CC BY-SA 3.0
2018-04-17T00:31:00.430Z
Why the largest $k$?
Marcus Ritt
CC BY-SA 3.0
2018-04-17T00:54:32.110Z
@MarcusRitt. Because the larger k is, the harder for a set of permutations to distinguish all size-$d$ subsets (note that a set must be distinguishable by all pair of permutations). Let's say $d=2$ as a non-trivial extreme case, and without loss of generality assume one of the permutation is simply $(1,2,3,\cdots,n)$, then $k\le 2$ and we must have the other permutation being $(n,n-1,\cdots,2,1)$.
Zihan Tan
CC BY-SA 3.0
2018-04-17T01:26:58.303Z
I guess for some $k= O(d/\sqrt n)^d$ or so, $k$ random permutations work with positive probability.
Neal Young
CC BY-SA 3.0
2018-04-17T01:51:42.523Z
@NealYoung I also got a similar bound via the most natural use of probabilistic method. I am wondering if a better bound can be derived via a more clever use of probabilistic method or via some combinatorial insight.
Zihan Tan
CC BY-SA 3.0
2018-04-17T06:36:06.987Z
What does "restricted orders" mean?  Do you mean $\sigma(i) < \sigma(j)$ iff $\sigma^*(i) < \sigma^*(j)$ for all $i,j \in T$?  So $\sigma,\sigma^*$ are distinguishable if there exists $i,j \in T$ such that $\sigma(i) < \sigma(j)$ and $\sigma^*(i) > \sigma^*(j)$?  P.S. It's easy to see that $k \le d!$. Can you edit the question to show the best upper and lower bounds you know so far?
D.W.
CC BY-SA 3.0
2018-04-17T07:02:57.677Z
As far as existence, it seems plausible to me that there might exist such a set of permutations for $k$ as large as $\Theta^*(d!^2/n^d)$ or so.  (I used the probabilistic method and a heuristic approximation for the probability; the approximation might be totally bogus, though, so I don't really trust this guess.)  This looks to be approximately the same as Neal Young's estimate for  when a random set of permutations suffices.
D.W.
CC BY-SA 3.0
2018-04-17T07:31:38.343Z
"*Naturally, we say that a subset $T\subseteq [n]$ is distinguished by a collection of permutations if it is distinguishable by every pair of permutations in the collection.*" The natural interpretation for me was that a subset is distinguished by a collection of permutations if it's distinguished by *any* pair of permutations in the collection.
Peter Taylor
CC BY-SA 3.0
2018-04-17T14:08:40.000Z
@D.W. Yes, your explanation for "restricted order" is correct. It is just the most natural definition one can think of. And yes, until now all of us derived the same lower bound using same method. Until now I know of no non-trivial lower bound on $k$.
Zihan Tan
CC BY-SA 3.0
2018-04-17T14:09:47.423Z
@PeterTaylor I see, then probably I should delete the word "naturally".
Zihan Tan
CC BY-SA 3.0
2018-04-17T14:55:27.850Z
Here's a variant of the posted question. Given $n$ and $d$, what's the maximum $k$ such that there are $k$ tournament graphs $G_1, \ldots, G_k$ with common vertex set $V=\{1,2,..,n\}$ such that for every pair $G_i, G_j$, for every $d$-subset $S$ of $V$, the subgraph of $G_i$ induced by $S$ is not the same as the subgraph of $G_j$ induced by $S$?  For this problem choosing $k$ random tournaments seems to work for some $k = O(d 2^{d/2} /n)^{d/2}$.  So here the threshold (for when choosing randomly gives you anything) seems to be around $d = \Theta(\log n)$ instead of $d \approx \sqrt n$.
Neal Young
CC BY-SA 3.0
2018-04-17T15:56:07.170Z
@NealYoung Thanks for pointing out that. Yes I can roughly see why in that case $d=\Theta(\log n)$ works. Since in the similar use of the probabilistic method the probability for a "bad event" to happen becomes $2^{-\Theta(d^2)}$ instead of $2^{-O(d\log d)}$.
Zihan Tan
<co.combinatorics><permutations>
Distinguishability a set of permutations
Zihan Tan
# Distinguishability a set of permutations

(Asked by: username_0 on 2018-04-17)

Given integers $d

Here we say that a set $T$ is NOT distinguishable by two permutation $\sigma,\sigma^\*$ if we view both permutations as arrangements of $[n]$ into a sequence, and the restricted orders on $T\subseteq [n]$ in both arrangements are the same, otherwise it is distinguishable by $\sigma$ and $\sigma^\*$. We say that a subset $T\subseteq [n]$ is distinguished by a collection of permutations if it is distinguishable by every pair of permutations in the collection.

Probably it is hard to express $k$ in terms of $n$ and $d$, so we shoot for asymptotic lower or upper bounds on $k$. Actually I am more interested in the case where $d$ is small (let's say $d=O(\sqrt{n})$). Any previous results or relevant ideas are appreciated.

**Tags:** co.combinatorics, permutations
> **Comments:**
> **username_1**: Why the largest $k$?  
> **username_0**: @MarcusRitt. Because the larger k is, the harder for a set of permutations to distinguish all size-$d$ subsets (note that a set must be distinguishable by all pair of permutations). Let's say $d=2$ as a non-trivial extreme case, and without loss of generality assume one of the permutation is simply $(1,2,3,\cdots,n)$, then $k\le 2$ and we must have the other permutation being $(n,n-1,\cdots,2,1)$.  
> **username_2**: I guess for some $k= O(d/\sqrt n)^d$ or so, $k$ random permutations work with positive probability.  
> **username_0**: @NealYoung I also got a similar bound via the most natural use of probabilistic method. I am wondering if a better bound can be derived via a more clever use of probabilistic method or via some combinatorial insight.  
> **username_3**: What does "restricted orders" mean?  Do you mean $\sigma(i) < \sigma(j)$ iff $\sigma^*(i) < \sigma^*(j)$ for all $i,j \in T$?  So $\sigma,\sigma^*$ are distinguishable if there exists $i,j \in T$ such that $\sigma(i) < \sigma(j)$ and $\sigma^*(i) > \sigma^*(j)$?  P.S. It's easy to see that $k \le d!$. Can you edit the question to show the best upper and lower bounds you know so far?  
> **username_3**: As far as existence, it seems plausible to me that there might exist such a set of permutations for $k$ as large as $\Theta^*(d!^2/n^d)$ or so.  (I used the probabilistic method and a heuristic approximation for the probability; the approximation might be totally bogus, though, so I don't really trust this guess.)  This looks to be approximately the same as Neal Young's estimate for  when a random set of permutations suffices.  
> **username_4**: "*Naturally, we say that a subset $T\subseteq [n]$ is distinguished by a collection of permutations if it is distinguishable by every pair of permutations in the collection.*" The natural interpretation for me was that a subset is distinguished by a collection of permutations if it's distinguished by *any* pair of permutations in the collection.  
> **username_0**: @D.W. Yes, your explanation for "restricted order" is correct. It is just the most natural definition one can think of. And yes, until now all of us derived the same lower bound using same method. Until now I know of no non-trivial lower bound on $k$.  
> **username_0**: @PeterTaylor I see, then probably I should delete the word "naturally".  
> **username_2**: Here's a variant of the posted question. Given $n$ and $d$, what's the maximum $k$ such that there are $k$ tournament graphs $G_1, \ldots, G_k$ with common vertex set $V=\{1,2,..,n\}$ such that for every pair $G_i, G_j$, for every $d$-subset $S$ of $V$, the subgraph of $G_i$ induced by $S$ is not the same as the subgraph of $G_j$ induced by $S$?  For this problem choosing $k$ random tournaments seems to work for some $k = O(d 2^{d/2} /n)^{d/2}$.  So here the threshold (for when choosing randomly gives you anything) seems to be around $d = \Theta(\log n)$ instead of $d \approx \sqrt n$.  
> **username_0**: @NealYoung Thanks for pointing out that. Yes I can roughly see why in that case $d=\Theta(\log n)$ works. Since in the similar use of the probabilistic method the probability for a "bad event" to happen becomes $2^{-\Theta(d^2)}$ instead of $2^{-O(d\log d)}$.  

---

## 1 answers

### Answer by username_2 on 2018-04-18. Score: 6 | Accepted answer

Here are loose lower and upper bounds.

Fix $d \le n$ as in the post. Let $k^\*$ denote the largest possible value of $k$ meeting the conditions in the post. We show that $k^\* = \exp(\Theta(d\log d)$) for $d\ge 3\sqrt n$, but $k^\* \le 2$ for $d\le n^{1/3}$. I suspect the latter bound can be strengthened (e.g. shown for larger $d$).

**Lemma 1.** $d!/{n\choose d} \le k^\* \le d!$

*Proof.* The upper bound $k^\*\le d!$ holds simply because each chosen permutation induces a distinct permutation on the $d$-subset $\{1,\ldots,d\}$. For the lower bound, say that two permutations of $[n]$ *conflict* if, for some $d$-subset $T$ of $[n]$, they induce the same relative order on $T$. A given permutation $\sigma$ induces a relative order on $n\choose d$ such $d$-subsets. Each $d$-subset $T$ and relative order on $T$ is induced by $n!/d!$ permutations of $[n]$. It follows that any given permutation $\sigma$ conflicts with at most $c = {n\choose d} \times n!/d!$ other permutations. So, any maximal set of pairwise non-conflicting permutations must have size at least $n! / c = d!/{n\choose d}$. $\diamond$

**Corollary 1.** *If $d\ge 3\sqrt n$, then $k^\* = \exp(\Theta(d\log d))$.*

*Proof.* By Lemma 1 and calculation from Stirling's approximation,
$$k^\* \ge d!/{n\choose d} = \frac{d^{2d+1}\exp(d^2/2n - 2d+O(1))}{n^d} = \exp(\Omega(d\log d))$$ for $d\ge 3\sqrt n$.
For the upper bound, note $k^\*\le d!= \exp(O(d\log d))$. $~~~~\diamond$

**Lemma 2.** *If $2\le d\le n^{1/3}$, then $k^\* = 2$.*

We give two proofs.

***Proof 1.***
Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^\*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse.  
To finish we show $k^\*\le 2$.

Fix any three permutations $\sigma\_1, \sigma\_2, \sigma\_3$. Assume WLOG that $\sigma\_1$ is the identity permutation: $\sigma\_1(k) = k$ for $k\in [n]$. We show that some $d$-subset of $[n]$ is not distinguishable by some pair of the three permutations.

If $\sigma\_2$ has an increasing subsequence of length $d$, then that subsequence induces the same permutation on its $d$-subset $T$ that $\sigma\_1$ does, so $T$ is indistinguishable by $\sigma\_1$ and $\sigma\_2$, and we are done.

Otherwise, by the [Erdős–Szekeres Theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem), $\sigma\_2$ has a decreasing subsequence of length $n/d \ge d^2$ on some subset, say $T'$, of $[n]$. On $T'$, $\sigma\_1$ is increasing and $\sigma\_2$ is decreasing.

Applying the theorem to $\sigma\_3$ restricted to $T'$, $\sigma\_3$ has either an increasing subsequence of length $\sqrt{d^2} = d$ on some $d$-subset $T''$ within $T'$, or a decreasing subsequence of that length on some $d$-subset $T''$ within $T'$. In the first case, $\sigma\_1$ and $\sigma\_3$ don't distinguish $T''$. In the second case, $\sigma\_2$ and $\sigma\_3$ don't distinguish $T''$.$~~\diamond$

Here's an alternate proof of Lemma 2, by adapting the proof of the [Erdős–Szekeres Theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem), for those who are interested in the details.

***Proof 2.*** Consider any $d$ with $2\le d\le n^{1/3}$.
To see that $k^\*\ge 2$, note that (as Zihan noted in his comment) for $d\ge 2$ every $d$-subset is distinguishable by the identity permutation and its reverse. To finish we show $k^\*\le 2$.

Fix any three permutations $\sigma\_1, \sigma\_2, \sigma\_3$. Assume WLOG that $\sigma\_1$ is the identity permutation: $\sigma\_1(k) = k$ for $k\in [n]$. Assume for contradiction that every $d$-subset $T$ of $[n]$ is distinguishable by each pair of these three permutations.

For each pair $i, j$ with $1\le i < j \le 3$, define $I\_{ij}(k)$ to be the maximum size of any subset $T\subseteq [k]$ that *contains $k$* such that the order imposed on $T$ by both $\sigma\_i$ and $\sigma\_j$ is monotonically *increasing*. Define $D\_{ij}(k)$ to be the maximum size of any subset $T\subseteq \{1,\ldots,k\}$ that contains $k$ such that the order imposed on $T$ by both $\sigma\_i$ and $\sigma\_j$ is monotonically *decreasing*. Define 3-tuple
$$s(k) = \big(I\_{12}(k),\,I\_{13}(k),\,D\_{23}(k)\big),$$
and $S = \{s(k) : k\in[n]\}.$

**Claim 1.** *For every $k,\ell$ with $1\le k<\ell \le n$, we have $s(k) \ne s(\ell)$.*

Before we prove the claim, note that it implies the lemma as follows. The claim implies that $|S| = n$. Each of the three values in any 3-tuple $s(k)$ is in $[d-1]$ (because, for example, there is a subset of $[n]$ of size $I\_{12}(k)$ that is not distinguishable by $\sigma\_1$ and $\sigma\_2$). So $S\subseteq [d-1]^3$, so $n = |S|\le(d-1)^3$, implying that $d>n^{1/3}$, contradicting that $d\le n^{1/3}$ and proving the lemma.

To prove the claim, consider any $k,\ell\in[n]$ with $k<\ell$. Consider the relative order that each of the three permutations induces on the pair $k, \ell$: for each $i\in[3]$, either $\sigma\_i(k) < \sigma\_i(\ell)$ or $\sigma\_i(k) > \sigma\_i(\ell)$. Since $\sigma\_1$ is the identity, $\sigma\_1(k) < \sigma\_1(\ell)$.

First consider the case that $\sigma\_2(k) < \sigma\_2(\ell)$. By definition of $I\_{12}$, there is a subset $T$ of $[k]$ that contains $k$ such that $|T| = I\_{12}(k)$ and $\sigma\_1$ and $\sigma\_2$ are monotonically increasing on $T$. So $T' = T\cup\{\ell\}$ is a subset of $[\ell]$ that contains $\ell$ such that $|T'| = I\_{12}(k)+1$ and $\sigma\_1$ and $\sigma\_2$ are monotonically increasing on $T'$. It follows that $I\_{12}(\ell) \ge |T'| > I\_{12}(k)$. It follows that $s(\ell) \ne s(k)$ in this case.

For the case when $\sigma\_3(k) < \sigma\_3(\ell)$, by the same argument $I\_{13}(\ell) > I\_{13}(k)$, so $s(\ell)\ne s(k)$ in that case.
In the remaining case, $\sigma\_2(\ell) < \sigma\_2(k)$ and $\sigma\_3(\ell) < \sigma\_3(k)$. By a similar argument $D\_{23}(\ell) > D\_{23}(k)$. So $s(\ell)\ne s(k)$ in all cases, proving the claim. $\diamond$

**EDIT:** *Comment on the tightness of the proof of Lemma 2.* The proof of Lemma 2 shows the existence of a $d$-subset $T$ which is indistinguishable by two of the permutations *and* that has the following stronger property: *the two permutations are both increasing or both decreasing* over $T$. Given this, I believe the bound of $\Theta(n^{1/3})$ on $d$ is best possible. That is, I believe that for, say, $d\ge 2n^{1/3}$, choosing appropriate random permutations w.h.p. yields $\exp(\Theta(d\log d))$ permutations such that, for every pair $\sigma$ and $\sigma^\*$ of the permutations, there is no $d$-subset $T$ on which $\sigma$ and $\sigma^\*$ are both increasing, or both decreasing. (The argument is similar to the proof of Lemma 1 above, with the additional observation that, for a random permutation, w.h.p. there are only about ${n\choose d}/d!$ $d$-subsets on which the permutation is increasing or decreasing.)

So, to strengthen the lemma, the proof would have to somehow consider indistinguishable subsets on which the two permutations are not monotonic.


---

