Voir la notice de l'article provenant de la source Cambridge University Press
@article{10_1017_fmp_2023_17,
author = {Matthew Kwan and Ashwin Sah and Lisa Sauermann and Mehtaab Sawhney},
title = {Anticoncentration in {Ramsey} graphs and a proof of the {Erd\H{o}s{\textendash}McKay} conjecture},
journal = {Forum of Mathematics, Pi},
publisher = {mathdoc},
volume = {11},
year = {2023},
doi = {10.1017/fmp.2023.17},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2023.17/}
}
TY - JOUR AU - Matthew Kwan AU - Ashwin Sah AU - Lisa Sauermann AU - Mehtaab Sawhney TI - Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture JO - Forum of Mathematics, Pi PY - 2023 VL - 11 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2023.17/ DO - 10.1017/fmp.2023.17 LA - en ID - 10_1017_fmp_2023_17 ER -
%0 Journal Article %A Matthew Kwan %A Ashwin Sah %A Lisa Sauermann %A Mehtaab Sawhney %T Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture %J Forum of Mathematics, Pi %D 2023 %V 11 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2023.17/ %R 10.1017/fmp.2023.17 %G en %F 10_1017_fmp_2023_17
Matthew Kwan; Ashwin Sah; Lisa Sauermann; Mehtaab Sawhney. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi, Tome 11 (2023). doi: 10.1017/fmp.2023.17
[1] , ‘Lower bounds for some Ramsey numbers’, Discrete Math. 2 (1972), 289–293.10.1016/0012-365X(72)90009-XGoogle Scholar | DOI
[2] and , ‘Ramsey graphs contain many distinct induced subgraphs’, Graphs Combin. 7 (1991), 1–6.10.1007/BF01789457Google Scholar | DOI
[3] , , and , ‘Sizes of induced subgraphs of Ramsey graphs’, Combin. Probab. Comput. 18 (2009), 459–476.10.1017/S0963548309009869Google Scholar | DOI
[4] and , ‘Graphs with a small number of distinct induced subgraphs’, Discrete Math. 75 (1989), 23–30. Graph theory and combinatorics (Cambridge, 1988).Google Scholar
[5] , and , ‘Algorithms with large domination ratio’, J. Algorithms 50 (2004), 118–131.10.1016/j.jalgor.2003.09.003Google Scholar | DOI
[6] , , and , ‘Edge-statistics on large graphs’, Combin. Probab. Comput. 29 (2020), 163–189.10.1017/S0963548319000294Google Scholar | DOI
[7] and , ‘Induced subgraphs with distinct sizes’, Random Structures Algorithms 34 (2009), 45–53.10.1002/rsa.20250Google Scholar | DOI
[8] , and , ‘Induced subgraphs of prescribed size’, J. Graph Theory 43 (2003), 239–251.10.1002/jgt.10117Google Scholar | DOI
[9] and , ‘Repeated communication and Ramsey graphs’, IEEE Trans. Inform. Theory 41 (1995), 1276–1289.10.1109/18.412676Google Scholar | DOI
[10] and , The Probabilistic Method, fourth edn., Wiley Series in Discrete Mathematics and Optimization ( & ., Hoboken, NJ, 2016).Google Scholar
[11] , , and , ‘2-source dispersers for entropy, and Ramsey graphs beating the Frankl-Wilson construction’, Ann. of Math. (2) 176 (2012), 1483–1543.10.4007/annals.2012.176.3.3Google Scholar | DOI
[12] , ‘A local limit theorem for cliques in ’, Preprint, .Google Scholar | arXiv
[13] , ‘A quantitative local limit theorem for triangles in random graphs’, Preprint, .Google Scholar | arXiv
[14] , , and , ‘Asymptotic distribution of random quadratic forms’, Preprint, .Google Scholar | arXiv
[15] , and , ‘Asymptotic distribution of Bernoulli quadratic forms’, Ann. Appl. Probab. 31 (2021), 1548–1597.10.1214/20-AAP1626Google Scholar | DOI
[16] and , ‘Induced subgraphs of Ramsey graphs with many distinct degrees’, J. Combin. Theory Ser. B 97 (2007), 612–619.10.1016/j.jctb.2006.09.006Google Scholar | DOI
[17] , and , ‘On subgraph sizes in random graphs’, Combin. Probab. Comput. 1 (1992), 123–134.10.1017/S0963548300000146Google Scholar | DOI
[18] , , and , ‘An exponential improvement for diagonal Ramsey’, Preprint, .Google Scholar | arXiv
[19] and , ‘Distributional and norm inequalities for polynomials over convex bodies in ’, Math. Res. Lett. 8 (2001), 233–248.10.4310/MRL.2001.v8.n3.a1Google Scholar | DOI
[20] and , ‘Explicit two-source extractors and resilient functions’, in STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (ACM, New York, 2016), 670–683.Google Scholar
[21] , ‘A note on constructive methods for Ramsey numbers’, J. Graph Theory 5 (1981), 109–113.10.1002/jgt.3190050109Google Scholar | DOI
[22] , ‘Open problems of Paul Erdős in graph theory’, J. Graph Theory 25 (1997), 3–36.10.1002/(SICI)1097-0118(199705)25:1<3::AID-JGT1>3.0.CO;2-RGoogle Scholar | DOI
[23] and , Erdős on Graphs (A. K. Peters, Ltd., Wellesley, MA, 1998), His legacy of unsolved problems. Google Scholar
[24] , ‘Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs’, in STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (ACM, New York, 2016), 278–284.Google Scholar
[25] and , ‘Graph removal lemmas’, in Surveys in Combinatorics 2013, London Math. Soc. Lecture Note Ser., vol. 409 (Cambridge Univ. Press, Cambridge, 2013), 1–49.Google Scholar
[26] , ‘Bilinear and quadratic variants on the Littlewood-Offord problem’, Israel J. Math. 194 (2013), 359–394.10.1007/s11856-012-0082-4Google Scholar | DOI
[27] , and , ‘Random symmetric matrices are almost surely nonsingular’, Duke Math. J. 135 (2006), 395–413.10.1215/S0012-7094-06-13527-5Google Scholar | DOI
[28] , ‘From dependence to complete independence: the decoupling approach’, in Fourth Symposium on Probability Theory and Stochastic Processes (Spanish) (Guanajuato, 1996), Aportaciones Mat. Notas Investigación, vol. 12 (Soc. Mat. Mexicana, México, 1996), 37–48.Google Scholar
[29] , and , ‘On the directions determined by a Cartesian product in an affine Galois plane’, Combinatorica 41 (2021), 755–763.10.1007/s00493-020-4516-zGoogle Scholar | DOI
[30] , Probability—Theory and Examples, fifth edn., Cambridge Series in Statistical and Probabilistic Mathematics, vol. 49 (Cambridge University Press, Cambridge, 2019).10.1017/9781108591034Google Scholar | DOI
[31] and , ‘The approximation of one matrix by another of lower rank’, Psychometrika 1 (1936), 211–218.10.1007/BF02288367Google Scholar | DOI
[32] , ‘On a lemma of Littlewood and Offord’, Bull. Amer. Math. Soc. 51 (1945), 898–902.10.1090/S0002-9904-1945-08454-7Google Scholar | DOI
[33] , ‘Some remarks on the theory of graphs’, Bull. Amer. Math. Soc. 53 (1947), 292–294.10.1090/S0002-9904-1947-08785-1Google Scholar | DOI
[34] , ‘Some of my favourite problems in various branches of combinatorics’, Combinatorics 92 (Catania, 1992), Matematiche (Catania) 47 (1992), 231–240 (1993).Google Scholar
[35] , ‘Some of my favourite problems in number theory, combinatorics, and geometry’, Resenhas 2 (1995), 165–186, Combinatorics Week (Portuguese) (São Paulo, 1994).Google Scholar
[36] , ‘Some recent problems and results in graph theory’, The Second Krakow Conference on Graph Theory (Zgorzelisko, 1994), Discrete Math. 164 (1997), 81–85.Google Scholar
[37] and , ‘On spanned subgraphs of graphs’, Contributions to Graph Theory and Its Applications (Internat. Colloq., Oberhof, 1977) (Tech. Hochschule Ilmenau, Ilmenau, 1977), 80–96.Google Scholar
[38] and , ‘A combinatorial problem in geometry’, Compositio Math. 2 (1935), 463–470.Google Scholar
[39] and , ‘On a Ramsey type theorem’, Period. Math. Hungar. 2 (1972), 295–299.10.1007/BF02018669Google Scholar | DOI
[40] and , ‘A generalized switching method for combinatorial estimation’, Australas. J. Combin. 39 (2007), 141–154.Google Scholar
[41] , and , ‘On the number of Hadamard matrices via anti-concentration’, Combin. Probab. Comput. 31 (2022), 455–477.10.1017/S0963548321000377Google Scholar | DOI
[42] , , and , ‘Invariance principle on the slice’, ACM Trans. Comput. Theory 10 (2018), Art. 11, 37.Google Scholar
[43] and , ‘Harmonicity and invariance on slices of the Boolean cube’, Probab. Theory Related Fields 175 (2019), 721–782.10.1007/s00440-019-00900-wGoogle Scholar | DOI
[44] , and , ‘Combinatorial anti-concentration inequalities, with applications’, Math. Proc. Cambridge Philos. Soc. 171 (2021), 227–248.10.1017/S0305004120000183Google Scholar | DOI
[45] and , ‘’A completion of the proof of the edge-statistics conjecture, Adv. Comb. (2020), Paper No. 4, 52.Google Scholar
[46] and , ‘Dependent random choice’, Random Structures Algorithms 38 (2011), 68–99.10.1002/rsa.20344Google Scholar | DOI
[47] and , ‘Intersection theorems with geometric consequences’, Combinatorica 1 (1981), 357–368.10.1007/BF02579457Google Scholar | DOI
[48] , ‘A constructive lower bound for some Ramsey numbers’, Ars Combin. 3 (1977), 297–302.Google Scholar
[49] and , Stochastic Finite Elements: A Spectral Approach (Springer-Verlag, New York, 1991).10.1007/978-1-4612-3094-6Google Scholar | DOI
[50] and , A local central limit theorem for triangles in a random graph , Random Structures Algorithms 48 (2016), 732–750.10.1002/rsa.20604Google Scholar | DOI
[51] , ‘On a local limit theorem of the theory of probability’, Uspekhi Matematicheskikh Nauk 3 (1948), 187–194.Google Scholar
[52] , ‘Constructing Ramsey graphs from Boolean function representations’, Combinatorica 34 (2014), 173–206.10.1007/s00493-014-2367-1Google Scholar | DOI
[53] , , and , ‘The average number of spanning trees in sparse graphs with given degrees’, European J. Combin. 63 (2017), 6–25.10.1016/j.ejc.2017.02.003Google Scholar | DOI
[54] , ‘Decoupling estimates in Fourier analysis’, Preprint, .Google Scholar | arXiv
[55] , ‘Estimates for the concentration function of combinatorial number theory and probability’, Period. Math. Hungar. 8 (1977), 197–211.10.1007/BF02018403Google Scholar | DOI
[56] and , ‘Refined estimates concerning sumsets contained in the roots of unity’, Proc. Lond. Math. Soc. (3) 122 (2021), 353–358.10.1112/plms.12322Google Scholar | DOI
[57] and , ‘A bound on tail probabilities for quadratic forms in independent random variables’, Ann. Math. Statist. 42 (1971), 1079–1083.10.1214/aoms/1177693335Google Scholar | DOI
[58] and , ‘Combinatorial estimates by the switching method’, in Combinatorics and Graphs, Contemp. Math., vol. 531 (Amer. Math. Soc., Providence, RI, 2010), 209–221.10.1090/conm/531/10469Google Scholar | DOI
[59] , and , Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (Wiley-Interscience, New York, 2000).10.1002/9781118032718Google Scholar | DOI
[60] , , and , ‘Distinct degrees in induced subgraphs’, Proc. Amer. Math. Soc. 148 (2020), 3835–3846.10.1090/proc/15060Google Scholar | DOI
[61] , ‘A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions’, Ann. Probab. 45 (2017), 1612–1679.10.1214/16-AOP1097Google Scholar | DOI
[62] and , ‘Concentration of multivariate polynomials and its applications’, Combinatorica 20 (2000), 417–434.10.1007/s004930070014Google Scholar | DOI
[63] and , ‘Pseudo-random graphs’, in More Sets, Graphs and Numbers, Bolyai Soc. Math. Stud., vol. 15 (Springer, Berlin, 2006), 199–262.10.1007/978-3-540-32439-3_10Google Scholar | DOI
[64] , and , ‘Probabilistic existence of regular combinatorial structures’, Geom. Funct. Anal. 27 (2017), 919–972.10.1007/s00039-017-0416-9Google Scholar | DOI
[65] and , ‘An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs’, Discrete Anal. (2020), Paper No. 12, 34.Google Scholar
[66] and , ‘Proof of a conjecture on induced subgraphs of Ramsey graphs’, Trans. Amer. Math. Soc. 372 (2019), 5571–5594.10.1090/tran/7729Google Scholar | DOI
[67] and , ‘Ramsey graphs induce subgraphs of quadratically many sizes’, Int. Math. Res. Not. IMRN (2020), 1621–1638.10.1093/imrn/rny064Google Scholar | DOI
[68] , and , ‘Anticoncentration for subgraph statistics’, J. Lond. Math. Soc. (2) 99 (2019), 757–777.10.1112/jlms.12192Google Scholar | DOI
[69] , , and , ‘A sub-Gaussian Berry-Esseen theorem for the hypergeometric distribution’, Preprint, .Google Scholar | arXiv
[70] , , and , ‘The complexity of proving that a graph is Ramsey’, Combinatorica 37 (2017), 253–268.10.1007/s00493-015-3193-9Google Scholar | DOI
[71] , ‘Non-malleable extractors and non-malleable codes: partially optimal constructions’, in 34th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 137 (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019), Art. No. 28, 49.Google Scholar
[72] and , ‘A bipartite version of the Erdős-McKay conjecture’, Combin. Probab. Comput. 32 (2023), 465–477.10.1017/S0963548322000347Google Scholar | DOI
[73] , , and , ‘The edge-statistics conjecture for ’, Israel J. Math. 234 (2019), 677–690.10.1007/s11856-019-1929-8Google Scholar | DOI
[74] , and , ‘Noise stability of functions with low influences: invariance and optimality’, Ann. of Math. (2) 171 (2010), 295–341.10.4007/annals.2010.171.295Google Scholar | DOI
[75] , ‘A certain constructive estimate of the Ramsey number’, Mat. Lapok 23 (1972), 301–302 (1974).Google Scholar
[76] , and , ‘Ramsey graphs induce subgraphs of many different sizes’, Combinatorica 39 (2019), 215–237.10.1007/s00493-017-3755-0Google Scholar | DOI
[77] , ‘Inverse Littlewood–Offord problems and the singularity of random symmetric matrices’, Duke Math. J. 161 (2012), 545–586.10.1215/00127094-1548344Google Scholar | DOI
[78] and , ‘Optimal inverse Littlewood–Offord theorems’, Adv. Math. 226 (2011), 5298–5319.10.1016/j.aim.2011.01.005Google Scholar | DOI
[79] and , Small Ball Probability, Inverse Theorems, and Applications, Erdős Centennial, Bolyai Soc. Math. Stud., vol. 25 (János Bolyai Math. Soc., Budapest, 2013), 409–463.Google Scholar
[80] and , On Rank vs. Communication Complexity, 35th Annual Symposium on Foundations of Computer Science (Santa Fe, NM, 1994) (IEEE Comput. Soc. Press, Los Alamitos, CA, 1994), 831–836.Google Scholar
[81] , Analysis of Boolean Functions (Cambridge University Press, New York, 2014).10.1017/CBO9781139814782Google Scholar | DOI
[82] , ‘The non-central - and -distribution and their applications’, Biometrika 36 (1949), 202–232.Google Scholar
[83] , Sums of Independent Random Variables, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 82 (Springer-Verlag, New York-Heidelberg, 1975). Translated from the Russian by .Google Scholar
[84] and , ‘Non-Ramsey graphs are -universal’, J. Combin. Theory Ser. A 88 (1999), 379–384.10.1006/jcta.1999.2972Google Scholar | DOI
[85] , ‘New inequalities for permanents and hafnians and some generalizations’, Preprint, .Google Scholar | arXiv
[86] , ‘Recent developments in non-asymptotic theory of random matrices’, in Modern Aspects of Random Matrix Theory, Proc. Sympos. Appl. Math., vol. 72 (Amer. Math. Soc., Providence, RI, 2014), 83–120.10.1090/psapm/072/00616Google Scholar | DOI
[87] and , ‘The Littlewood–Offord problem and invertibility of random matrices’, Adv. Math. 218 (2008), 600–633.10.1016/j.aim.2008.01.010Google Scholar | DOI
[88] and , Local Limit Theorems for Subgraph Counts (2022), 950–1011.Google Scholar
[89] , ‘An introduction to randomness extractors’, in Automata, Languages and Programming, Part II, Lecture Notes in Comput. Sci., vol. 6756 (Springer, Heidelberg, 2011), 21–41.10.1007/978-3-642-22012-8_2Google Scholar | DOI
[90] , ‘Erdős and Rényi conjecture’, J. Combin. Theory Ser. A 82 (1998), 179–185.10.1006/jcta.1997.2845Google Scholar | DOI
[91] and , ‘A sharp inverse Littlewood–Offord theorem’, Random Structures Algorithms 37 (2010), 525–539.10.1002/rsa.20327Google Scholar | DOI
[92] and , ‘Inverse Littlewood–Offord theorems and the condition number of random discrete matrices’, Ann. of Math. (2) 169 (2009), 595–632.10.4007/annals.2009.169.595Google Scholar | DOI
[93] and , Additive Combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105 (Cambridge University Press, Cambridge, 2010).Google Scholar
[94] , ‘Random walks in Euclidean space’, Ann. of Math. (2) (2015), 243–301.10.4007/annals.2015.181.1.4Google Scholar | DOI
[95] , ‘Invertibility of symmetric random matrices’, Random Structures Algorithms 44 (2014), 135–182.10.1002/rsa.20429Google Scholar | DOI
Cité par Sources :