% 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}