NB: A PDF version of this announcement (suitable for posting) is also available.

Intersection patterns of geometric objects

Rados Radoicic
Rutgers, The State University of New Jersey

Wednesday, February 15, 2006
102 Bradley Hall, 4:05 pm
Tea 3:30 pm, Math Lounge

Abstract: Not every graph can be obtained as the intersection graph of, say, straight-line segments (or other geometric objects) in the plane. These graphs have many nice structural properties. In particular, they contain much larger homogenous subgraphs than guaranteed by Ramsey's theorem. It seems that this phenomenon is related to some basic topological facts, including the Borsuk-Ulam theorem. But does it have anything to do with algebra? We discuss this question and as a byproduct, we prove a conjecture of Erdos about distance distributions in d-space. Our proof also uses Szemeredi's regularity lemma.

This is joint work with the appropriate subsets of the following people: N. Alon, J. Pach, R. Pinchasi, M. Sharir, and J. Vondrak.

This talk will be accessible to undergraduates.