Ramsey-Turán numbers for semi-algebraic graphs
The electronic journal of combinatorics, Tome 25 (2018) no. 4
A semi-algebraic graph $G = (V,E)$ is a graph where the vertices are points in $\mathbb{R}^d$, and the edge set $E$ is defined by a semi-algebraic relation of constant complexity on $V$. In this note, we establish the following Ramsey-Turán theorem: for every integer $p\geq 3$, every $K_{p}$-free semi-algebraic graph on $n$ vertices with independence number $o(n)$ has at most $\frac{1}{2}\left(1 - \frac{1}{\lceil p/2\rceil-1} + o(1) \right)n^2$ edges. Here, the dependence on the complexity of the semi-algebraic relation is hidden in the $o(1)$ term. Moreover, we show that this bound is tight.
@article{10_37236_7988,
author = {Jacob Fox and J\'anos Pach and Andrew Suk},
title = {Ramsey-Tur\'an numbers for semi-algebraic graphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {4},
doi = {10.37236/7988},
zbl = {1409.05207},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7988/}
}
Jacob Fox; János Pach; Andrew Suk. Ramsey-Turán numbers for semi-algebraic graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/7988
Cité par Sources :