Large cliques and independent sets all over the place

Alon, Noga; Bucić, Matija; Sudakov, Benny

doi:10.1090/proc/15323

Large cliques and independent sets all over the place
HTML articles powered by AMS MathViewer

by Noga Alon, Matija Bucić and Benny Sudakov PDF

Proc. Amer. Math. Soc. 149 (2021), 3145-3157 Request permission

Abstract:

We study the following question raised by Erdős and Hajnal in the early 90’s. Over all $n$-vertex graphs $G$ what is the smallest possible value of $m$ for which any $m$ vertices of $G$ contain both a clique and an independent set of size $\log n$? We construct examples showing that $m$ is at most $2^{2^{(\log \log n)^{1/2+o(1)}}}$ obtaining a twofold sub-polynomial improvement over the upper bound of about $\sqrt {n}$ coming from the natural guess, the random graph. Our (probabilistic) construction gives rise to new examples of Ramsey graphs, which while having no very large homogenous subsets contain both cliques and independent sets of size $\log n$ in any small subset of vertices. This is very far from being true in random graphs. Our proofs are based on an interplay between taking lexicographic products and using randomness.

References

H. L. Abbott, A note on Ramsey’s theorem, Canad. Math. Bull. 15 (1972), 9–10. MR 314673, DOI 10.4153/CMB-1972-002-5
Noga Alon, Michael Krivelevich, and Benny Sudakov, Induced subgraphs of prescribed size, J. Graph Theory 43 (2003), no. 4, 239–251. MR 1994296, DOI 10.1002/jgt.10117
Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
Noga Alon and Benny Sudakov, On graphs with subgraphs having large independence numbers, J. Graph Theory 56 (2007), no. 2, 149–157. MR 2350623, DOI 10.1002/jgt.20264
Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, and Santosh Vempala, Local versus global properties of metric spaces, SIAM J. Comput. 41 (2012), no. 1, 250–271. MR 2888328, DOI 10.1137/090780304
József Balogh and Wojciech Samotij, An efficient container lemma, Discrete Anal. , posted on (2020), Paper No. 17, 56. MR 4186910, DOI 10.19086/da
Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson, 2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction, Ann. of Math. (2) 176 (2012), no. 3, 1483–1543. MR 2979856, DOI 10.4007/annals.2012.176.3.3
M. Bucić and B. Sudakov, Large independent sets from local considerations, arXiv:2007.03667, 2020.
Eshan Chattopadhyay and David Zuckerman, Explicit two-source extractors and resilient functions, Ann. of Math. (2) 189 (2019), no. 3, 653–705. MR 3961081, DOI 10.4007/annals.2019.189.3.1
Gil Cohen, Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs, STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 278–284. MR 3536572, DOI 10.1145/2897518.2897530
P. Erdős and A. Szemerédi, On a Ramsey type theorem, Period. Math. Hungar. 2 (1972), 295–299. MR 325446, DOI 10.1007/BF02018669
P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. MR 19911, DOI 10.1090/S0002-9904-1947-08785-1
P. Erdös, Problems and results in combinatorial analysis and combinatorial number theory, Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) Wiley-Intersci. Publ., Wiley, New York, 1991, pp. 397–406. MR 1170793
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
Jacob Fox and Benny Sudakov, Induced Ramsey-type theorems, Adv. Math. 219 (2008), no. 6, 1771–1800. MR 2455625, DOI 10.1016/j.aim.2008.07.009
P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457
Dennis Geller and Saul Stahl, The chromatic number and other functions of the lexicographic product, J. Combinatorial Theory Ser. B 19 (1975), no. 1, 87–95. MR 392645, DOI 10.1016/0095-8956(75)90076-3
Helmut Hasse, Darstellbarkeit von Zahlen durch quadratische Formen in einem beliebigen algebraischen Zahlkörper, J. Reine Angew. Math. 153 (1924), 113–130 (German). MR 1581027, DOI 10.1515/crll.1924.153.113
Matthew Jenssen, Peter Keevash, Eoin Long, and Liana Yepremyan, Distinct degrees in induced subgraphs, Proc. Amer. Math. Soc. 148 (2020), no. 9, 3835–3846. MR 4127829, DOI 10.1090/proc/15060
K. S. Kedlaya, From quadratic reciprocity to class field theory, Princeton Companion to Mathematics, Princeton University Press, 2008.
Ph. G. Kolaitis, H. J. Prömel, and B. L. Rothschild, $K_{l+1}$-free graphs: asymptotic structure and a $0$-$1$ law, Trans. Amer. Math. Soc. 303 (1987), no. 2, 637–671. MR 902790, DOI 10.1090/S0002-9947-1987-0902790-6
Alexandr Kostochka and Matthew Yancey, Ore’s conjecture on color-critical graphs is almost true, J. Combin. Theory Ser. B 109 (2014), 73–101. MR 3269903, DOI 10.1016/j.jctb.2014.05.002
Michael Krivelevich, On the minimal number of edges in color-critical graphs, Combinatorica 17 (1997), no. 3, 401–426. MR 1606048, DOI 10.1007/BF01215921
Matthew Kwan and Benny Sudakov, Ramsey graphs induce subgraphs of quadratically many sizes, Int. Math. Res. Not. IMRN 6 (2020), 1621–1638. MR 4089430, DOI 10.1093/imrn/rny064
Matthew Kwan and Benny Sudakov, Proof of a conjecture on induced subgraphs of Ramsey graphs, Trans. Amer. Math. Soc. 372 (2019), no. 8, 5571–5594. MR 4014288, DOI 10.1090/tran/7729
Nathan Linial, Local-global phenomena in graphs, Combin. Probab. Comput. 2 (1993), no. 4, 491–503. MR 1264721, DOI 10.1017/S0963548300000857
Nathan Linial and Yuri Rabinovich, Local and global clique numbers, J. Combin. Theory Ser. B 61 (1994), no. 1, 5–15. MR 1275260, DOI 10.1006/jctb.1994.1026
M. Naor, Constructing Ramsey graphs from small probability spaces, Citeseer, 1992.
Hans Jürgen Prömel and Vojtěch Rödl, Non-Ramsey graphs are $c\log n$-universal, J. Combin. Theory Ser. A 88 (1999), no. 2, 379–384. MR 1723803, DOI 10.1006/jcta.1999.2972
F. P. Ramsey, On a Problem of Formal Logic, Proc. London Math. Soc. (2) 30 (1929), no. 4, 264–286. MR 1576401, DOI 10.1112/plms/s2-30.1.264
Saharon Shelah, Erdős and Rényi conjecture, J. Combin. Theory Ser. A 82 (1998), no. 2, 179–185. MR 1620869, DOI 10.1006/jcta.1997.2845
Terence Tao and Tamar Ziegler, Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors, Discrete Anal. , posted on (2016), Paper No. 13, 60. MR 3555196, DOI 10.19086/da.850