Séminaire LACIM: «Combinatorial bounds and approximation via Lorentzian polynomials»

Conférencier: Jonathan Leake (Waterloo)

Lorentzian polynomials were developed about 5 years ago by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant to provide a unifying approach to various log-concavity statements (in particular, Mason’s conjectures). A line of research which has utilized this and related polynomial classes is that of the polynomial capacity method, which was developed by Gurvits about 20 years ago to bound and approximate the permanent of a matrix (among many other things). In this talk, we will describe this method and discuss a few of its applications; in particular, counting/approximating bipartite perfect matchings and counting/approximating lattice points of transportation and flow polytopes. If time permits, we will also briefly mention the most recent application to the analysis of the traveling salesperson problem. Joint work with various subsets of Petter Brändén, Leonid Gurvits, Nathan Klein, Alejandro Morales, and Igor Pak. 

clockCreated with Sketch.Date / heure

vendredi 23 février 2024
11 h

pinCreated with Sketch.Lieu

UQAM - Pavillon Président-Kennedy (PK)
201, avenue du Président-Kennedy
Montréal (QC)