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

Main Article Content

Martin Doležal Jan Hladký Jan Kolář Themis Mitsis Christos Pelekis Václav Vlasák

Abstract

A \emph{large-distance graph} is a measurable graph whose vertex set is a measurable subset of $\R^d$, and two vertices are connected by an edge if and only if their distance is larger that 2. We address questions from extremal graph theory in the setting of large-distance graphs, focusing in particular on upper-bounds on the measures of vertices and edges of $K_r$-free large-distance graphs. Our main result states that if $A\subset \R^2$ is a measurable set such that the large-distance graph on $A$ does not contain any complete subgraph on three verticesthen the $2$-dimensional Lebesgue measure of $A$ is at most $2\pi$.

Article Details

How to Cite
Doležal, M., Hladký, J., Kolář, J., Mitsis, T., Pelekis, C., & Vlasák, V. (2019). A Turán-type theorem for large-distance graphs in Euclidean spaces, and related isodiametric problems. Acta Mathematica Universitatis Comenianae, 88(3), 625-629. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1300/769
Section
EUROCOMB 2019