A Proof of Erdős-Fishburn's Conjecture for $g(6)=13$

Wei Xianglin

Abstract


A planar point set $X$ in the Euclidean plane is called a $k$-distance set if there are exactly $k$ distances between two distinct points in $X$. An interesting problem is to find the largest possible cardinality of a $k$-distance set. This problem was introduced by Erdős and Fishburn (1996). Maximum planar sets that determine $k$ distances for $k$ less than 5 have been identified. The 6-distance conjecture of Erdős and Fishburn states that 13 is the maximum number of points in the plane that determine exactly 6 different distances. In this paper, we prove the conjecture.


Keywords


6-distance conjecture; Diameter graph; Independent set

Full Text: PDF