Vanishing of Littlewood-Richardson polynomials is in P (Q2311547): Difference between revisions

\textit{J. A. De Loera} and \textit{T. B. McAllister} [Exp. Math. 15, No. 1, 7--19 (2006; Zbl 1115.17005)] and Mulmuley, Narayanan and Sohoni [\textit{K. D. Mulmuley} et al., J. Algebr. Comb. 36, No. 1, 103--110 (2012; Zbl 1271.03055)] independently proved that determining the vanishing of Littlewood-Richardson coefficients has strongly polynomial time computational complexity. Viewing these as Schubert calculus numbers, they prove the generalization to the Littlewood-Richardson polynomials that control equivariant cohomology of Grassmannians. In this paper they construct a polytope using the edge-labeled tableau rule of \textit{H. Thomas} and \textit{A. Yong} [Ann. Inst. Fourier 68, No. 1, 275--318 (2018; Zbl 1400.05273)]. The proof then combines a saturation theorem of Anderson, Richmond and Yong [\textit{D. Anderson} et al., Compos. Math. 149, No. 9, 1569--1582 (2013; Zbl 1286.15023)], a reading order independence property, and \textit{É. Tardos}' algorithm for combinatorial linear programming [Oper. Res. 34, 250--256 (1986; Zbl 0626.90053)].