Bruhat Order and Sperner Property

“Mathematics is the music of reason.”

James J. Sylvester

This week is the first week of the spring term and also my first week of undergraduate research with Prof. Satriano, so I decided to write about a research paper I’ve given to read, this one. In a nutshell, the paper proves a combinatorical conjecture posed by McKinnon, Satriano and Huang, about orbits on a hyperplane under permutation. Specifically, suppose that \(\sigma\in S_n\) acts on \(v\in\mathbf R^n\) by permutation, and let \(\mathcal{O}(v, w)=\{\sigma\in S_n: w\cdot \sigma v=0\}\). We prove a best bound for the number of vectors obtained by permutation of coordinates that are contained in a hyperplane through the origin except for \(\sum_ix_i=0\), where \(n\ge 3\). In notations, we have the following theorem.

Theorem 1. For \(n\ge 3\), we have
\[\max\{|\mathcal{O}(v,w)|: v\in S,w\in\mathbf{R}^n\}=2\lfloor n/2\rfloor (n-2)!\]where \(S=\{v\in \mathbf R^n: v\cdot \mathbf{1}\ne 0, v\mathrm{\ has\ distinct\ coordinates}\}\).

An explicit construction that achieves this bound is given by McKinnon, Satriano and Huang, so it suffice to show that this is the best bound. The proof uses Bruhat order and Sperner property.

Bruhat order

Suppose \(\alpha\vdash n\) with \(\ell(\alpha)=m\), and \(i_j=\sum_{k=1}^j\alpha_j\) for \(j=0,1\dots,m\). Let \(X_{\alpha}\) be the set of ordered set partitions of type \(\alpha\). Naturally, we have \(\alpha^*\in X_{\alpha}\) where \(\alpha^*_j=\{i_j+1,i_j+2,\dots,i_{j+1}\}\). Let \(S(\alpha)=\{i_1,\dots,i_{m-1}\}\). We have \(S_n\) acts on \(X_{\alpha}\) by element, which is a transitive action. Thus identify \(X_{\alpha}\cong S_n/S_\alpha\) where \(S_{\alpha}\) is the stabilizer of \(\alpha^*\). Denote \(\alpha!=|S_{\alpha}|=\prod_{i}\alpha_i!\)

Definition 2. The Bruhat order on \(S_n/S_\alpha\) is the transitive closure (they are connected by relations of the following kind) of \(B<(i\ j)B\) for \(B\in S_n/S_\alpha\) where \(i\in B_a\) and \(j\in B_b\) and \(a<b\) and \(i<j\).

We note that the Bruhat order on \(S_n/S_{(1,\dots,1)}\) is just the usual Bruhat order on \(S_n\). For \(B\in S_n/S_\alpha\) let \(\operatorname{word}(B)\) be the permutation by concatonating the numbers in each set written in their usual order. This sends ordered set partitions to a more common definition: \(\sigma\in S_n\) where \(\sigma(i)>\sigma(i+1)\) implies \(i\in S(\alpha)\), and Bruhat order restricted to such permutations. There is an obvious bijection \((S_n/S_\alpha)\times S_\alpha\rightarrow S_n\) by \((B,\sigma)\mapsto \operatorname{word}(B)\sigma\). The \(\alpha\)-Bruhat order \(\le_{\alpha}\) on \(S_n\) is the image of \((B,\sigma)\le (B^\prime,\sigma^\prime)\) iff \(\sigma=\sigma^\prime\) and \(B\le B^\prime\) in Bruhat order under the aforementioned bijection, which is isomorphic to \(\alpha!\) isomorphic copies of \(S_n/S_\alpha\). If \(w\in\mathbf R^n\), define \(\operatorname{comp}(w)\vdash n\) as the composition of lengths of the weekly increasing components. An antichain in a poset is a set consisting of elements from different disjoint components.

Lemma 3. Suppose \(v\in\mathbf R^n\) is stricly increasing and \(w\in\mathbf R^n\) weakly increasing, then \(\mathcal O(v,w)\) is an antichain in the \(\alpha\)-Bruhat order where \(\alpha=\operatorname{comp}(w)\).

Proof

Suppose \(\pi\in S_{\alpha}\) and \(\tau=\operatorname{word}(B)\) for some \(B\in S_n/S_\alpha\). Suppose \(i\in B_a\) and \(j\in B_b\) for \(i<j\) and \(a<b\). We have \(\tau \pi< (i\ j)\tau \pi\). Next, we compute that
\[w\cdot \tau\pi v-w\cdot (i\ j)\tau \pi v=(w_j-w_i)(v_{\pi^{-1}\tau^{-1}(j)}-v_{\pi^{-1}\tau^{-1}(i)})\]Since \(\tau^{-1}(i)\) is at a lower interval than \(\tau^{-1}(j)\) (since \(a<b\)) and \(\pi^{-1}\) preserves these intervals, we have \(v_{\pi^{-1}\tau^{-1}(j)}>v_{\pi^{-1}\tau^{-1}(i)}\). Since we have \(w_i<w_j\) by assumption, we have \(w\cdot \tau\pi v>w\cdot (i\ j)\tau \pi v\). Therefore, if \(\sigma<_{\alpha}\sigma^\prime\) then \(w\cdot \sigma v>w\cdot \sigma^\prime v\).

Therefore, we can bound the sizes of antichains in the \(\alpha\)-Bruhat order.

Sperner property

We use \(q\)-polynomials to bound the sizes of antichains. Specifically, we will make use of the Sperner property of \(S_n/S_\alpha\): it is a ranked poset where the set of elements of rank \(r\), for some fixed \(r\), forms an antichain of maximal size. The rank generating function of \(S_n/S_\alpha\) is the \(q\)-binomial coefficient \(\begin{bmatrix}n\\ \alpha\end{bmatrix}_q\).

Theorem 4. Let \(v,w\in\mathbf R^n\) where \(v\) has distinct coordinates, then
\[|\mathcal{O}(v,w)|\le \alpha!M\left(\begin{bmatrix}n\\ \alpha\end{bmatrix}_q\right)\]where \(\alpha=\operatorname{comp}(w)\) and \(M:\mathbf{Z}[q]\rightarrow\mathbf Z\) is the map that takes the maximum coefficient.

Proof

Since \(|\mathcal{O}(v,w)|=|\mathcal{O}(\sigma v,\tau w)|\) for any \(\sigma,\tau\in S^n\), we can assume \(v\) is strictly increasing and \(w\) weakly increasing. By the previous lemma, we have \(\mathcal{O}(v,w)\) is an antichain in the \(\alpha\)-Bruhat order on \(S_n\), and hence also on \(S_n/S_\alpha\times S_\alpha\). By the Sperner property, we have this bound.

Therefore, it suffice to bound the coefficients of \(\begin{bmatrix}n\\ \alpha\end{bmatrix}_q\).

Bounding coefficients

Given \(\alpha,\beta\vdash n\), then we say \(\beta\) refines \(\alpha\), written as \(\alpha\prec \beta\), if \(\beta\) is obtained from \(\alpha\) by decomposing its entries.

Lemma 5. If \(\alpha,\beta\vdash n\) and \(\alpha\prec \beta\), then \(\beta !M\left(\begin{bmatrix}n\\ \beta\end{bmatrix}_q\right)\le \alpha! M\left(\begin{bmatrix}n\\ \alpha\end{bmatrix}_q\right)\).

Proof

Assume \(\beta=(\alpha_1,\dots,\alpha_{i-1},\alpha_{i}-p,p,\alpha_{i+1},\dots,\alpha_m)\), then
\[\beta!\begin{bmatrix}n\\ \beta\end{bmatrix}_q=\binom{\alpha_i}{p}^{-1}\begin{bmatrix}\alpha_i\\ p\end{bmatrix}_q \alpha!\begin{bmatrix}n\\ \alpha\end{bmatrix}_q\]The lemma follows from \(M(fg)\le f(1)M(g)\).

Eventually, with some lengthy calculations, we have \(M\left(\begin{bmatrix}n\\ k\end{bmatrix}_q\right)\le \displaystyle\frac{1}{n}\binom{n}{k}\) for \(n\ge 0\) and \(2 < k < n-2\).

Theorem 1. For \(n\ge 3\), we have
\[\max\{|\mathcal{O}(v,w)|: v\in S,w\in\mathbf{R}^n\}=2\lfloor n/2\rfloor (n-2)!\]where \(S=\{v\in \mathbf R^n: v\cdot \mathbf{1}\ne 0, v\mathrm{\ has\ distinct\ coordinates}\}\).

Proof

If \(\operatorname{comp}(w)\) has \(1\) part then obviously \(|\mathcal{O}(v,w)|=0\). Assume \(\operatorname{comp}(w)\) has at least \(2\) parts.
\[\begin{aligned}|\mathcal{O}(v,w)|&\le \operatorname{comp}(w)!M\left(\begin{bmatrix}n\\ \operatorname{comp}(w)\end{bmatrix}_q\right)\\ &\le \operatorname{max}_{\alpha\vdash n, \ell(\alpha)\ge 2}\alpha!M\left(\begin{bmatrix}n\\ \alpha\end{bmatrix}_q\right)\\ &\le \operatorname{max}_{0<k<n}k!(n-k)!M\left(\begin{bmatrix}n\\ k\end{bmatrix}\right)
\end{aligned}\]For \(2<k<n-2\), \[k!(n-k)!M\left(\begin{bmatrix}n\\ k\end{bmatrix}\right)\le k!(n-k)!\frac{1}{n}\binom{n}{k}=(n-1)!\] We see that if \(k=1\) then \(1!(n-1)!M\left(\begin{bmatrix}n\\ 1\end{bmatrix}\right)=(n-1)!\) and if \(k=2\) then \[2!(n-2)!M\left(\begin{bmatrix}n\\ 2\end{bmatrix}\right)=2(n-2)!\lfloor n/2\rfloor=\left\{\begin{matrix}(n-1)!&n\mathrm{\ odd}\\ n(n-2)!& n\mathrm{\ even}\end{matrix}\right.\]