7
$\begingroup$

Given integers $d<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.

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.

$\endgroup$
  • $\begingroup$ Why the largest $k$? $\endgroup$ – Marcus Ritt Apr 17 '18 at 0:31
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Zihan Tan Apr 17 '18 at 0:54
  • 1
    $\begingroup$ I guess for some $k= O(d/\sqrt n)^d$ or so, $k$ random permutations work with positive probability. $\endgroup$ – Neal Young Apr 17 '18 at 1:26
  • $\begingroup$ @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. $\endgroup$ – Zihan Tan Apr 17 '18 at 1:51
  • $\begingroup$ 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? $\endgroup$ – D.W. Apr 17 '18 at 6:36
7
$\begingroup$

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, $\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, 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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.