Let $S_n$ denote the set of bijections on the set $M = \{1, 2, ... , n\}$. Suppose that a set $\Omega \subset S_n$ satisfies the following condition: there is $k \leq n$ such that, for each nonempty subset $A \subset M$ with $|A| \leq k$ and each $a \in A$ there exist exactly $\frac{|\Omega|}{|A|}$ permutations $\pi \in \Omega$ for which $\min_{x \in A} \pi (x) = \pi (a)$. Is it true, that for every nonempty subset $A \subset M$ with $|A| \leq k$ and every $m \in \{1, 2, ... |A|\}$ there exist exactly $\frac{|\Omega|}{|A|}$ permutations $\pi \in \Omega$ such that $\pi (a)$ is the $m$-th largest element of $\pi (A)$?

For small $n$-s the statement seems to be true. However, I have no idea how to prove it in general.

Any help will be appreciated.

  • Do you have an example with $\Omega\subsetneq S_n$ for which your “following condition” is true with $k>2$? Certainly it’s true for $\Omega= S_n$ (for any $k$), and regardless of $\Omega$, if you consider subsets $A=\{i,j\}$ of cardinality $2$, the condition “$\sigma(i)$ is $m$th largest in $\sigma(A)$” is the same as “$\sigma(j)$ is smallest” when $m=1$ and “$\sigma(i)$ is smallest” for $m=2$. So it seems like your conjecture could only have a counterexample with $\Omega\subsetneq S_n$ and $k>2$, but I can’t easily think of a proper subset of $S_n$ with your condition ($k>2$). – Steve Kass Jun 30 at 18:03
  • I suspect you want $k$ to be a fixed constant, rather than "there exists $k$". – darij grinberg Jun 30 at 18:21
  • 5
    @SteveKass: $\Omega = A_n$ (the alternating group) and $k \leq n-2$ always works. – darij grinberg Jun 30 at 18:23
up vote 5 down vote accepted
+250

The answer is affirmative. Use induction, say, on $m$. By assumption, the statement holds for $m=1$.

Denote for $\pi \in S_n$, $A\subset[n]$, $a\in A$ by $\nu_\pi(A,a)$ the rank of $\pi(a)$ among $\pi(x), x\in A$. Then $$ N(A,a,m) = \sum_{\pi\in\Omega}\mathbf{1}_{\nu_\pi(A,a)=m} $$ is the quantity we are interested in.

If $m = |A|$, then by induction hypothesis $$ N(A,a,m) = |\Omega| - \sum_{i=1}^{m-1} N(A,a,i) = |\Omega| - \sum_{i=1}^{m-1} \frac{|\Omega|}{|A|} = \frac{|\Omega|}{|A|}. $$

Otherwise, if $2\le m<|A|$, write by induction hypothesis $$ |\Omega| = (|A|-1)\cdot\frac{|\Omega|}{|A|-1} = \sum_{b\in A\setminus \{a\}} N(A\setminus \{b\},a,m-1)\\ = \sum_{b\in A\setminus \{a\}} \sum_{\pi\in\Omega}\mathbf{1}_{\nu_\pi(A\setminus\{b\},a)=m-1} = \sum_{\pi\in\Omega}\sum_{b\in A\setminus \{a\}}\mathbf{1}_{\nu_\pi(A\setminus\{b\},a)=m-1}. $$ Note that if $\nu_\pi(A\setminus\{b\},a)=m-1$, then either $\pi(b)>\pi (a)$ and $\nu_\pi(A,a)=m-1$ or $\pi(b)<\pi(a)$ and $\nu_\pi(A,a)=m$. Therefore, using the induction hypothesis, $$ |\Omega| = \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m-1} \sum_{b\in A:\pi(b)>\pi(a) }1 + \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m } \sum_{b\in A:\pi(b)<\pi(a) }1 \\ = \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m-1} (|A|-m + 1) + \sum_{\pi \in |\Omega|} \mathbf{1}_{\nu_\pi(A,a)=m }(m-1)\\ = (|A|-m + 1) N(A,a,m-1) + (m-1) N(A,a,m)\\ = (|A|-m + 1) \frac{|\Omega|}{|A|} + (m-1) N(A,a,m). $$ Hence, $$ N(A,a,m) = \frac{|\Omega|}{|A|}, $$ as required.

  • In fact, the cases $m=|A|$ and $m<|A|$ can be combined: I had a mistake in my draft, where the induction was in $k$ and $m$, and $N(A,a,m)$ was written in terms of $N(A,a,m-1)$ and $N(A\setminus\{b\}, a,m)$, so I put this case in there. Now considering $m=|A|$ individually is no longer needed, but let it be. – zhoraster Jul 17 at 5:24

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.