[{"title":"Smoothed analysis for graph isomorphism","month":"06","department":[{"_id":"MaKw"}],"date_updated":"2025-07-14T06:33:50Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"doi":"10.1145/3717823.3718173","publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"article_processing_charge":"Yes (via OA deal)","publisher":"Association for Computing Machinery","publication_status":"published","citation":{"apa":"Anastos, M., Kwan, M. A., &#38; Moore, B. (2025). Smoothed analysis for graph isomorphism. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>","short":"M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2098–2106.","chicago":"Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis for Graph Isomorphism.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 2098–2106. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>.","ama":"Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:2098-2106. doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>","ista":"Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 2098–2106.","mla":"Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 2098–106, doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>.","ieee":"M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 2098–2106."},"date_published":"2025-06-15T00:00:00Z","year":"2025","OA_type":"hybrid","conference":{"end_date":"2025-06-27","name":"STOC: Symposium on Theory of Computing","start_date":"2025-06-23","location":"Prague, Czechia"},"abstract":[{"lang":"eng","text":"There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial “refinement” algorithms seem to be very efficient in practice. Some philosophical justification for this phenomenon is provided by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”) yields a so-called canonical labelling scheme for “almost all graphs”. More precisely, for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph."}],"project":[{"name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777"},{"grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"},{"_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","name":"Combinatorial Optimisation Problems on Sparse Random Graphs","grant_number":"ESP3863424"}],"quality_controlled":"1","external_id":{"arxiv":["2410.06095"]},"ec_funded":1,"oa_version":"Published Version","day":"15","type":"conference","author":[{"first_name":"Michael","last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567"},{"first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin","last_name":"Moore"}],"acknowledgement":"All authors were supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Michael Anastos was also supported in part by the Austrian Science Fund (FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. For Open Access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","file_date_updated":"2025-07-14T06:13:10Z","arxiv":1,"OA_place":"publisher","_id":"20007","oa":1,"page":"2098-2106","ddc":["000"],"file":[{"access_level":"open_access","success":1,"file_size":706445,"relation":"main_file","date_created":"2025-07-14T06:13:10Z","checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","creator":"dernst","file_id":"20012","file_name":"2025_STOC_Anastos.pdf","date_updated":"2025-07-14T06:13:10Z","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","has_accepted_license":"1","status":"public","date_created":"2025-07-13T22:01:23Z","scopus_import":"1"},{"article_processing_charge":"Yes (via OA deal)","publication_identifier":{"issn":["1073-7928"],"eissn":["1687-0247"]},"publisher":"Oxford University Press","doi":"10.1093/imrn/rnaf273","publication_status":"published","year":"2025","date_published":"2025-09-11T00:00:00Z","citation":{"chicago":"Jain, Vishesh, Matthew Alan Kwan, Dhruv Mubayi, and Tuan Tran. “The Edge-Statistics Conjecture for Hypergraphs.” <i>International Mathematics Research Notices</i>. Oxford University Press, 2025. <a href=\"https://doi.org/10.1093/imrn/rnaf273\">https://doi.org/10.1093/imrn/rnaf273</a>.","ama":"Jain V, Kwan MA, Mubayi D, Tran T. The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. 2025;2025(18). doi:<a href=\"https://doi.org/10.1093/imrn/rnaf273\">10.1093/imrn/rnaf273</a>","apa":"Jain, V., Kwan, M. A., Mubayi, D., &#38; Tran, T. (2025). The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rnaf273\">https://doi.org/10.1093/imrn/rnaf273</a>","short":"V. Jain, M.A. Kwan, D. Mubayi, T. Tran, International Mathematics Research Notices 2025 (2025).","mla":"Jain, Vishesh, et al. “The Edge-Statistics Conjecture for Hypergraphs.” <i>International Mathematics Research Notices</i>, vol. 2025, no. 18, rnaf273, Oxford University Press, 2025, doi:<a href=\"https://doi.org/10.1093/imrn/rnaf273\">10.1093/imrn/rnaf273</a>.","ieee":"V. Jain, M. A. Kwan, D. Mubayi, and T. Tran, “The edge-statistics conjecture for hypergraphs,” <i>International Mathematics Research Notices</i>, vol. 2025, no. 18. Oxford University Press, 2025.","ista":"Jain V, Kwan MA, Mubayi D, Tran T. 2025. The edge-statistics conjecture for hypergraphs. International Mathematics Research Notices. 2025(18), rnaf273."},"article_number":"rnaf273","isi":1,"title":"The edge-statistics conjecture for hypergraphs","date_updated":"2025-12-01T13:00:35Z","month":"09","department":[{"_id":"MaKw"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"quality_controlled":"1","external_id":{"isi":["001575137400001"],"arxiv":["2505.03954"]},"project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"volume":2025,"oa_version":"Published Version","day":"11","OA_type":"hybrid","article_type":"original","abstract":[{"text":"Let r, k,  be integers such that 0 ≤  ≤ (k/r). Given a large r-uniform hypergraph G, we consider the\r\nfraction of k-vertex subsets that span exactly  edges. If  is 0 or (k/r), this fraction can be exactly 1 (by taking G to be empty or complete), but for all other values of , one might suspect that this fraction is always significantly smaller than 1.\r\nIn this paper we prove an essentially optimal result along these lines: if  is not 0 or (k/r), then this\r\nfraction is at most (1/e) + ε, assuming k is sufficiently large in terms of r and ε > 0, and G is sufficiently large in terms of k. Previously, this was only known for a very limited range of values of r, k,  (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujic). Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested this as a hypergraph generalization of their edge-statistics conjecture. We also prove a much stronger bound when  is far from 0 and (k/r).","lang":"eng"}],"arxiv":1,"_id":"20504","OA_place":"publisher","oa":1,"acknowledgement":"This work was supported by NSF CAREER award DMS-2237646 [to V.J.], ERC Starting Grant “RANDSTRUCT” [no. 101076777 to M.K.], NSF grant DMS-2153576 [to D.M.], and the National Key Research and Development Program of China [2023YFA101020 to T.T.].\r\nWe would like to thank Lisa Sauermann for her helpful comments. We would also like to thank Alex Grebennikov for identifying an oversight in the application of Theorem 7.1 (in a previous version of this paper).","author":[{"full_name":"Jain, Vishesh","last_name":"Jain","first_name":"Vishesh"},{"last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567"},{"first_name":"Dhruv","last_name":"Mubayi","full_name":"Mubayi, Dhruv"},{"first_name":"Tuan","full_name":"Tran, Tuan","last_name":"Tran"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","corr_author":"1","issue":"18","file_date_updated":"2025-10-21T07:36:56Z","publication":"International Mathematics Research Notices","PlanS_conform":"1","language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","scopus_import":"1","date_created":"2025-10-20T11:08:57Z","intvolume":"      2025","ddc":["510"],"file":[{"creator":"dernst","file_id":"20511","content_type":"application/pdf","file_name":"2025_IMRN_Jain.pdf","date_updated":"2025-10-21T07:36:56Z","file_size":774323,"relation":"main_file","success":1,"access_level":"open_access","checksum":"016aa4df9453dc180ae7504ac77bf72f","date_created":"2025-10-21T07:36:56Z"}]},{"ddc":["510"],"file":[{"content_type":"application/pdf","date_updated":"2025-04-16T09:16:25Z","file_name":"2025_EuropJournCombinatorics_Carbonero.pdf","creator":"dernst","file_id":"19577","checksum":"2c75f78f40ebb93d16fe3765bda2905a","date_created":"2025-04-16T09:16:25Z","relation":"main_file","file_size":1110657,"success":1,"access_level":"open_access"}],"intvolume":"       125","date_created":"2025-01-05T23:01:55Z","status":"public","scopus_import":"1","publication":"European Journal of Combinatorics","language":[{"iso":"eng"}],"has_accepted_license":"1","corr_author":"1","file_date_updated":"2025-04-16T09:16:25Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We thank the anonymous referees for their careful proofreading which helped improve the presentation of this paper. We also thank one of the anonymous referees for pointing out our construction implies Theorem 1.7!\r\nBenjamin Moore finished this project while a postdoctoral researcher at Charles University, and was supported by project 22-17398S (Flows and cycles in graphs on surfaces) of the Czech Science Foundation. Benjamin Moore is currently funded by RANDSTRUCT No. 101076777, and appreciates the gracious support. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912]. This project was funded in part by the Government of Ontario .","author":[{"first_name":"Alvaro","last_name":"Carbonero","full_name":"Carbonero, Alvaro"},{"full_name":"Koerts, Hidde","last_name":"Koerts","first_name":"Hidde"},{"id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin","last_name":"Moore","first_name":"Benjamin"},{"first_name":"Sophie","full_name":"Spirkl, Sophie","last_name":"Spirkl"}],"type":"journal_article","oa":1,"arxiv":1,"_id":"18753","OA_place":"publisher","article_type":"original","abstract":[{"text":"We continue a line of research which studies which hereditary families of digraphs have bounded dichromatic number. For a class of digraphs  C, a hero in  C  is any digraph  H\r\n  such that  H -free digraphs in  C  have bounded dichromatic number. We show that if  F\r\n  is an oriented star of degree at least five, the only heroes for the class of  F -free digraphs are transitive tournaments. For oriented stars  F  of degree exactly four, we show the only heroes in  F -free digraphs are transitive tournaments, or possibly special joins of transitive tournaments. Aboulker et al. characterized the set of heroes of  {H,K1+P2→} -free digraphs almost completely, and we show the same characterization for the class of  {H,rK1+P3→} -free digraphs. Lastly, we show that if we forbid two \"valid\" orientations of brooms, then every transitive tournament is a hero for this class of digraphs.","lang":"eng"}],"OA_type":"hybrid","day":"01","oa_version":"Published Version","volume":125,"external_id":{"arxiv":["2306.04710"],"isi":["001400113700001"]},"quality_controlled":"1","project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"date_updated":"2025-05-19T14:06:00Z","department":[{"_id":"MaKw"}],"month":"03","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"isi":1,"article_number":"104104","title":"On heroes in digraphs with forbidden induced forests","date_published":"2025-03-01T00:00:00Z","year":"2025","citation":{"ista":"Carbonero A, Koerts H, Moore B, Spirkl S. 2025. On heroes in digraphs with forbidden induced forests. European Journal of Combinatorics. 125, 104104.","ieee":"A. Carbonero, H. Koerts, B. Moore, and S. Spirkl, “On heroes in digraphs with forbidden induced forests,” <i>European Journal of Combinatorics</i>, vol. 125. Elsevier, 2025.","mla":"Carbonero, Alvaro, et al. “On Heroes in Digraphs with Forbidden Induced Forests.” <i>European Journal of Combinatorics</i>, vol. 125, 104104, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">10.1016/j.ejc.2024.104104</a>.","short":"A. Carbonero, H. Koerts, B. Moore, S. Spirkl, European Journal of Combinatorics 125 (2025).","apa":"Carbonero, A., Koerts, H., Moore, B., &#38; Spirkl, S. (2025). On heroes in digraphs with forbidden induced forests. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">https://doi.org/10.1016/j.ejc.2024.104104</a>","ama":"Carbonero A, Koerts H, Moore B, Spirkl S. On heroes in digraphs with forbidden induced forests. <i>European Journal of Combinatorics</i>. 2025;125. doi:<a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">10.1016/j.ejc.2024.104104</a>","chicago":"Carbonero, Alvaro, Hidde Koerts, Benjamin Moore, and Sophie Spirkl. “On Heroes in Digraphs with Forbidden Induced Forests.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2024.104104\">https://doi.org/10.1016/j.ejc.2024.104104</a>."},"publisher":"Elsevier","article_processing_charge":"Yes (in subscription journal)","publication_identifier":{"issn":["0195-6698"]},"doi":"10.1016/j.ejc.2024.104104","publication_status":"published"},{"corr_author":"1","file_date_updated":"2025-04-03T11:24:35Z","type":"journal_article","acknowledgement":"We would like to thank Timo Seppäläinen for some illuminating discussion about random high-dimensional orders and for bringing our attention to [59]. We would also like to thank the referees for helpful feedback. Michael Anastos is supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. Matthew Kwan is supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777, also funded by the European Union. Zhihan Jin and Benny Sudakov are supported by SNSF grant 200021-228014.","author":[{"full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","first_name":"Michael"},{"full_name":"Jin, Zhihan","last_name":"Jin","first_name":"Zhihan"},{"full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan"},{"first_name":"Benny","last_name":"Sudakov","full_name":"Sudakov, Benny"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"arxiv":1,"OA_place":"publisher","_id":"19433","ddc":["510"],"file":[{"date_created":"2025-04-03T11:24:35Z","checksum":"f396270ad78c1ed67095c8e5a66fca26","access_level":"open_access","success":1,"relation":"main_file","file_size":630297,"date_updated":"2025-04-03T11:24:35Z","file_name":"2025_ForumMathSigma_Anastos.pdf","content_type":"application/pdf","creator":"dernst","file_id":"19468"}],"intvolume":"        13","date_created":"2025-03-20T12:59:14Z","status":"public","scopus_import":"1","language":[{"iso":"eng"}],"publication":"Forum of Mathematics, Sigma","has_accepted_license":"1","month":"03","department":[{"_id":"MaKw"}],"date_updated":"2025-09-30T11:18:57Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"isi":1,"article_number":"e55","title":"Extremal, enumerative and probabilistic results on ordered hypergraph matchings","citation":{"chicago":"Anastos, Michael, Zhihan Jin, Matthew Alan Kwan, and Benny Sudakov. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2025. <a href=\"https://doi.org/10.1017/fms.2024.144\">https://doi.org/10.1017/fms.2024.144</a>.","ama":"Anastos M, Jin Z, Kwan MA, Sudakov B. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. <i>Forum of Mathematics, Sigma</i>. 2025;13. doi:<a href=\"https://doi.org/10.1017/fms.2024.144\">10.1017/fms.2024.144</a>","apa":"Anastos, M., Jin, Z., Kwan, M. A., &#38; Sudakov, B. (2025). Extremal, enumerative and probabilistic results on ordered hypergraph matchings. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2024.144\">https://doi.org/10.1017/fms.2024.144</a>","short":"M. Anastos, Z. Jin, M.A. Kwan, B. Sudakov, Forum of Mathematics, Sigma 13 (2025).","mla":"Anastos, Michael, et al. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” <i>Forum of Mathematics, Sigma</i>, vol. 13, e55, Cambridge University Press, 2025, doi:<a href=\"https://doi.org/10.1017/fms.2024.144\">10.1017/fms.2024.144</a>.","ieee":"M. Anastos, Z. Jin, M. A. Kwan, and B. Sudakov, “Extremal, enumerative and probabilistic results on ordered hypergraph matchings,” <i>Forum of Mathematics, Sigma</i>, vol. 13. Cambridge University Press, 2025.","ista":"Anastos M, Jin Z, Kwan MA, Sudakov B. 2025. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 13, e55."},"year":"2025","date_published":"2025-03-14T00:00:00Z","doi":"10.1017/fms.2024.144","article_processing_charge":"Yes","publication_identifier":{"issn":["2050-5094"]},"publisher":"Cambridge University Press","publication_status":"published","article_type":"original","abstract":[{"lang":"eng","text":"An ordered r-matching is an r-uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of r-dimensional orders. The theory of ordered 2-matchings is well developed and has connections and applications to extremal and enumerative combinatorics, probability and geometry. On the other hand, in the case  r≥3 much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński made some first steps towards a general theory of ordered r-matchings, and in this paper we substantially improve several of their results and introduce some new directions of study. Many intriguing open questions remain."}],"OA_type":"gold","ec_funded":1,"day":"14","volume":13,"oa_version":"Published Version","project":[{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"},{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"quality_controlled":"1","external_id":{"isi":["001444429200001"],"arxiv":["2308.12268"]}},{"date_created":"2025-04-13T22:01:19Z","scopus_import":"1","status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"Journal of the London Mathematical Society","file":[{"file_id":"19564","creator":"dernst","file_name":"2025_JourLondMathSoc_Glasgow.pdf","date_updated":"2025-04-15T13:18:43Z","content_type":"application/pdf","success":1,"access_level":"open_access","relation":"main_file","file_size":392208,"date_created":"2025-04-15T13:18:43Z","checksum":"69ce9feaf64e776b99f3afd1041b1b11"}],"ddc":["510"],"intvolume":"       111","oa":1,"OA_place":"publisher","_id":"19554","arxiv":1,"file_date_updated":"2025-04-15T13:18:43Z","issue":"4","corr_author":"1","type":"journal_article","author":[{"first_name":"Margalit","last_name":"Glasgow","full_name":"Glasgow, Margalit"},{"last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan"},{"first_name":"Ashwin","last_name":"Sah","full_name":"Sah, Ashwin"},{"last_name":"Sawhney","full_name":"Sawhney, Mehtaab","first_name":"Mehtaab"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","acknowledgement":"We would like to thank Christina Goldschmidt and Eleonora Kreačić for insightful discussions and clarifications about their work in the thesis [26]. Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777. Ashwin Sah and Mehtaab Sawhney were supported by NSF Graduate Research Fellowship Program DGE-2141064. Ashwin Sah was supported by the PD Soros Fellowship.\r\nOpen access funding provided by Institute of Science and Technology Austria/KEMÖ.","volume":111,"oa_version":"Published Version","day":"01","project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"external_id":{"isi":["001473087200024"],"arxiv":["2402.05851"]},"quality_controlled":"1","abstract":[{"text":"In 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erdős–Rényi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthening this classical result, and answering a question of Aronson, Frieze and Pittel, we prove a central limit theorem in the same setting: the fluctuations in the matching number of a sparse random graph are asymptotically Gaussian. Our new contribution is to prove this central limit theorem in the subcritical and critical regimes, according to a celebrated algorithmic phase transition first observed by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem has recently been proved in the PhD thesis of Kreačić, using a stochastic generalisation of the differential equation method (comparing the so-called Karp–Sipser process to a system of stochastic differential equations). Our proof builds on these methods, and introduces new techniques to handle certain degeneracies present in the subcritical and critical cases. Curiously, our new techniques lead to a non-constructive result: we are able to characterise the fluctuations of the matching number around its mean, despite these fluctuations being much smaller than the error terms in our best estimates of the mean. We also prove a central limit theorem for the rank of the adjacency matrix of a sparse random graph.","lang":"eng"}],"article_type":"original","OA_type":"hybrid","citation":{"chicago":"Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney. “A Central Limit Theorem for the Matching Number of a Sparse Random Graph.” <i>Journal of the London Mathematical Society</i>. Wiley, 2025. <a href=\"https://doi.org/10.1112/jlms.70101\">https://doi.org/10.1112/jlms.70101</a>.","ama":"Glasgow M, Kwan MA, Sah A, Sawhney M. A central limit theorem for the matching number of a sparse random graph. <i>Journal of the London Mathematical Society</i>. 2025;111(4). doi:<a href=\"https://doi.org/10.1112/jlms.70101\">10.1112/jlms.70101</a>","apa":"Glasgow, M., Kwan, M. A., Sah, A., &#38; Sawhney, M. (2025). A central limit theorem for the matching number of a sparse random graph. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70101\">https://doi.org/10.1112/jlms.70101</a>","short":"M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the London Mathematical Society 111 (2025).","mla":"Glasgow, Margalit, et al. “A Central Limit Theorem for the Matching Number of a Sparse Random Graph.” <i>Journal of the London Mathematical Society</i>, vol. 111, no. 4, e70101, Wiley, 2025, doi:<a href=\"https://doi.org/10.1112/jlms.70101\">10.1112/jlms.70101</a>.","ieee":"M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “A central limit theorem for the matching number of a sparse random graph,” <i>Journal of the London Mathematical Society</i>, vol. 111, no. 4. Wiley, 2025.","ista":"Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. A central limit theorem for the matching number of a sparse random graph. Journal of the London Mathematical Society. 111(4), e70101."},"date_published":"2025-04-01T00:00:00Z","year":"2025","publication_status":"published","doi":"10.1112/jlms.70101","article_processing_charge":"Yes (via OA deal)","publication_identifier":{"eissn":["1469-7750"],"issn":["0024-6107"]},"publisher":"Wiley","tmp":{"image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)"},"license":"https://creativecommons.org/licenses/by-nc/4.0/","department":[{"_id":"MaKw"}],"month":"04","date_updated":"2025-09-30T11:35:55Z","title":"A central limit theorem for the matching number of a sparse random graph","article_number":"e70101","isi":1},{"title":"The exact rank of sparse random graphs","department":[{"_id":"MaKw"}],"month":"09","date_updated":"2026-02-23T10:44:41Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"doi":"10.4171/jems/1692","publisher":"European Mathematical Society Press","article_processing_charge":"No","publication_identifier":{"issn":["1435-9855"],"eissn":["1435-9863"]},"publication_status":"epub_ahead","citation":{"apa":"Glasgow, M., Kwan, M. A., Sah, A., &#38; Sawhney, M. (2025). The exact rank of sparse random graphs. <i>Journal of the European Mathematical Society</i>. European Mathematical Society Press. <a href=\"https://doi.org/10.4171/jems/1692\">https://doi.org/10.4171/jems/1692</a>","short":"M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the European Mathematical Society (2025).","chicago":"Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney. “The Exact Rank of Sparse Random Graphs.” <i>Journal of the European Mathematical Society</i>. European Mathematical Society Press, 2025. <a href=\"https://doi.org/10.4171/jems/1692\">https://doi.org/10.4171/jems/1692</a>.","ama":"Glasgow M, Kwan MA, Sah A, Sawhney M. The exact rank of sparse random graphs. <i>Journal of the European Mathematical Society</i>. 2025. doi:<a href=\"https://doi.org/10.4171/jems/1692\">10.4171/jems/1692</a>","ista":"Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. The exact rank of sparse random graphs. Journal of the European Mathematical Society.","mla":"Glasgow, Margalit, et al. “The Exact Rank of Sparse Random Graphs.” <i>Journal of the European Mathematical Society</i>, European Mathematical Society Press, 2025, doi:<a href=\"https://doi.org/10.4171/jems/1692\">10.4171/jems/1692</a>.","ieee":"M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “The exact rank of sparse random graphs,” <i>Journal of the European Mathematical Society</i>. European Mathematical Society Press, 2025."},"date_published":"2025-09-02T00:00:00Z","year":"2025","OA_type":"diamond","article_type":"original","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4171/JEMS/1692"}],"abstract":[{"lang":"eng","text":"Two landmark results in combinatorial random matrix theory, due to Komlós and Costello–Tao–Vu, show that discrete random matrices and symmetric discrete random matrices are typically nonsingular. In particular, in the language of graph theory, when p is a fixed constant, the biadjacency matrix of a random Erdős–Rényi bipartite graph G(n,n,p) and the adjacency matrix of an Erdős–Rényi random graph G(n,p) are both nonsingular with high probability. However, very sparse random graphs (i.e., where p is allowed to decay rapidly with n) are typically singular, due to the presence of “local” dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbour. In this paper, we give a combinatorial description of the rank of a sparse random graph G(n,n,c/n) or G(n,c/n) in terms of such local dependencies, for all constants c=e (and we present some evidence that the situation is very different for c=e). This gives an essentially complete answer to a question raised by Vu (2014). As applications of our main theorem and its proof, we also determine the asymptotic singularity probability of the 2-core of a sparse random graph, we show that the rank of a sparse random graph is extremely well approximated by its matching number, and we deduce a central limit theorem for the rank of G(n,c/n)."}],"project":[{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"external_id":{"arxiv":["2303.05435"]},"quality_controlled":"1","day":"02","oa_version":"Published Version","type":"journal_article","acknowledgement":"We would like to thank Noga Alon for suggesting that our main result gives\r\na linear-time algorithm for computing the rank. We also thank the referees for a number of thoughtful comments and suggestions. Glasgow was supported by NSF graduate research fellowship program award DGE1656518. Kwan was supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302.\r\n","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Margalit","full_name":"Glasgow, Margalit","last_name":"Glasgow"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Ashwin","full_name":"Sah, Ashwin","last_name":"Sah"},{"full_name":"Sawhney, Mehtaab","last_name":"Sawhney","first_name":"Mehtaab"}],"corr_author":"1","arxiv":1,"DOAJ_listed":"1","OA_place":"publisher","_id":"21263","oa":1,"ddc":["510"],"language":[{"iso":"eng"}],"PlanS_conform":"1","publication":"Journal of the European Mathematical Society","has_accepted_license":"1","date_created":"2026-02-17T07:41:59Z","status":"public"},{"type":"journal_article","acknowledgement":"We are grateful to the anonymous referees for their thorough reading of the paper, and for many suggestions which have improved the exposition throughout.\r\n\r\nMichael Anastos was supported by the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413. Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777, also funded by the European Union image. Mihyun Kang was supported in part by the Austrian Science Fund (FWF) [10.55776/I6502]. For the purpose of open access, the authors have applied a CC-BY public copyright licence to any Author Accepted Manuscript version arising from this submission.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"},{"id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","full_name":"Cooley, Oliver","last_name":"Cooley","first_name":"Oliver"},{"last_name":"Kang","full_name":"Kang, Mihyun","first_name":"Mihyun"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan"}],"file_date_updated":"2024-12-10T08:10:39Z","issue":"6","corr_author":"1","OA_place":"publisher","_id":"18583","arxiv":1,"oa":1,"intvolume":"       110","file":[{"creator":"dernst","file_id":"18639","content_type":"application/pdf","date_updated":"2024-12-10T08:10:39Z","file_name":"2024_JournLondonMathSoc_Anastos.pdf","file_size":539891,"relation":"main_file","success":1,"access_level":"open_access","checksum":"98e301e0565d75e3fb50e10e982a5018","date_created":"2024-12-10T08:10:39Z"}],"ddc":["510"],"has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"Journal of the London Mathematical Society","scopus_import":"1","date_created":"2024-11-24T23:01:48Z","status":"public","title":"Partitioning problems via random processes","isi":1,"article_number":"e70010","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"month":"12","department":[{"_id":"MaKw"}],"date_updated":"2025-12-02T13:52:26Z","publication_status":"published","doi":"10.1112/jlms.70010","article_processing_charge":"Yes (via OA deal)","publication_identifier":{"eissn":["1469-7750"],"issn":["0024-6107"]},"publisher":"Wiley","citation":{"ista":"Anastos M, Cooley O, Kang M, Kwan MA. 2024. Partitioning problems via random processes. Journal of the London Mathematical Society. 110(6), e70010.","ieee":"M. Anastos, O. Cooley, M. Kang, and M. A. Kwan, “Partitioning problems via random processes,” <i>Journal of the London Mathematical Society</i>, vol. 110, no. 6. Wiley, 2024.","mla":"Anastos, Michael, et al. “Partitioning Problems via Random Processes.” <i>Journal of the London Mathematical Society</i>, vol. 110, no. 6, e70010, Wiley, 2024, doi:<a href=\"https://doi.org/10.1112/jlms.70010\">10.1112/jlms.70010</a>.","short":"M. Anastos, O. Cooley, M. Kang, M.A. Kwan, Journal of the London Mathematical Society 110 (2024).","apa":"Anastos, M., Cooley, O., Kang, M., &#38; Kwan, M. A. (2024). Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70010\">https://doi.org/10.1112/jlms.70010</a>","ama":"Anastos M, Cooley O, Kang M, Kwan MA. Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. 2024;110(6). doi:<a href=\"https://doi.org/10.1112/jlms.70010\">10.1112/jlms.70010</a>","chicago":"Anastos, Michael, Oliver Cooley, Mihyun Kang, and Matthew Alan Kwan. “Partitioning Problems via Random Processes.” <i>Journal of the London Mathematical Society</i>. Wiley, 2024. <a href=\"https://doi.org/10.1112/jlms.70010\">https://doi.org/10.1112/jlms.70010</a>."},"year":"2024","date_published":"2024-12-01T00:00:00Z","OA_type":"hybrid","abstract":[{"text":"There are a number of well-known problems and conjectures about partitioning graphs to satisfy local constraints. For example, the majority colouring conjecture of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph has a 3-colouring such that for every vertex v, at most half of the out-neighbours of v have the same colour as \r\n. As another example, the internal partition conjecture, due to DeVos and to Ban and Linial, states that for every d, all but finitely many d-regular graphs have a partition into two non-empty parts such that for every vertex v, at least half of the neighbours of v lie in the same part as v. We prove several results in this spirit: in particular, two of our results are that the majority colouring conjecture holds for Erdős–Rényi random directed graphs (of any density), and that the internal partition conjecture holds if we permit a tiny number of ‘exceptional vertices’. Our proofs involve a variety of techniques, including several different methods to analyse random recolouring processes. One highlight is a personality-changing scheme: we ‘forget’ certain information based on the state of a Markov chain, giving us more independence to work with.","lang":"eng"}],"article_type":"original","project":[{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413"},{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics","grant_number":"101076777"}],"quality_controlled":"1","external_id":{"isi":["001374738100001"],"arxiv":["2307.06453"]},"volume":110,"day":"01","oa_version":"Published Version","ec_funded":1},{"OA_type":"hybrid","abstract":[{"text":"The inertia bound and ratio bound (also known as the Cvetković bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number α(G) of a graph G in terms of spectral information about a weighted adjacency matrix of G. For both inequalities, given a graph G, one needs to make a judicious choice of weighted adjacency matrix to obtain as strong a bound as possible.\r\nWhile there is a well-established theory surrounding the ratio bound, the inertia bound is much more mysterious, and its limits are rather unclear. In fact, only recently did Sinkovic find the first example of a graph for which the inertia bound is not tight (for any weighted adjacency matrix), answering a longstanding question of Godsil. We show that the inertia bound can be extremely far from tight, and in fact can significantly underperform the ratio bound: for example, one of our results is that for infinitely many n, there is an n-vertex graph for which even the unweighted ratio bound can prove α(G)≤4n3/4, but the inertia bound is always at least n/4. In particular, these results address questions of Rooney, Sinkovic, and Wocjan--Elphick--Abiad.","lang":"eng"}],"article_type":"original","quality_controlled":"1","external_id":{"isi":["001279563300001"],"arxiv":["2312.04925"]},"project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics","grant_number":"101076777"}],"oa_version":"Published Version","day":"01","volume":56,"title":"The inertia bound is far from tight","isi":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"date_updated":"2025-09-08T08:45:39Z","department":[{"_id":"MaKw"}],"month":"10","publication_status":"published","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"article_processing_charge":"Yes (via OA deal)","publisher":"London Mathematical Society","doi":"10.1112/blms.13127","date_published":"2024-10-01T00:00:00Z","year":"2024","citation":{"chicago":"Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society, 2024. <a href=\"https://doi.org/10.1112/blms.13127\">https://doi.org/10.1112/blms.13127</a>.","ama":"Kwan MA, Wigderson Y. The inertia bound is far from tight. <i>Bulletin of the London Mathematical Society</i>. 2024;56(10):3196-3208. doi:<a href=\"https://doi.org/10.1112/blms.13127\">10.1112/blms.13127</a>","apa":"Kwan, M. A., &#38; Wigderson, Y. (2024). The inertia bound is far from tight. <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society. <a href=\"https://doi.org/10.1112/blms.13127\">https://doi.org/10.1112/blms.13127</a>","short":"M.A. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024) 3196–3208.","mla":"Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10, London Mathematical Society, 2024, pp. 3196–208, doi:<a href=\"https://doi.org/10.1112/blms.13127\">10.1112/blms.13127</a>.","ieee":"M. A. Kwan and Y. Wigderson, “The inertia bound is far from tight,” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10. London Mathematical Society, pp. 3196–3208, 2024.","ista":"Kwan MA, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 56(10), 3196–3208."},"intvolume":"        56","page":"3196-3208","file":[{"success":1,"access_level":"open_access","relation":"main_file","file_size":175966,"date_created":"2025-01-09T13:36:53Z","checksum":"7117f9819eaeb45eef1b0a226f9c2709","file_id":"18814","creator":"dernst","file_name":"2024_BulletinLondonMathSoc_Kwan.pdf","date_updated":"2025-01-09T13:36:53Z","content_type":"application/pdf"}],"ddc":["510"],"has_accepted_license":"1","publication":"Bulletin of the London Mathematical Society","language":[{"iso":"eng"}],"date_created":"2024-08-04T22:01:22Z","scopus_import":"1","status":"public","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","acknowledgement":"The authors are grateful to Noga Alon, Anurag Bishnoi, Clive Elphick, and Ferdinand Ihringer for helpful comments and interesting discussions on earlier drafts of this paper. Matthew Kwan is supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Yuval Wigderson is supported by Dr. Max Rössler, the Walter Haefner Foundation, and the ETH Zürich Foundation.\r\nOpen access funding provided by Eidgenossische Technische Hochschule Zurich.","author":[{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson"}],"type":"journal_article","file_date_updated":"2025-01-09T13:36:53Z","issue":"10","_id":"17376","OA_place":"publisher","arxiv":1,"oa":1},{"page":"869-899","intvolume":"        75","ddc":["500"],"file":[{"checksum":"abf200d37ad69e6f2c0750a30296ad97","date_created":"2024-09-06T12:23:57Z","relation":"main_file","file_size":946411,"access_level":"open_access","success":1,"content_type":"application/pdf","file_name":"2024_QuJofMath_Koval.pdf","date_updated":"2024-09-06T12:23:57Z","creator":"cchlebak","file_id":"17851"}],"language":[{"iso":"eng"}],"publication":"Quarterly Journal of Mathematics","has_accepted_license":"1","date_created":"2024-09-01T22:01:07Z","scopus_import":"1","status":"public","type":"journal_article","acknowledgement":"Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"last_name":"Koval","id":"2eed1f3b-896a-11ed-bdf8-93c7c4bf159e","full_name":"Koval, Illya","first_name":"Illya"},{"first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","last_name":"Kwan"}],"issue":"3","corr_author":"1","file_date_updated":"2024-09-06T12:23:57Z","arxiv":1,"_id":"17475","oa":1,"article_type":"original","abstract":[{"lang":"eng","text":"As a discrete analogue of Kac’s celebrated question on ‘hearing the shape of a drum’ and towards a practical\r\ngraph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by\r\ntheir spectrum (of their adjacency matrix). A striking conjecture in this area, due to van Dam and Haemers,\r\nis that ‘almost all graphs are determined by their spectrum’, meaning that the fraction of unlabelled n-vertex\r\ngraphs which are determined by their spectrum converges to 1 as n → ∞.\r\nIn this paper, we make a step towards this conjecture, showing that there are exponentially many n-vertex\r\ngraphs which are determined by their spectrum. This improves on previous bounds (of shape e\r\nc\r\n√\r\nn\r\n). We also\r\npropose a number of further directions of research.\r\n"}],"project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics","grant_number":"101076777"}],"external_id":{"arxiv":["2309.09788"],"isi":["001249741500001"]},"quality_controlled":"1","day":"19","oa_version":"Published Version","volume":75,"isi":1,"title":"Exponentially many graphs are determined by their spectrum","department":[{"_id":"MaKw"},{"_id":"VaKa"}],"month":"06","date_updated":"2025-09-08T09:09:41Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"doi":"10.1093/qmath/haae030","publication_identifier":{"issn":["0033-5606"],"eissn":["1464-3847"]},"article_processing_charge":"Yes (via OA deal)","publisher":"Oxford University Press","publication_status":"published","citation":{"apa":"Koval, I., &#38; Kwan, M. A. (2024). Exponentially many graphs are determined by their spectrum. <i>Quarterly Journal of Mathematics</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/qmath/haae030\">https://doi.org/10.1093/qmath/haae030</a>","short":"I. Koval, M.A. Kwan, Quarterly Journal of Mathematics 75 (2024) 869–899.","chicago":"Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” <i>Quarterly Journal of Mathematics</i>. Oxford University Press, 2024. <a href=\"https://doi.org/10.1093/qmath/haae030\">https://doi.org/10.1093/qmath/haae030</a>.","ama":"Koval I, Kwan MA. Exponentially many graphs are determined by their spectrum. <i>Quarterly Journal of Mathematics</i>. 2024;75(3):869-899. doi:<a href=\"https://doi.org/10.1093/qmath/haae030\">10.1093/qmath/haae030</a>","ista":"Koval I, Kwan MA. 2024. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 75(3), 869–899.","mla":"Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” <i>Quarterly Journal of Mathematics</i>, vol. 75, no. 3, Oxford University Press, 2024, pp. 869–99, doi:<a href=\"https://doi.org/10.1093/qmath/haae030\">10.1093/qmath/haae030</a>.","ieee":"I. Koval and M. A. Kwan, “Exponentially many graphs are determined by their spectrum,” <i>Quarterly Journal of Mathematics</i>, vol. 75, no. 3. Oxford University Press, pp. 869–899, 2024."},"date_published":"2024-06-19T00:00:00Z","year":"2024"},{"oa":1,"_id":"14499","arxiv":1,"file_date_updated":"2023-11-07T09:16:23Z","corr_author":"1","type":"journal_article","author":[{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"full_name":"Sah, Ashwin","last_name":"Sah","first_name":"Ashwin"},{"first_name":"Lisa","full_name":"Sauermann, Lisa","last_name":"Sauermann"},{"first_name":"Mehtaab","last_name":"Sawhney","full_name":"Sawhney, Mehtaab"}],"acknowledgement":"Kwan was supported for part of this work by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-2141064. Sah was supported by the PD Soros Fellowship. Sauermann was supported by NSF Award DMS-2100157, and for part of this work by a Sloan Research Fellowship.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","keyword":["Discrete Mathematics and Combinatorics","Geometry and Topology","Mathematical Physics","Statistics and Probability","Algebra and Number Theory","Analysis"],"status":"public","date_created":"2023-11-07T09:02:48Z","has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"Forum of Mathematics, Pi","file":[{"file_name":"2023_ForumMathematics_Kwan.pdf","date_updated":"2023-11-07T09:16:23Z","content_type":"application/pdf","creator":"dernst","file_id":"14500","date_created":"2023-11-07T09:16:23Z","checksum":"54b824098d59073cc87a308d458b0a3e","success":1,"access_level":"open_access","file_size":1218719,"relation":"main_file"}],"ddc":["510"],"intvolume":"        11","citation":{"ista":"Kwan MA, Sah A, Sauermann L, Sawhney M. 2023. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. 11, e21.","ieee":"M. A. Kwan, A. Sah, L. Sauermann, and M. Sawhney, “Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture,” <i>Forum of Mathematics, Pi</i>, vol. 11. Cambridge University Press, 2023.","mla":"Kwan, Matthew Alan, et al. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” <i>Forum of Mathematics, Pi</i>, vol. 11, e21, Cambridge University Press, 2023, doi:<a href=\"https://doi.org/10.1017/fmp.2023.17\">10.1017/fmp.2023.17</a>.","short":"M.A. Kwan, A. Sah, L. Sauermann, M. Sawhney, Forum of Mathematics, Pi 11 (2023).","apa":"Kwan, M. A., Sah, A., Sauermann, L., &#38; Sawhney, M. (2023). Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. <i>Forum of Mathematics, Pi</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fmp.2023.17\">https://doi.org/10.1017/fmp.2023.17</a>","ama":"Kwan MA, Sah A, Sauermann L, Sawhney M. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. <i>Forum of Mathematics, Pi</i>. 2023;11. doi:<a href=\"https://doi.org/10.1017/fmp.2023.17\">10.1017/fmp.2023.17</a>","chicago":"Kwan, Matthew Alan, Ashwin Sah, Lisa Sauermann, and Mehtaab Sawhney. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” <i>Forum of Mathematics, Pi</i>. Cambridge University Press, 2023. <a href=\"https://doi.org/10.1017/fmp.2023.17\">https://doi.org/10.1017/fmp.2023.17</a>."},"year":"2023","date_published":"2023-08-24T00:00:00Z","publication_status":"published","doi":"10.1017/fmp.2023.17","publication_identifier":{"issn":["2050-5086"]},"article_processing_charge":"Yes","publisher":"Cambridge University Press","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"department":[{"_id":"MaKw"}],"month":"08","date_updated":"2025-09-09T13:16:15Z","title":"Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture","article_number":"e21","isi":1,"day":"24","oa_version":"Published Version","volume":11,"project":[{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"quality_controlled":"1","external_id":{"isi":["001123866200001"],"arxiv":["2208.02874"]},"abstract":[{"text":"An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clog2n (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a C-Ramsey graph. This brings together two ongoing lines of research: the study of ‘random-like’ properties of Ramsey graphs and the study of small-ball probability for low-degree polynomials of independent random variables.\r\n\r\nThe proof proceeds via an ‘additive structure’ dichotomy on the degree sequence and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics and low-rank approximation. In particular, a key ingredient is a new sharpened version of the quadratic Carbery–Wright theorem on small-ball probability for polynomials of Gaussians, which we believe is of independent interest. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős reiterated in several of his open problem collections and for which he offered one of his notorious monetary prizes.","lang":"eng"}],"article_type":"original"}]