Ramsey-Turan numbers for semi-algebraic graphs
A semi-algebraic graph G = (V, E) is a graph where the vertices are points in 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-Turan theorem: for every integer p >= 3, every K-p-free semi-algebraic graph on n vertices with independence number o(n) has at most 1/2(1 - 1/inverted right perpendicularp/2inverted left perpendicular - 1 + o(1)) n(2) edges. Here, the dependence on 1-1 the complexity of the semi-algebraic relation is hidden in the o(1) term. Moreover, we show that this bound is tight.
ojs-index-php-eljc-article-download-v25i4p61.pdf
Publisher's version
openaccess
CC BY
235.88 KB
Adobe PDF
1ad4a13dc43e01fe342acc1d775aad46