2023/03/26 by József Balogh, Felix Christian Clemen, Balogh, József +3
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Mathematics and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2303.14663
openalex publication_date 2023/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Almost 50 years ago Erdős and Purdy asked the following question: Given n points in the plane, how many triangles can be approximate congruent to equilateral triangles? They pointed out that by dividing the points evenly into three small clusters built around the three vertices of a fixed equilateral triangle, one gets at least \lfloor (n)/(3) \rfloor ⋅ \lfloor (n+1)/(3) \rfloor ⋅ \lfloor (n+2)/(3) \rfloor such approximate copies. In this paper we provide a matching upper bound and thereby answer their question. More generally, for every triangle T we determine the maximum number of approximate congruent triangles to T in a point set of size n. Parts of our proof are based on hypergraph Turán theory: for each point set in the plane and a triangle T, we construct a 3-uniform hypergraph H=H(T), which contains no hypergraph as a subgraph from a family of forbidden hypergraphs F=F(T). Our upper bound on the number of edges of H will determine the maximum number of triangles that are approximate congruent to T.