% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.61}{25(4)}{2018}

% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded.
% We recommend these AMS packages:
\usepackage{amsmath,amssymb}
% We recommend the graphicx package for importing figures:
\usepackage{graphicx}
% Use this command to create hyperlinks (optional and recommended):
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note

%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Jul 7, 2018}{Nov 26, 2018}{Dec 21, 2018}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05D10, 52C10}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{  The authors. Released under the CC BY-ND license (International 4.0).}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\newcommand{\RR}{{\mathbb R}}
	\newcommand{\NN}{{\mathbb N}}

% If needed, include a line break (\\) at an appropriate place in the title.
\title{Ramsey-Tur\'an numbers for semi-algebraic graphs}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

\author{Jacob Fox\thanks{Supported by a Packard Fellowship and by NSF CAREER award DMS 1352121.}\\
\small Department of Mathematics\\[-0.8ex]
\small Stanford University\\[-0.8ex]
\small Stanford, CA, U.S.A.\\
\small\tt jacobfox@stanford.edu \\
\and
J\'anos Pach\thanks{Supported by Swiss National Science Foundation Grants 200020-162884 and 200021-175977.} \\
\small Chair of Combinatorial Geometry DCG\\[-0.8ex]
\small \'Ecole Polytechnique F\'ed\'erale de Lausanne\\[-0.8ex]
\small Lausanne, Switzerland\\
\small\tt pach@cims.nyu.edu
\and
Andrew Suk\thanks{Supported an NSF CAREER award and an Alfred Sloan Fellowship.} \\
\small Department of Mathematics\\[-0.8ex]
\small University of California San Diego\\[-0.8ex]
\small La Jolla, CA, U.S.A.\\
\small\tt asuk@ucsd.edu }

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract may be distributed without the rest of the
% paper so it must be entirely self-contained.  Try to include all words
% and phrases that someone might search for when looking for your paper.

\begin{abstract}
A \emph{semi-algebraic graph} $G = (V,E)$ is a graph where the vertices are points in $\RR^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\'an 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.
\end{abstract}


\section{Introduction}


Over the past decade, several authors have shown that many classical theorems in extremal graph theory can be significantly improved if we restrict our attention to semi-algebraic graphs, that is, graphs whose vertices are points in Euclidean space, and edges are defined by a semi-algebraic relation of constant complexity \cite{alon,CFPSS,FPSSZ,suk,FPS,BM}.  In this note, we continue this sequence of works by studying Ramsey-Tur\'an numbers for semi-algebraic graphs.

More formally, a graph $G  = (V,E)$ is a \emph{semi-algebraic graph} with \emph{complexity} at most $t$, if its vertex set $V$ is an ordered set of points in $\RR^d$, where $d \leq t$, and if there are at most $t$ polynomials $g_1,\ldots,g_s\in \RR[x_1,\ldots,x_{2d}]$, $s\leq t$, of degree at most $t$ and a Boolean formula $\Phi$ such that for vertices $u,v \in V$ such that $u$ comes before $v$ in the ordering,
$$(u,v) \in E \hspace{.5cm}\Leftrightarrow\hspace{.5cm} \Phi(g_{1}(u,v) \geq 0;\ldots;g_{s}(u,v) \geq 0) = 1.$$

\noindent  At the evaluation of $g_{\ell}(u,v)$, we substitute the variables $x_1,\ldots,x_d$ with the coordinates of $u$, and the variables $x_{d+1},\ldots,x_{2d}$ with the coordinates of $v$.  Here, we assume that the complexity $t$ is a fixed parameter, and $n =|V|$ tends to infinity.


The classical theorem of Tur\'an gives the maximum number of edges in a $K_p$-free graph on $n$ vertices.

  \begin{theorem}[Tur\'an, \cite{T41}]\label{turan}
Let $G = (V,E)$ be a $K_p$-free graph with $n$ vertices.  Then  $$|E|\leq \frac{1}{2}\left(1 - \frac{1}{p-1} + o(1)\right)n^2.$$
\end{theorem}

\noindent The only graph for which this bound is tight is the complete $(p-1)$-partite graph whose parts are of size as equal as possible.  This graph can easily be realized as an intersection graph of segments in the plane, which is a semi-algebraic graph with complexity at most four.  Therefore, Tur\'an's theorem cannot be improved by restricting it to semi-algebraic graphs.


Let $H$ be a fixed graph.  The \emph{Ramsey-Tur\'an number} $\mathbf{RT}(n,H,\alpha)$ is defined as the maximum number of edges that an $n$-vertex graph of independence number at most $\alpha$ can have without containing $H$ as a (not necessarily induced) subgraph.  Ramsey-Tur\'an numbers were introduced by Andr\'asfai~\cite{An} and were motivated by the classical theorems of Ramsey and Tur\'an and their connections to geometry, analysis, and number theory.  According to one of the earliest results in Ramsey-Tur\'an theory, which appeared in \cite{sos}, for every $p\geq 2$, we have
\begin{equation}\label{eq1}
\mathbf{RT}(n,K_{2p-1},o(n)) = \frac{1}{2}\left(1 - \frac{1}{p-1}\right)n^2 + o(n^2).
\end{equation}

\noindent For excluded $K_4$, a celebrated result of Szemer\'edi \cite{S72} and Bollob\'as-Erd\H{o}s \cite{BE} states that
$$\mathbf{RT}(n,K_4,o(n)) = \frac{1}{8}n^2 + o(n^2).$$

\noindent This was generalized by Erd\H os, Hajnal, S\'os, and Szemer\'edi \cite{EHSS83} to all cliques of even size. For every $p\ge 2$, we have
\begin{equation}\label{eq2}
\mathbf{RT}(n,K_{2p},o(n)) = \frac{1}{2}\cdot\frac{3p-5}{3p-2}n^2 + o(n^2).
\end{equation}

\noindent For more results in Ramsey-Tur\'an theory, consult the survey of Simonovits and S\'os \cite{SS01}.


In the present note, we establish asymptotically tight bounds on Ramsey-Tur\'an numbers for semi-algebraic graphs. We define $\mathbf{RT}_{t}(n,K_p,o(n))$ as the maximum number of edges that $n$-vertex $K_p$-free semi-algebraic graphs with complexity at most $t$ can have, if their independence number is $o(n)$. Strictly speaking, this definition and all above results apply to {\em sequences} of graphs with $n$ vertices, as $n$ tends to infinity.

It turns out that if the size of the excluded clique is {\em even}, then the answer to the Ramsey-Tur\'an question significantly changes when the graphs are required to be semi-algebraic. However, in the odd case, we obtain the same asymptotics for the Ramsey-Tur\'an function as in (\ref{eq1}). More precisely, we have


\begin{theorem}\label{rt}

For any fixed integers $t\geq 5$ and $p \geq 2$, we have

$$\mathbf{RT}_{t}(n,K_{2p-1},o(n)) = \mathbf{RT}_{t}(n,K_{2p},o(n)) = \frac{1}{2}\left(1 - \frac{1}{p-1}\right)n^2  + o(n^2).$$

\end{theorem}












\section{Proof of Theorem \ref{rt}}\label{ramseyturan}


The aim of this section is to prove Theorem \ref{rt}.  One of the main tools used in the proof is the following regularity lemma for semi-algebraic graphs.   Given a graph $G = (V,E)$, a vertex partition is called \emph{equitable} if any two parts differ in size by at most one.  Given two disjoint subsets $V_i,V_j \subset V$, we say that the pair $(V_i,V_j)$ is \emph{homogeneous} if $V_i\times V_j \subset E$ or $(V_i\times V_j) \cap E = \emptyset.$

\begin{lemma}[\cite{FPS}]\label{reg1}

For any positive integer $t$, there exists a constant $c = c(t) > 0$ with the following property.  Let $0 < \varepsilon < 1/2$ and let $G = (V,E)$ be a semi-algebraic graph with complexity at most $t$.  Then $V$ has an equitable partition $V = V_1\cup \cdots \cup V_K$ into $K$ part, where $1/\varepsilon < K <  (1/\varepsilon)^c$, such that all but an $\varepsilon$-fraction of the pairs of parts are homogeneous.

\end{lemma}









The upper bound in Theorem \ref{rt} follows from


\begin{theorem}

Let $\varepsilon > 0$ and let $G = (V,E)$ be an $n$-vertex semi-algebraic graph with complexity at most $t$.  If $G$ is $K_{2p}$-free and $|E| >  \frac{1}{2}\left(1 - \frac{1}{p-1}  + \varepsilon\right)n^2$, then $G$ has an independent set of size $\gamma n$, where $\gamma = \gamma(t,p,\varepsilon)$.

\end{theorem}


\begin{proof}  We apply Lemma \ref{reg1} with parameter $\varepsilon/4$ to obtain an equitable partition $\mathcal{P}:V = V_1\cup\cdots\cup V_K$ such that $\frac{4}{\varepsilon} \leq K\leq \left(\frac{4}{\varepsilon}\right)^{c}$, where $c = c(t)$ and all but an at most $\frac{\varepsilon}{4}$-fraction of all pairs of parts in $\mathcal{P}$ are homogeneous (complete or empty with respect to $E$).  If $n \leq 10K$, then $G$ has an independent set of size one, and the theorem holds trivially.  So, we may assume $n > 10K$.

By deleting all edges inside each part, we have deleted at most
$$K{\lceil n/K \rceil\choose 2} \leq \frac{4n^2}{5K} \leq \varepsilon \frac{n^2}{5}$$
edges.  Deleting all edges between non-homogeneous pairs of parts, we lose an additional at most
$$\left\lceil\frac{n}{K}\right\rceil^2\frac{\varepsilon}{4}\frac{K^2}{2} \leq \varepsilon\frac{n^2}{5}$$
 edges. In total, we have deleted at most $2\varepsilon n^2/5$ edges of $G$.  The only edges that remain in $G$ are edges between homogeneous pairs of parts, and we have at least\,$\frac{1}{2}\left(1 - \frac{1}{p-1} + \varepsilon/5\right)n^2$ edges.  
By Tur\'an's theorem (Theorem \ref{turan}), there is at least one remaining copy of $K_p$, and its vertices lie in $p$ distinct parts $V_{i_1},\ldots,V_{i_p} \in \mathcal{P}$ that form a complete $p$-partite subgraph. 
 If any of the parts $V_{i_j}$ forms an independent set in $G$, then there is an independent set of order $|V_{i_j}| \geq \lfloor n/K\rfloor \geq \gamma n$, 
 where $\gamma = \gamma(t,\epsilon, p)$, and we are done.  Otherwise, there is an edge in each of the $p$ parts, and the endpoints of these $p$ edges 
 form a $K_{2p}$ in $G$, a contradiction.\end{proof}

\smallskip

The lower bound on $\mathbf{RT}(n,K_{2p-1},o(n))$ and $\mathbf{RT}(n,K_{2p},o(n))$ in Theorem \ref{rt} is constructive and is based on the following result of Walczak.


\begin{lemma}[\cite{walczak}]\label{segments}

For any pair of positive integers $n$ and $p$, where $n$ is a multiple of $p-1$, there is a collection $S$ of $n/(p-1)$ segments in the plane whose intersection graph $G_S$ is triangle-free and has no independent set of size $c_pn/\log\log n$. Here $c_p$ is a suitable constant.

\end{lemma}


\noindent \textbf{The construction.}  Take $p-1$ dilated copies of a set $S$ meeting the requirements in Lemma \ref{segments}, and label them as $S_1,\ldots, S_{p-1}$, so that $S_i$ lies inside a ball with center $(i,0)$ and radius 1/10.  Set $V = S_1\cup\cdots \cup S_{p-1}$.  Note that $|S_i| = n/(p-1)$ so that $|V| = n$.  Let $G = (V,E)$ be the graph whose vertices are the elements of $V$, and two vertices (that is, two segments) are connected by an edge if and only if they cross or their left endpoints are at least 1/2 apart.  The graph $G$ consists of a complete $(p-1)$-partite graph, where each part induces a copy of the triangle-free graph $G_S$.  Clearly, $G$ is $K_{2p-1}$-free and does not contain any independent set of size $c_pn/\log\log n$.  Moreover, $$|E(G)| \geq \frac{1}{2}\left(1 - \frac{1}{p-1}\right)n^2.$$  Every segment can be represented by a point in $\RR^4$, and whether or not two segments intersect can be determined by four polynomial inequalities of degree at most two (see \cite{alon}).  Thus, counting the distance condition, we have 5 quadratic inequalities, showing that $E$ is a semi-algebraic relation of complexity $5$.


















\begin{thebibliography}{99}

    \bibitem{alon} N. Alon, J. Pach, R. Pinchasi, R. Radoi\v{c}i\'c, and M. Sharir, Crossing patterns of semi-algebraic sets, \emph{J. Combin. Theory Ser. A} \textbf{111} (2005), 310--326.

\bibitem{An} B. Andr\'asfai, \"Uber ein Extremalproblem der Graphentheorie, {\em Acta Math. Hungar.} {\bf 13} (1962) 443--455.

\bibitem{BE} B. Bollob\'as and P. Erd\H{o}s, On a Ramsey-Tur\'an type problem,  \emph{J. Combin. Theory Ser. B} {\bf 21} (1976), 166--168.

    \bibitem{BM} B. Bukh, J. Matou\v{s}ek, Erd\H os-Szekeres-type statements: Ramsey function and decidability in dimension 1, \emph{Duke J. Math.} \textbf{163} (2014), 2243--2270.

\bibitem{CFPSS} D. Conlon, J. Fox, J. Pach, B. Sudakov, A. Suk, Ramsey-type results for semi-algebraic relations, \emph{Trans. Amer. Math. Soc.}~\textbf{366} (2014), 5043--5065.



\bibitem{EHSS83} P. Erd\H os, A. Hajnal, V. S\'os, and E. Szemer\'edi, More results on Ramsey-Tur\'an type problems, \emph{Combinatorica} \textbf{3} (1983), 69--81.


\bibitem{sos} P. Erd\H os and V. S\'os, Some remarks on Ramsey's and Turan's theorem, \emph{Coll. Math. Soc. J. Bolyai} \textbf{4}, \emph{Comb. Theory and its Appl.}, North-Holland (1969), 395--404.

\bibitem{FPSSZ} J. Fox, J. Pach, A. Sheffer, A. Suk, J. Zahl, A semi-algebraic version of Zarankiewicz's problem, \emph{J. Eur. Math. Soc.} \emph{19} (2017), 1785-1810.


\bibitem{FPS} J. Fox, J. Pach, and A. Suk,  A polynomial regularity lemma for semi-algebraic hypergraphs and its applications in geometry and property testing, \emph{SIAM J. Comput.}~\textbf{45} (2016), 2199--2223.



\bibitem{SS01} M. Simonovits and V.T. S\'os, Ramsey-Tur\'an theory, \emph{Discrete Math.} \textbf{229} (2001), 293--340.



\bibitem{suk} A. Suk, Semi-algebraic Ramsey numbers, \emph{J. Combin. Theory Ser. B} \textbf{116} (2016), 465--483.


\bibitem{S72} E. Szemer\'edi, On graphs containing no complete subgraph with 4 vertices (Hungarian), \emph{Mat. Lapok} \textbf{23} (1972), 113--116.




\bibitem{T41} P. Tur\'an, On an extremal problem in graph theory, \emph{Matematikai \'es Fizikai Lapok} (in Hungarian) 48 (1941), 436--452.


\bibitem{walczak} B. Walczak, Triangle-free geometric intersection graphs with no large independent sets, \emph{Discrete Comput. Geom.} \textbf{53} (2015), 221--225.


 \end{thebibliography}


\end{document}
