A linear upper bound for the unit distance problem in convex position.
Bernardo Abrego and Sylvia Fernandez, Rutgers University
October 31, 4:30 PM, Rutgers Univ. Hill CORE building, Room 431
Abstract.
More than forty years ago Erdos and Moser conjectured that n
vertices of a strictly convex polygon determine O(n) unit distances. In
this talk we settle this conjecture affirmatively by proving the following
generalization.
For every strictly convex domain C with smooth boundary V, we
define the unit distance graph G=(V,E) associated with
V by connecting two points in the boundary if their distance is
one. We prove that there is a way of orienting the edges of this graph in
such a way that every vertex has in-degree at most 6.