Ramsey-Turán numbers for semi-algebraic graphs
Summary: A \textit{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.
scientific article; zbMATH DE number 7032067
scientific article