On the Ramsey-Turán problem for 4-cliques
Béla Csaba · 2025
Read On the Ramsey-Turán problem for 4-cliques by Béla Csaba (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00644.txt.
Introduction
Béla Csaba gives a near-tight bound for the Ramsey-Turán problem on four-cliques. A four-clique is a set of four nodes, each linked to the rest. He counts the most edges a graph can have with no such set. The count turns on the independence number, the size of the largest set with no links inside it. His proof avoids the Regularity lemma. That choice widens the range where the tight count holds, apart from small lower-order terms.
Catalog record
| CREATOR | Béla Csaba |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-00644
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Ramsey-Turán problem for 4-cliques Béla Csaba Abstract We present an essentially tight bound for the Ramsey-Turán problem for 4-cliques without using the Regularity lemma. This enables us to substantially extend the range in which one has the tight bound for the number of edges in K 4 K_{4} -free graphs as a function of the independence number, apart from lower order terms. 1 Introduction Two classical results in combinatorics are the Ramsey theorem [ 8 ] and the Turán [ 13 ] theorem. In 1969 Vera T. Sós in [ 12 ] introduced a common generalization of these, the so called Ramsey-Turán problems. The Ramsey-Turán number RT(n,H,m) is the maximum number of edges a graph G on n vertices with independence number less than m can have without containing H as a subgraph. In this paper we consider the H=K_{4} case. For more information on Ramsey-Turán theory the reader may consult with the excellent survey [ 9 ] by Simonovits and Sós. It is convenient to introduce the notation \alpha=m/n, we will use it throughout the paper. In 1972 Endre Szemerédi [ 10 ] proved the following upper bound for K_{4} -free graphs with a small independence number. Theorem 1.1 . For every \eta>0 there exists an \alpha>0 such that the following holds. Every n -vertex graph having at least (\frac{1}{8}+\eta)n^{2} edges contains either a K_{4} or an independent set larger than \alpha n. This result turned out to be almost tight, Bollobás and Erdős [ 1 ] constructed K_{4} -free graphs with independence number o(n) having n^{2}/8-o(n^{2}) edges. The proof 1 1 1 This was the first occurrence of a (weak) regularity notion. of Theorem 1.1 gives the upper bound of O((\log\log\frac{1}{\alpha})^{-1/2+o(1)}) for \eta. Conlon and Schacht, independently, in unpublished work, showed that the bound O((\log\frac{1}{\alpha})^{-1/2+o(1)}) is already sufficiently large for \eta, they applied the Frieze-Kannan weak regularity lemma [ 4 ] . In [ 3 ] Fox, Loh and Zhao gave significantly better upper and lower bounds for \eta as a function of \alpha. Their paper contains several deep results concerning the Ramsey-Turán problem for 4 -cliques, here we only mention those which are most relevant for our main theorem. Fox et al. proved that there exists an absolute constant \gamma>0 such that if \alpha\leq\gamma, \alpha(G)=\alpha n, and e(G)\geq\frac{n^{2}}{8}+\frac{3}{2}\alpha n^{2}, then G has a K_{4} (Theorem 1.6 in [ 3 ] ). For the lower bounds in [ 3 ] set \beta=\sqrt{(\log\log n)^{3}/\log n} and assume that 0<\alpha<1/3 such that \alpha/\beta\longrightarrow\infty. They constructed (Theorem 1.7) K_{4} -free graphs with maximum independent set of size \alpha n and number of edges at least \frac{n^{2}}{8}+(\frac{1}{3}-o(1))\alpha n^{2}. Moreover, in the case \alpha^{2}/\beta\longrightarrow\infty they gave an even stronger lower bound for the number of edges: \frac{n^{2}}{8}+(\alpha-\alpha^{2})\frac{n^{2}}{2}-\beta n^{2}. That is, they proved the following bounds for \eta if \alpha is sufficiently larger than \beta : \frac{1}{2}(\alpha-\alpha^{2})-o(\alpha^{2})\leq\eta\leq\frac{3}{2}\alpha. We remark that for the upper bound they used the Regularity lemma [ 11 ] . Recently, Lüders and Reiher [ 6 ] proved 2 2 2 In fact they considered the Ramsey-Turán problem for every K_{r} ( r\geq 3 ), and proved sharp bounds. that the above lower bound is essentially the truth in case \alpha is a constant (although very small). Theorem 1.2 . There exists a threshold 0<\gamma^{*}\ll 1 such that if 0<\gamma\leq\gamma^{*}, n is sufficiently large, G is a graph on n vertices with e(G)>(n^{2}+n)/8+(\gamma-\gamma^{2})n^{2}/2 and \alpha(G)\leq\gamma n, then G contains a K_{4}. Observe, that the above bound for \eta is (\gamma-\gamma^{2})/2, which could be much larger than (\alpha-\alpha^{2})/2, whenever \alpha\longrightarrow 0 as n\longrightarrow\infty. Since in the proof they used the Regularity lemma, \gamma^{*} is very small, and the sufficiently large n is in fact a tower-type function of \gamma. There is a significant interest in finding new, “Regularity lemma-free” proofs for theorems that use the Regularity lemma. This motivated our investigations. In the present paper we improve upon Theorem 1.2 in two ways. First, the value we give for \eta is essentially optimal for any \alpha which is smaller than an absolute constant. Second, since we do not use the Regularity lemma, the constants are much better, only single-exponential. Our main result is the following: Theorem 1.3 . Set \nu=1/500, and let \gamma=\exp(-10\log(1/\nu)/\nu) and N=\exp(10\log(1/\nu)/\nu). If n\geq N, G is a graph on n vertices with \alpha=\alpha(G)/n\leq\gamma and e(G)>\frac{n^{2}+n}{8}+(\alpha-\alpha^{2})\frac{n^{2}}{2}, then G contains a K_{4}. We did not optimize for the value of \nu in Theorem 1.3 , it is possible that with careful computation one can significantly improve upon it. Several ideas, which play an essential role in the proof of Theorem 1.3 , are taken from the papers [ 3 ] and [ 6 ] , together with a recent graph decomposition method of the author [ 2 ] , which has some common features with a key lemma in [ 10 ] . The outline of the paper is as follows. In the second section we discuss the necessary notions, and prove a key lemma. In the final section we prove our main theorem. Let us remark that we will not be concerned with floor signs, divisibility, and so on in the proof. This makes the notation simpler, and the proof easier to follow. 2 Definitions, main tools Given a graph G with vertex set V and edge set E we let e(G)=|E(G)|. For a vertex v\in V the degree of v is denoted by deg_{G}(v), if it is clear from the context, the subscription may be omitted. The neighborhood of v is denoted by N(v), so deg(v)=|N(v)|. The minimum degree of G is denoted by \delta(G). If S\subset V, then G[S] denotes the subgraph of G induced by S and deg(v,S)=|N(v)\cap S|. Given two disjoint sets S,T\subset V the bipartite subgraph induced by them is denoted by G[S,T], and E(G[S,T])=E(S,T), and we let e(S,T)=|E(S,T)|. Suppose that F=(V,E) is a graph with non-empty subsets A,B\subset V, A\cap B=\emptyset. Then the density of F[A,B] is d_{F}(A,B)=\frac{e_{F}(A,B)}{|A|\cdot|B|}. 2.1 On the minimum degree of G Let G=(V,E) be a graph on n vertices with independence number \alpha(G)=\alpha n, where 0<\alpha<1/3. We assume, as in Theorem 1.3 , that e(G)>\frac{n^{2}+n}{8}+(\alpha-\alpha^{2})\frac{n^{2}}{2}. Take the smallest subset V_{1}\subset V for which e(G[V_{1}])>\frac{|V_{1}|^{2}+|V_{1}|}{8}+(\alpha-\alpha^{2})\frac{n^{2}}{2} (note, that we have n, not |V_{1}| in the second part of the expression on the right). Let us denote G[V_{1}] by G_{1}. Claim 2.1 . The number of vertices in G_{1} is more than \sqrt{\alpha(G)n/2}\geq\sqrt{\alpha(G)N/2}. Proof: It is easy to see, that e(G_{1})>(\alpha-\alpha^{2})\frac{n^{2}}{2}. Since \alpha\leq\gamma<1/2, we have e(G_{1})>{\alpha n^{2}}/4=\alpha(G)n/4. Using that G_{1} is a simple graph, this implies that it must have more than \sqrt{\alpha(G)n/2} vertices. The fact that n\geq N finishes the proof. \Box Set n_{1}=|V_{1}|, and let \alpha_{1}=\alpha(G_{1})/n_{1}. Clearly, \alpha(G_{1})\leq\alpha(G), as G_{1} cannot have a larger independent set than what G has. Claim 2.2 . The minimum degree of G_{1} is at least n_{1}/4. Moreover, e(G_{1})>\frac{n_{1}^{2}+n_{1}}{8}+(\alpha_{1}-\alpha_{1}^{2})\frac{n_{1}^{2}}{2}. Proof: Using that V_{1} is the smallest subset with the above property, for every v\in V_{1} we have e(G_{1}[V_{1}-v])\leq\frac{(n_{1}-1)^{2}+n_{1}-1}{8}+(\alpha-\alpha^{2})\frac{n^{2}}{2}. Hence, deg_{G_{1}}(v)=e(G_{1}[V_{1}])-e(G_{1}[V_{1}-v])\geq\frac{(n_{1})^{2}+n_{1}}{8}+(\alpha-\alpha^{2})\frac{n^{2}}{2}-\frac{(n_{1})^{2}-n_{1}}{8}-(\alpha-\alpha^{2})\frac{n^{2}}{2}=\frac{n_{1}}{4}. Clearly, for the second part of the claim it is enough to prove that \alpha(G)n-\alpha(G)^{2}\geq\alpha(G_{1})n-\alpha(G_{1})^{2}, since n_{1}\leq n implies \alpha(G_{1})n-\alpha(G_{1})^{2}\geq\alpha(G_{1})n_{1}-\alpha(G_{1})^{2}. Dividing by n^{2} we get \frac{\alpha(G)}{n}-\frac{\alpha(G)^{2}}{n^{2}}\geq\frac{\alpha(G_{1})}{n}-\frac{\alpha(G_{1})^{2}}{n^{2}}. Since \alpha(G_{1})\leq\alpha(G)<n/2 and the function f(x)=x-x^{2} is monotone increasing in the interval (0,1/2), the above inequality is