Ramsey-Turán numbers for semi-algebraic graphs
type: Item
instance of: scholarly article
title: Ramsey-Turán numbers for semi-algebraic graphs
zbMATH Open document ID: 1409.05207
author: Jacob Fox
author: János Pach
author: Andrew Suk
published in: The Electronic Journal of Combinatorics
publication date: 2019-03-05T00:00:00Z
full work available at URL: v25i4p61
review text: 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.
Mathematics Subject Classification ID: 05D10
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 7032067
MaRDI profile type: Publication
cites work: Crossing patterns of semi-algebraic sets
cites work: Über ein Extremalproblem der Graphentheorie
cites work: On a Ramsey-Turán type problem
cites work: Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
cites work: Ramsey-type results for semi-algebraic relations
cites work: More results on Ramsey-Turán type problems
cites work: Q5610920
cites work: A semi-algebraic version of Zarankiewicz's problem
cites work: A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing
cites work: Ramsey-Turán theory
cites work: Semi-algebraic Ramsey numbers
cites work: Q4401979
cites work: Triangle-free geometric intersection graphs with no large independent sets
description: scientific article; zbMATH DE number 7032067