2019/04/30 by Martin Doležal, Jan Hladký, Jan Kolář +3
Mathematics · #Euclidean geometry #Euclidean space #Graph #Graph theory and applications #Lebesgue integration #Lebesgue measure #Limits and Structures in Graph Theory #Measure (data warehouse) #Stochastic processes and statistical mechanics #Vertex (graph theory) #math.CO #math.MG
paper · pdf · doi:10.1007/s00454-020-00183-2
published in Discrete & Computational Geometry 66(1), 281-300 (Springer Science+Business Media) · 15 pages, 3 figure; minor edits including more details in the proof of Theorem 1.8
openalex created_date 2019/04/25 · arxiv created 2020/01/08 · openalex publication_date 2020/02/24 · arxiv updated 2021/11/16 · openalex updated_date 2026/08/05
Given a measurable set A⊂ \mathbb Rd we consider the "large-distance graph" GA, 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.