The number of unit distances is almost linear for most norms (Q624331)

The author studies the maximal possible number \(u(n)\) of unit distances determined by an \(n\)-point set in the plane with a given norm. For the Euclidean norm, this question was raised by \textit{P.~Erdős} [Am. Math. Mon. 53, 248--250 (1946; Zbl 0060.34805)]. It is known that, for any strictly convex metric, \(u(n)\) grows not slower than \(n\log n\) [\textit{P.~Erdős} and \textit{G.~Purdy}, Proc. 7th Southeast. Conf. Comb., Graph Theory, Comput., Baton Rouge 1976, 307--322 (1976; Zbl 0345.52007)], not faster than \(n^{4/3}\) [\textit{J.~Spencer}, \textit{J.~Szemeredi} and \textit{W.~Trotter}, Graph theory and combinatorics, Proc. Conf. Hon. P. Erdős, Cambridge 1983, 293--303 (1984; Zbl 0561.52008)], and the upper bound is attained for a certain norm [\textit{P.~Valtr}, ``Strictly convex norms allowing many unit distances and related touching questions'', preprint, Charles University, Prague (2005)]. The author proves that the lower bound is ``almost'' attained for ``almost all'' norms. Namely, for all norms outside the union of countably many nowhere dense sets (in the sense of Hausdorff distance), \(u(n)\) is at most \( O(n \log n \log \log n)\). The proof is based on graph-theoretic results of independent interest.