SIR Mathematics Investigation Abstract
DISCRETE GEOMETRY AND EXTREMAL GRAPH THEORY
Presenter:
Tony Liu, Illinois Mathematics and Science Academy
Advisor:
Professor Laszlo Babai, University of Chicago
Abstract:
In 1946, Paul Erdos proposed the following problem: what is the maximum number of unit distances among n points in the plane? Erdos established an upper bound of and a lower bound that grows slightly faster than n.
A graph is a collection of "vertices" and "edges" connecting some pairs of vertices. For example, in an airline route chart, airports are the vertices and direct connections correspond to the edges. We examine graphs without a 4-cycle, and show the maximum number of edges to be at most . Replacing the 4-cycle by the "T-graph,'' we obtain an upper bound of on the number of edges. Finally, we use this seemingly unrelated graph theoretic result to establish Erdos' upper bound on the number of unit distances.
Although we present the optimal solution, within a constant factor, to the graph theory problem, Erdos' question on unit distances remains wide open after sixty years.