Title: Locally-Planar Graphs

Speaker: Gabor Tardos, Renyi Institute

Location: Hill Center, room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

A geometric graph is a straight-line plane drawing of a graph, possibly with intersecting edges. Elementary fact (about planar graphs) is that if a geometric graph does not have intersecting edges then it has at most 3v-6 edges, where v is the number of vertices.

What happens if we want the intersection-free property to hold locally, i.e., we require that some k radius (graph-theoretic) neighborhood of every vertex be intersection-free. In other words all self-intersecting paths have to be of length at least 2k+1. Surprisingly, such a locally planar graph can have a super-linear number edges: we construct such a graph with average degree approximately k-times-iterated log of v (where v is the number of vertices). Matching upper bound is not known, the exact order of magnitude of the number of edges in the extremal graph is only known for the simplest case when only self-intersecting paths of length 3 are forbidden. (This is joint result with J. Pach and G. Toth.)

The construction is based on a recursive thinning procedure of bipartite graphs. This same procedure yields interesting results also in the Turan-type extremal theory of matrices. Consider the following question:

How many 1 can there be in an n by n 0-1 matrix that avoids certain configurations of 1's (submatrices)?

It was noted first by Z. Furedi that the number of 1 entries in a matrix avoiding the configuration
11
1 1
(not necessarily consecutive rows/columns) is O(n\log n). We show that if a matrix avoids both the configuration
11
1 1
and its mirror image:
1 1
11
then it has O(n\log\log n) 1 entries, and this bound is tight.