Generalized permutahedra and Schubert calculus (Q2101710)

The paper gives a sufficient criterion for Schubert intersection numbers to vanish which can be executed in polynomial time. Schubert intersection numbers arise from Schubert varieties \(X_{w}\), which are certain subvarieties of the flag variety \(X\) indexed by permutations \(w \in S_{n}\). The Poincaré duals \(\sigma_{w} = [X_{w}]\) of Schubert varieties form a basis of the cohomology ring \(H^\ast(X)\) of the flag variety. A Schubert problem is a \(k\)-tuple \((w^{(1)}, w^{(2)}, \dots, w^{(k)})\) of permutations in \(S_{n}\) such that the sum of the lengths is \(\binom{n}{2}\). The Schubert intersection number \(C_{w^{(1)}, w^{(2)}, \dots, w^{(k)}}\) is equivalently either \begin{itemize} \item the multiplicity of \(\sigma_{w_{0}}\) in \(\prod_{i = 1}^k \sigma_{w^{(i)}}\), or \item the number of points in \(\bigcap_{i = 1}^k g_{i}X_{w^{(i)}}\), where each \(g_{i}\) lies in some dense open subset of \(GL_{n}\). \end{itemize} Finding a combinatorial counting rule for Schubert intersection numbers is a famous open problem. Many algorithms exist for computing them. As stated previously, the aim of the paper is to give an algorithm to decide whether or not they vanish in a given case. The algorithm which the paper introduces proceeds roughly as follows. Given \(w \in S_{n}\), one can define the Rothe diagram \(D(w)\) as a certain subset of the boxes of the \(n \times n\) grid. Given a Schubert problem \((w^{(1)}, w^{(2)}, \dots, w^{(k)})\), one concatenates the Rothe diagrams \(D(w^{(i)})\) to obtain a diagram \(D\). One then considers the fillings of \(D\) which obey certain rules. If there are no such fillings, then the Schubert intersection number vanishes. There is then a polynomial-time algorithm to determine whether there are indeed no such fillings. The arguments of the paper use generalised permutahedra, which are obtained from the standard permutahedron by degeneration. The particular generalised permutahedra that the authors are interested in are known as ``Schubitopes''. These are constructed from fillings of rectangular grids. In the case of the Rothe diagram \(D(w)\) mentioned above, the Schubitope obtained is the Newton polytope of the Schubert polynomial \(\mathfrak{S}_{w}\) of \(w\) by [\textit{A. Fink} et al., Adv. Math. 332, 465--475 (2018; Zbl 1443.05179)]. The crux is that the emptiness of the set of fillings from the previous paragraph is equivalent to the presence of a certain point in a Schubitope by \textit{A. Adve} et al. [Sémin. Lothar. Comb. 82B, Paper No. 52, 12 p. (2019; Zbl 1436.05115)]. This can then be decided in polynomial time by standard linear programming methods, given the algorithm mentioned above. The paper finishes by comparing the test for vanishing of Schubert intersection numbers proven in the paper to three other tests from the literature. In each instance, there are some cases in which the test from the paper can decide and which the test from the literature cannot, and also some cases where the opposite is true. We mention finally that the paper contains a couple of variations on its main result.