# Does the following object have such property?

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 '18 at 18:03
• I suspect you want $k$ to be a fixed constant, rather than "there exists $k$". – darij grinberg Jun 30 '18 at 18:21
• @SteveKass: $\Omega = A_n$ (the alternating group) and $k \leq n-2$ always works. – darij grinberg Jun 30 '18 at 18:23

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 '18 at 5:24