Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
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.
Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis