|Discrete Mathematics and Optimization Seminar
New York and Budapest
Monday December 6th at 4.30pm
Title. Intersection Patterns of Geometric Objects.
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 homogeneous 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 some of its computational consequences.
As a byproduct, we prove a conjecture of Erdos
about distance distributions in 3-space.