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

0543158 - MÚ 2022 RIV US eng J - Článek v odborném periodiku
Doležal, Martin - Hladký, Jan - Kolář, Jan - Mitsis, T. - Pelekis, Christos - Vlasák, V.
A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems.
Discrete & Computational Geometry. Roč. 66, č. 1 (2021), s. 281-300. ISSN 0179-5376. E-ISSN 1432-0444
Grant CEP: GA ČR(CZ) GJ18-01472Y; GA ČR(CZ) GA17-27844S
Institucionální podpora: RVO:67985840
Klíčová slova: extremal graph theory * geometric graphs
Obor OECD: Pure mathematics
Impakt faktor: 0.639, rok: 2021
Způsob publikování: Omezený přístup
https://doi.org/10.1007/s00454-020-00183-2

Given a measurable set A⊂R^d we consider the 'large-distance graph' 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.
Trvalý link: http://hdl.handle.net/11104/0320435