2009/11/24 by Yury J. Ionin · 1 citation
Computer Science · Mathematics · #Algorithm #Cardinality (data modeling) #Combinatorics #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete mathematics #Euclidean space #Geometry #Hamming code #Hamming distance #Hamming space #Hyperplane #Isosceles triangle #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Metric space #Plane (geometry) #Space (punctuation) #Upper and lower bounds
paper · pdf · doi:10.37236/230
openalex publication_date 2009/11/24 · openalex created_date 2022/05/12 · openalex updated_date 2026/05/21
In 1946, Paul Erdős posed a problem of determining the largest possible cardinality of an isosceles set, i.e., a set of points in plane or in space, any three of which form an isosceles triangle. Such a question can be asked for any metric space, and an upper bound n+2\choose 2 for the Euclidean space \Bbb En was found by Blokhuis. This upper bound is known to be sharp for n=1, 2, 6, and 8. We will consider Erdős' question for the binary Hamming space Hn and obtain the following upper bounds on the cardinality of an isosceles subset S of Hn: if there are at most two distinct nonzero distances between points of S, then |S|≤n+1\choose 2+1; if, furthermore, n≥ 4, n≠ 6, and, as a set of vertices of the n-cube, S is contained in a hyperplane, then |S|≤n\choose 2; if there are more than two distinct nonzero distances between points of S, then |S|≤n\choose 2+1. The first bound is sharp if and only if n=2 or n=5; the other two bounds are sharp for all relevant values of n, except the third bound for n=6, when the sharp upper bound is 12. We also give the exact answer to the Erdős problem for \Bbb En with n≤ 7 and describe all isosceles sets of the largest cardinality in these dimensions.