library/distance_problems/bhowmick_2024_problem_erdos_about_rich_distances

Full paper in Markdown.

---

Full paper in Markdown.

Krishnendu Bhowmick, A problem of Erdős about rich distances. arXiv preprint (2024). arXiv:2407.01174, doi:10.48550/arXiv.2407.01174.

Bhowmick answers affirmatively an old question of Erdos on whether some set of n points can have cn distances each occurring more than n times, exhibiting a set of n points in which floor(n/4) distances occur more than n times. A generalization gives, for each m, sets of n points with c_mn distances occurring more than n+m times. The paper is six pages and construction-based; Theorems 1.1 and 1.2 give the two constructions. It was screened as a candidate source for problem 217 and confirmed unrelated: problem 217 concerns a set in which the i-th distance occurs exactly i times, a different configuration from richness above n.

For Problem 132, the construction is counterpressure rather than a solution: it shows that linearly many distance values can simultaneously have multiplicity greater than $n$, while Problem 132 asks how many occurring distances must have multiplicity at most $n$.

Source: https://arxiv.org/abs/2407.01174.