Scaling algorithms and applications to extremal combinatorics
1 Plan of the Mini-Curso
For the minicurso, I intend to give three lectures geared towards introducing scaling problems to the participants, and then showcasing one recent application of such scaling problems to extremal combinatorics – the quantitative generalizations of the Sylvester-Gallai theorem obtained by [Bar+11; DSW14; Dvi+18].
The lectures shall be divided as follows (January 7th, 9th and 11th):
1. Introduction to scaling problems – general setting, background, history (from Hilbert’s definition of the null cone to Mumford and the works of Kempf-Ness-Mumford and Kirwan). In this lecture, I will describe the natural scaling problem given by a group acting on a vector space, and introduce the matrix scaling problem as a basic example that illustrates the theory.
2. Define matrix and operator scaling more formally, and prove some structural results about them, needed for the applications to extremal combinatorics.
3. Describe the Sylvester-Gallai (SG) problem, history and many generalizations of it. Show how matrix scaling is used to give good bounds on the quantitative versions of the SG problem. Show how operator scaling is used to give tight bounds on such quantitative version, and outline open questions in the field, and also some more open problems related to scaling problems.
These three lectures will be very elementary, with only a multivariate calculus and linear algebra background needed in order to grasp most of the concepts discussed.
[Bar+11] Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. “Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes”. In: Proceedings of the forty-third annual ACM symposium on Theory of computing. ACM. 2011, pp. 519–528.
[DSW14] Zeev Dvir, Shubhangi Saraf, and Avi Wigderson. “Improved rank bounds for design matrices and a new proof of Kelly’s theorem”. In: Forum of Mathematics, Sigma. Vol. 2. Cambridge University Press. 2014.[Dvi+18] Zeev Dvir, Ankit Garg, Rafael Oliveira, and Jozsef Solymosi. “Rank bounds for design matrices with block entries and geometric applications”. In: Discrete Analysis 5202018.1 (2018), p. 3118.