Locally planar geometric graphsGábor TardosRényi Institute of Mathematics, Hungary
November 6,

ABSTRACT


A geometric graph is a straightline 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 3v6 edges, where v is the number of vertices. What happens if we want the intersectionfree property to hold locally, i.e., we require that some k radius (graphtheoretic) neighborhood of every vertex be intersectionfree. In other words all selfintersecting paths have to be of length at least 2k+1. Surprisingly, such a locally planar graph can have a superlinear number edges: we construct such a graph with average degree approximately ktimesiterated 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 selfintersecting 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 Turantype extremal theory of matrices. Consider the following question: How many 1 can there be in an n by n 01 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

Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

