Math 206B Combinatorial Theory: Total positivity (Winter 2020)

Course description: We will discuss combinatorial aspects of recent developments in the theory of total positivity. We will also consider several applications to particle physics and statistical mechanics. The following topics will be covered:

Grassmannians and flag varieties.
Permutations, reduced words, matroids, and planar bipartite graphs.
Polytopes: permutohedra, associahedra, hypersimplices, cyclic polytopes, zonotopes.
Combinatorial topology: partially ordered sets and regular CW complexes.
Amplituhedron and the physics of scattering amplitudes.
Statistical mechanics: electrical networks and the Ising model.

Instructor: Pavel Galashin (udе.аlсu.htаm@nihsаlаg)

Time and location: MWF 1-1:50, room MS 5127.

Grading: based on several homework problem sets.

Prerequisites: basic knowledge of linear algebra.

Office hours: by appointment.

Homeworks

Homework #1 was due in class on Monday, February 10.
Homework #2 was due by email on Wednesday, March 11.

Lectures

Lecture 1 (01/06/20). Describing polytopes by inequalities: simplex, hypercube, hypersimplex. Definition of totally positive and totally nonnegative square matrices. Cauchy-Binet formula. The space of totally nonnegative upper unitriangular matrices.
Lecture 2 (01/08/20). Cells coming from totally nonnegative upper unitriangular matrices. Bruhat order, reduced words, wiring diagrams.
Lecture 3 (01/10/20). Properties of the Bruhat order. Weak Bruhat order and the permutohedron. Handout #1 (pdf).
Lecture 4 (01/13/20). Back to the TNN part of U: a cell decomposition, Lusztig's relation, closure relations.
Lecture 5 (01/15/20). Lindström–Gessel–Viennot lemma (wiki).
Lecture 6 (01/17/20). Applications of the LGV lemma. Describing cells of the TNN part of U using minors.
Lecture 7 (01/22/20). Disjointness of cells in the TNN part of U. Optimal total positivity tests via chamber minors in wiring diagrams.
Lecture 8 (01/24/20). Total positivity of the Vandermonde matrix. Schur polynomials (wiki).
Lecture 9 (01/27/20). TNN square matrices: cell decomposition and generators (see [FZ99]).
Lecture 10 (01/29/20). Grassmannian: definition and basic properties.
Lecture 11 (01/31/20). Plücker coordinates. Matroid stratification of Gr(k,n).
Lecture 12 (02/03/20). Non-realizable matroids. Schubert stratification of Gr(k,n).
Lecture 13 (02/05/20). Counting points over finite fields. Plücker relations. Cohomology.
Lecture 14 (02/07/20). Cohomology of the Grassmannian. The Littlewood-Richardson rule.
Lecture 15 (02/10/20). Symmetries of Littlewood-Richardson coefficients. Homework discussion.
Lecture 16 (02/12/20). The totally nonnegative Grassmannian - definition, cyclic symmetry, positroids.
Lecture 17 (02/14/20). Bounded affine permutations.
Lecture 18 (02/19/20). Open positroid varieties, bounded affine permutations, and Grassmann necklaces.
Lecture 19 (02/21/20). Plabic graphs, perfect orientations, almost perfect matchings.
Lecture 20 (02/24/20). Boundary measurement map. Moves on plabic graphs.
Lecture 21 (02/26/20). Reduced plabic graphs. Strand permutation.
Lecture 22 (02/28/20). Structure of the TNN Grassmannian. Topology of the whole space (it's a ball).
Lecture 23 (03/02/20). Regular CW complexes. Fomin-Shapiro conjecture (it's true).
Lecture 24 (03/04/20). TNN Grassmannians and partial flag varieties are regular CW complexes.
Lecture 25 (03/06/20). Ising model: definition, history, phase transitions, boundary correlation matrix.
Lecture 26 (03/09/20). Ising model and the totally nonnegative orthogonal Grassmannian. (arXiv:1807.03282)
Lecture 27 (03/11/20-cancelled). See these slides.
Lecture 28 (03/13/20-cancelled). See this video.

Course materials

Here is some bibliography related to the first few lectures on totally positive and totally nonnegative square matrices.

[FZ99] S. Fomin and A. Zelevinsky, Double Bruhat cells and total positivity, J. Amer. Math. Soc. 12.2 (1999): 335-380.

[FZ00] S. Fomin and A. Zelevinsky, Total positivity: tests and parametrizations, Math. Intelligencer 22 (2000), 23-33.

[Fom10] S. Fomin, Total positivity and cluster algebras, Proceedings of the International Congress of Mathematicians. Volume II, 125–145, Hindustan Book Agency, New Delhi, 2010.
See also the links on this page.

Here's a great book on the Bruhat order.

[BB05] A. Bjorner, F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, 2005

The following sources will be relevant throughout the course.

[Lam14] T. Lam, Totally nonnegative Grassmannian and Grassmann polytopes, Current Developments in Mathematics, 2014.
[Pos06] A. Postnikov, Total positivity, Grassmannians, and networks, preprint, 2006.
[Pos13] Postnikov's lecture notes from 2013, scribed by A. Morales.

Regarding M_n and M'_n. For M'_n (sum over chains in the weak Bruhat order), this is due to Macdonald [Mac91], proven bijectively by Billey-Holroyd-Young [BHY17] in 2017. For M_n (sum over chains in the strong Bruhat order), the equality is due to Stembridge [Ste02], but goes back to a 1958 work by Chevalley. I do not know of any bijective proof.

For the cell decomposition of the TNN part of U, see Lusztig's paper [Lus94] (which may require some knowledge of algebraic groups).

[Mac91] I. Macdonald, Notes on Schubert Polynomials, vol. 6, Publications du LACIM, Université du Québec à Montréal, 1991.
[BHY17] S. C. Billey, A. E. Holroyd, B. Young, A bijective proof of Macdonald's reduced word formula, preprint, 2017.
[Ste02] J. Stembridge, A Weighted Enumeration of Maximal Chains in the Bruhat Order, Journal of Algebraic Combinatorics 15 (2002), 291–301.
[Lus94] G. Lusztig, Total Positivity in Reductive Groups, Lie Theory and Geometry. Progress in Mathematics, vol 123. Birkhäuser, Boston, MA.

As we go along, I will be adding more links here.