Thu, January 2, 2:30 PM
45 MINUTES
Extremal Configurations in Point-Line Arrangements

The famous Szemerédi-Trotter theorem states that any arrangement of n points and n lines in the plane determines O(n4/3) incidences, and this bound is tight. Al-though there are several proofs for the Szemerédi-Trotter theorem, our knowledge of the structure of the point-line arrangements maximizing the number of incidences is severely lacking. In this talk, we present some Turán-type results for point-line incidences. Let L1 and L2 be two sets of t lines in the plane and let P = {l1 ϵ l2 : l1 ϵ L1,l2 ϵ L2} be the set of intersection points between L1 and L2. We say that (P,L1 ϵ L2) forms a natural t × t grid if |P| = t2, and conv(P) does not contain the intersection point of some two lines in Li, for i = 1,2. For fixed t > 1, we show that any arrangement of n points and n lines in the plane that does not contain a natural t×t grid determines O(n-43ϵ) incidences, where ϵ = ϵ(t). We also provide a con-struction of n points and n lines in the plane that does not contain small cycles and determines superlinear number of incidences. This is joint work with Andrew Suk and Jacques Verstraete.

Mozhgan Mirzaei

PhD student at the University of California at San Diego

Mozhgan is a last year PhD student at the University of California at San Diego, working under supervision of prof. Andrew Suk. She is interested in Combinatorics and Combinarial Geometry. She got her B.Sc degree in Mathematics from Sharif University of Technology under supervision of prof. Ebadollah Mahmoodian.