Article ID Journal Published Year Pages File Type
4647079 Discrete Mathematics 2015 5 Pages PDF
Abstract
In 1959, Erdős and Moser asked for the maximum number of unit distances that may occur among the vertices of a convex n-gon. Until now, the best known upper bound has been 2πnlog2n+O(n), achieved by Füredi in 1990. In this paper we examine two properties that any convex polygon must satisfy and use them to prove several facts related to the above question. In particular, we improve upon Füredi's result, obtaining a bound of nlog2n+O(n); we exhibit a new class of “cycles” formed by unit distances that are forbidden in convex polygons; and we provide a lower bound that shows the limitations of our methods. The second result answers a question of Fishburn and Reeds in the negative.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,