New Crossing Lemmas with Multiplicities
Ponente: Janos Pach
Institución: Rényi Institute of Mathematics y Moscow Institute of Physics and Technology
Tipo de Evento: Investigación
Institución: Rényi Institute of Mathematics y Moscow Institute of Physics and Technology
Tipo de Evento: Investigación
| Cuándo |
26/03/2021 de 13:00 a 14:00 |
|---|---|
| Dónde | ZOOM ID 882 9372 3602 |
| Agregar evento al calendario |
vCal
iCal
|
According to the so-called crossing lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the crossing number of any graph with n vertices and m>4n edges is at least const.m^3/n^2. This result, which is tight up to the constant factor, has been successfully applied to a variety of problems in discrete and computational geometry, additive number theory, algebra, and elsewhere. In some applications, it is the bottleneck that one needs a lower bound on the crossing number of a multigraph rather than a graph. The aim of this talk is to review a number of recent attempts how to deal with this challenge.
