A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems

Abstract

Given a measurable set $A\subset {\mathbb{R}}^d$ we consider the "large-distance graph" ${\mathcal{G}}_A$, on the ground set $A$, in which each pair of points from $A$ whose distance is bigger than 2 forms an edge. We consider the problems of maximizing the $2d$-dimensional Lebesgue measure of the edge set as well as the $d$-dimensional Lebesgue measure of the vertex set of a large-distance graph in the $d$-dimensional Euclidean space that contains no copies of a complete graph on $k$ vertices. The former problem may be seen as a continuous analogue of Turán's classical graph theorem, and the latter as a graph-theoretic analogue of the classical isodiametric problem. Our main result yields an analogue of Mantel's theorem for large-distance graphs. Our approach employs an isodiametric inequality in an annulus, which might be of independent interest.

15 pages, 3 figure; minor edits including more details in the proof of Theorem 1.8