Colloquium: Natan Rubin (BGU) - Crossing Lemmas, touching Jordan curves, and finding large cliques

It is a major challenge in Combinatorial Geometry to understand the intersection structure of the edges in a geometric or topological graph, in the Euclidean plane. One of the few "tight" results in this direction is the the Crossing Lemma (due to Ajtai, Chvatal, Newborn, and Szemeredi 1982, and independently Leighton 1983). It provides a relation between the number of edges in the graph and the number of crossings amongst these edges. This line of work led to several Ramsey-type questions of geometric nature. We will focus on two recent advances. The first one is an analogue of the Crossing Lemma for contact graphs of families of Jordan curves. (It is inspired by the Circle Packing Lemma of Koebe 1936, Andreev 1970 and Thurston 1985.) The other result states that any complete (or dense) geometric graph must contain an almost-linear size family of edges with pairwise crossing interiors. Based on joint work with Janos Pach and Gabor Tardos.

Date: 

Thu, 01/11/2018 - 14:30 to 15:30

Location: 

Manchester Building (Hall 2), Hebrew University Jerusalem