Personal tools
You are here: Home CG seminar 2018 New Crossing Lemmas
« September 2018 »
September
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
Log in


Forgot your password?
 

New Crossing Lemmas


Wednesday, May 16th, 2018, 16:10

Schreiber 309

underline

New Crossing Lemmas

János Pach, Rényi Institute, Budapest and EPFL, Lausanne

Abstract: 

The Crossing Lemma  of Ajtai, Chvátal, Newborn, Szemerédi (1982) and Leighton (1983) states that if a graph of n vertices and e>4n edges is drawn in the plane, then the number of crossings between its edges must be at least constant times e^3/n^2. This statement, which is asymptotically tight, has found many applications in combinatorial geometry and in additive combinatorics. However, most results that were obtained using the Crossing Lemma do not appear to be optimal, and there is a quest for improved versions of the lemma for graphs satisfying certain special properties. In this talk, I describe some recent extensions of the lemma to multigraphs (joint work with G. Tóth).

Document Actions