← All problems

Erdős Problem #96 — Unit distances in convex polygons

36 years old · traced to

For an integer n≥3n\ge 3, let P⊂R2P\subset\mathbb{R}^2 be the set of the nn distinct vertices of a convex nn-gon, and let U(P)U(P) count unordered pairs of distinct vertices at Euclidean distance exactly 11. The question is whether there is an absolute constant CC such that, for every nn and every such PP,

U(P)=#{{p,q}⊂P:p≠q, ∥p−q∥=1}≤Cn.U(P)=\#\bigl\{\{p,q\}\subset P: p\ne q,\ \|p-q\|=1\bigr\}\le Cn.

Equivalently, is the maximum Uc(n)U_c(n) of U(P)U(P) over convex nn-gons O(n)O(n) as nn grows? Erdős Problem #96 On Unit Distances in a Convex Polygon

Background

This is a structured version of the planar unit-distance problem: instead of maximizing over arbitrary sets of nn points, one restricts to the vertices of a convex polygon. Erdős and Moser posed the convex-polygon variant in 1959 and conjectured that its maximum is of linear order. Their initial lower bound was at least ⌊5(n−1)/3⌋\lfloor 5(n-1)/3\rfloor. The linear conjecture is commonly associated with Erdős and Moser; Erdős later credited the sharper proposed bound 2n2n to himself and Fishburn. Erdős Problem #96 On Unit Distances in a Convex Polygon

The convexity restriction makes the problem amenable to combinatorial encodings unavailable for arbitrary point sets. In particular, the upper-bound approach described for this problem represents convex-polygon distances using 00–11 matrices. This converts geometric restrictions on the vertices into constraints on patterns of unit-distance incidences, and gives bounds sharper than the general planar unit-distance estimate. On Unit Distances in a Convex Polygon

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.