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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F21%3A00543158" target="_blank" >RIV/67985840:_____/21:00543158 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/21:10422533

Výsledek na webu

<a href="https://doi.org/10.1007/s00454-020-00183-2" target="_blank" >https://doi.org/10.1007/s00454-020-00183-2</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00454-020-00183-2" target="_blank" >10.1007/s00454-020-00183-2</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete & Computational Geometry

ISSN

0179-5376

e-ISSN

1432-0444

Svazek periodika

66

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

20

Strana od-do

281-300

Kód UT WoS článku

000516374700001

EID výsledku v databázi Scopus

2-s2.0-85107553012