[{"article_processing_charge":"Yes (via OA deal)","month":"02","_id":"21159","year":"2026","oa_version":"Published Version","title":"Counting perfect matchings in Dirac hypergraphs","article_type":"original","publication_status":"published","author":[{"first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","orcid":"0000-0002-4003-7567"},{"first_name":"Roodabeh","full_name":"Safavi Hemami, Roodabeh","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","last_name":"Safavi Hemami"},{"first_name":"Yiting","id":"1917d194-076e-11ed-97cd-837255f88785","full_name":"Wang, Yiting","orcid":"0000-0002-2856-767X","last_name":"Wang"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"success":1,"checksum":"47b0031d90b0e6b9a843f422a1486089","date_updated":"2026-02-16T09:52:38Z","file_name":"2026_Combinatorica_Kwan.pdf","content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2026-02-16T09:52:38Z","file_id":"21228","relation":"main_file","file_size":539646}],"oa":1,"date_published":"2026-02-01T00:00:00Z","abstract":[{"lang":"eng","text":"One of the foundational theorems of extremal graph theory is Dirac’s theorem, which\r\nsays that if an n-vertex graph G has minimum degree at least n/2, then G has a\r\nHamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy,\r\nSelkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles\r\nand perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise\r\ndescription of the numbers of Hamilton cycles and perfect matchings in a Dirac graph\r\nG (in terms of an entropy-like parameter of G). In this paper we extend Cuckler\r\nand Kahn’s result to perfect matchings in hypergraphs. For positive integers d < k,\r\nand for n divisible by k, let md (k, n) be the minimum d-degree that ensures the\r\nexistence of a perfect matching in an n-vertex k-uniform hypergraph. In general, it is\r\nan open question to determine (even asymptotically) the values of md (k, n), but we are\r\nnonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if\r\nan n-vertex k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n)\r\n(for any constantγ > 0), then the number of perfect matchings in G is controlled by\r\nan entropy-like parameter of G. This strengthens cruder estimates arising from work\r\nof Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin."}],"scopus_import":"1","status":"public","OA_type":"hybrid","arxiv":1,"ddc":["510"],"acknowledgement":"We would like to thank the referees for a number of helpful comments and suggestions, which have substantially improved the paper. Open access funding provided by Institute of Science and Technology (IST Austria).","publication":"Combinatorica","citation":{"chicago":"Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature, 2026. https://doi.org/10.1007/s00493-025-00194-8.","ama":"Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8","mla":"Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.” Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8.","ista":"Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 46, 5.","apa":"Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8","ieee":"M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 2026.","short":"M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026)."},"volume":46,"publisher":"Springer Nature","doi":"10.1007/s00493-025-00194-8","day":"01","type":"journal_article","file_date_updated":"2026-02-16T09:52:38Z","date_created":"2026-02-08T23:02:49Z","PlanS_conform":"1","department":[{"_id":"MaKw"},{"_id":"MoHe"}],"article_number":"5","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","language":[{"iso":"eng"}],"intvolume":" 46","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"has_accepted_license":"1","OA_place":"publisher","date_updated":"2026-02-16T09:55:17Z","corr_author":"1","external_id":{"arxiv":["2408.09589"]}},{"oa":1,"file":[{"success":1,"checksum":"c932ebe45c460d4a73f5b2dcca643db1","file_name":"2025_MathIntelligencer_Brunck.pdf","date_updated":"2025-04-08T11:17:45Z","content_type":"application/pdf","creator":"dernst","date_created":"2025-04-08T11:17:45Z","access_level":"open_access","file_id":"19530","relation":"main_file","file_size":1760643}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"author":[{"full_name":"Brunck, Florestan R","id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","first_name":"Florestan R","last_name":"Brunck"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"}],"article_type":"original","publication_status":"published","acknowledgement":"Open access funding provided by Copenhagen University.","ddc":["510"],"arxiv":1,"OA_type":"hybrid","status":"public","date_published":"2025-03-01T00:00:00Z","abstract":[{"text":"Interest in sliding block puzzles dates back to the 15-puzzle, seemingly invented by Noyes Chapman in 1874 (see [23] for an account of the fascinating history of the puzzle). The game consists of fifteen movable square blocks numbered \r\n and arranged within a \r\n square box, leaving one empty space (see Figure 1). The task at hand is to start from a given configuration of the numbered blocks and reach the desired target configuration, where the only allowed move is to slide a numbered block into an adjacent empty space. This task seemed to be unpredictably either very easy to accomplish, or completely impossible, and the puzzle turned into a worldwide sensation in the spring of 1880. A particularly challenging instance, known as the 13-15-14 puzzle, consisted of initial and target configurations that differed by a single swap (historically this swap involved the blocks labeled 14 and 15). The craze of this puzzle was such that it consistently made newspaper headlines in 1880, with an article in the New York Times lamenting that it was “threatening our free institutions” [23, p. 9]. Various prizes were offered for anyone who could solve this challenge, beginning with a $25 set of teeth and culminating with Sam Loyd’s famous $1,000 cash prize.","lang":"eng"}],"scopus_import":"1","month":"03","article_processing_charge":"Yes (via OA deal)","title":"Books, Hallways, and social butterflies: A note on sliding block puzzles","oa_version":"Published Version","year":"2025","_id":"18157","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":"UlWa"},{"_id":"MaKw"}],"file_date_updated":"2025-04-08T11:17:45Z","date_created":"2024-09-29T22:01:38Z","external_id":{"isi":["001318056000001"],"arxiv":["2303.09459"]},"date_updated":"2025-05-19T14:00:09Z","OA_place":"publisher","has_accepted_license":"1","publication_identifier":{"issn":["0343-6993"]},"intvolume":" 47","language":[{"iso":"eng"}],"quality_controlled":"1","publication":"Mathematical Intelligencer","type":"journal_article","page":"52-65","publisher":"Springer Nature","doi":"10.1007/s00283-024-10358-x","day":"01","volume":47,"citation":{"chicago":"Brunck, Florestan R, and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” Mathematical Intelligencer. Springer Nature, 2025. https://doi.org/10.1007/s00283-024-10358-x.","ama":"Brunck FR, Kwan MA. Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. 2025;47:52-65. doi:10.1007/s00283-024-10358-x","ieee":"F. R. Brunck and M. A. Kwan, “Books, Hallways, and social butterflies: A note on sliding block puzzles,” Mathematical Intelligencer, vol. 47. Springer Nature, pp. 52–65, 2025.","ista":"Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. 47, 52–65.","apa":"Brunck, F. R., & Kwan, M. A. (2025). Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. Springer Nature. https://doi.org/10.1007/s00283-024-10358-x","mla":"Brunck, Florestan R., and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” Mathematical Intelligencer, vol. 47, Springer Nature, 2025, pp. 52–65, doi:10.1007/s00283-024-10358-x.","short":"F.R. Brunck, M.A. Kwan, Mathematical Intelligencer 47 (2025) 52–65."}},{"page":"2098-2106","publisher":"Association for Computing Machinery","day":"15","doi":"10.1145/3717823.3718173","type":"conference","ec_funded":1,"citation":{"mla":"Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2098–106, doi:10.1145/3717823.3718173.","apa":"Anastos, M., Kwan, M. A., & Moore, B. (2025). Smoothed analysis for graph isomorphism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. https://doi.org/10.1145/3717823.3718173","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.","ieee":"M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Prague, Czechia, 2025, pp. 2098–2106.","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 Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2098–2106. Association for Computing Machinery, 2025. https://doi.org/10.1145/3717823.3718173.","ama":"Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2025:2098-2106. doi:10.1145/3717823.3718173"},"publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","date_updated":"2025-07-14T06:33:50Z","has_accepted_license":"1","OA_place":"publisher","external_id":{"arxiv":["2410.06095"]},"corr_author":"1","quality_controlled":"1","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"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_created":"2025-07-13T22:01:23Z","file_date_updated":"2025-07-14T06:13:10Z","department":[{"_id":"MaKw"}],"title":"Smoothed analysis for graph isomorphism","year":"2025","_id":"20007","oa_version":"Published Version","month":"06","article_processing_charge":"Yes (via OA deal)","OA_type":"hybrid","conference":{"start_date":"2025-06-23","name":"STOC: Symposium on Theory of Computing","end_date":"2025-06-27","location":"Prague, Czechia"},"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.","arxiv":1,"ddc":["000"],"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."}],"scopus_import":"1","date_published":"2025-06-15T00:00:00Z","status":"public","file":[{"content_type":"application/pdf","date_created":"2025-07-14T06:13:10Z","creator":"dernst","access_level":"open_access","file_id":"20012","relation":"main_file","file_size":706445,"success":1,"checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","file_name":"2025_STOC_Anastos.pdf","date_updated":"2025-07-14T06:13:10Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"project":[{"name":"Randomness and structure in combinatorics","grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"},{"name":"Combinatorial Optimisation Problems on Sparse Random Graphs","grant_number":"ESP3863424","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9"}],"publication_status":"published","author":[{"last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael"},{"first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan"},{"last_name":"Moore","first_name":"Benjamin","full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6"}]},{"date_created":"2025-10-20T11:08:57Z","file_date_updated":"2025-10-21T07:36:56Z","article_number":"rnaf273","PlanS_conform":"1","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)"},"intvolume":" 2025","language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"issn":["1073-7928"],"eissn":["1687-0247"]},"date_updated":"2025-12-01T13:00:35Z","has_accepted_license":"1","OA_place":"publisher","external_id":{"arxiv":["2505.03954"],"isi":["001575137400001"]},"corr_author":"1","publication":"International Mathematics Research Notices","citation":{"chicago":"Jain, Vishesh, Matthew Alan Kwan, Dhruv Mubayi, and Tuan Tran. “The Edge-Statistics Conjecture for Hypergraphs.” International Mathematics Research Notices. Oxford University Press, 2025. https://doi.org/10.1093/imrn/rnaf273.","ama":"Jain V, Kwan MA, Mubayi D, Tran T. The edge-statistics conjecture for hypergraphs. International Mathematics Research Notices. 2025;2025(18). doi:10.1093/imrn/rnaf273","ieee":"V. Jain, M. A. Kwan, D. Mubayi, and T. Tran, “The edge-statistics conjecture for hypergraphs,” International Mathematics Research Notices, 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.","mla":"Jain, Vishesh, et al. “The Edge-Statistics Conjecture for Hypergraphs.” International Mathematics Research Notices, vol. 2025, no. 18, rnaf273, Oxford University Press, 2025, doi:10.1093/imrn/rnaf273.","apa":"Jain, V., Kwan, M. A., Mubayi, D., & Tran, T. (2025). The edge-statistics conjecture for hypergraphs. International Mathematics Research Notices. Oxford University Press. https://doi.org/10.1093/imrn/rnaf273","short":"V. Jain, M.A. Kwan, D. Mubayi, T. Tran, International Mathematics Research Notices 2025 (2025)."},"volume":2025,"day":"11","publisher":"Oxford University Press","doi":"10.1093/imrn/rnaf273","type":"journal_article","project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"article_type":"original","publication_status":"published","author":[{"last_name":"Jain","full_name":"Jain, Vishesh","first_name":"Vishesh"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"last_name":"Mubayi","first_name":"Dhruv","full_name":"Mubayi, Dhruv"},{"last_name":"Tran","full_name":"Tran, Tuan","first_name":"Tuan"}],"file":[{"content_type":"application/pdf","date_created":"2025-10-21T07:36:56Z","creator":"dernst","access_level":"open_access","file_id":"20511","file_size":774323,"relation":"main_file","success":1,"checksum":"016aa4df9453dc180ae7504ac77bf72f","file_name":"2025_IMRN_Jain.pdf","date_updated":"2025-10-21T07:36:56Z"}],"isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"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"}],"scopus_import":"1","date_published":"2025-09-11T00:00:00Z","status":"public","OA_type":"hybrid","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).","ddc":["510"],"arxiv":1,"article_processing_charge":"Yes (via OA deal)","month":"09","year":"2025","_id":"20504","issue":"18","oa_version":"Published Version","title":"The edge-statistics conjecture for hypergraphs"},{"has_accepted_license":"1","OA_place":"publisher","date_updated":"2025-09-30T11:18:57Z","corr_author":"1","external_id":{"isi":["001444429200001"],"arxiv":["2308.12268"]},"quality_controlled":"1","language":[{"iso":"eng"}],"intvolume":" 13","publication_identifier":{"issn":["2050-5094"]},"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_created":"2025-03-20T12:59:14Z","file_date_updated":"2025-04-03T11:24:35Z","department":[{"_id":"MaKw"}],"article_number":"e55","day":"14","doi":"10.1017/fms.2024.144","publisher":"Cambridge University Press","ec_funded":1,"type":"journal_article","citation":{"ama":"Anastos M, Jin Z, Kwan MA, Sudakov B. Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 2025;13. doi:10.1017/fms.2024.144","chicago":"Anastos, Michael, Zhihan Jin, Matthew Alan Kwan, and Benny Sudakov. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” Forum of Mathematics, Sigma. Cambridge University Press, 2025. https://doi.org/10.1017/fms.2024.144.","short":"M. Anastos, Z. Jin, M.A. Kwan, B. Sudakov, Forum of Mathematics, Sigma 13 (2025).","apa":"Anastos, M., Jin, Z., Kwan, M. A., & Sudakov, B. (2025). Extremal, enumerative and probabilistic results on ordered hypergraph matchings. Forum of Mathematics, Sigma. Cambridge University Press. https://doi.org/10.1017/fms.2024.144","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.","mla":"Anastos, Michael, et al. “Extremal, Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” Forum of Mathematics, Sigma, vol. 13, e55, Cambridge University Press, 2025, doi:10.1017/fms.2024.144.","ieee":"M. Anastos, Z. Jin, M. A. Kwan, and B. Sudakov, “Extremal, enumerative and probabilistic results on ordered hypergraph matchings,” Forum of Mathematics, Sigma, vol. 13. Cambridge University Press, 2025."},"volume":13,"publication":"Forum of Mathematics, Sigma","OA_type":"gold","ddc":["510"],"arxiv":1,"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.","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."}],"scopus_import":"1","date_published":"2025-03-14T00:00:00Z","status":"public","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"file":[{"file_id":"19468","file_size":630297,"relation":"main_file","content_type":"application/pdf","date_created":"2025-04-03T11:24:35Z","creator":"dernst","access_level":"open_access","file_name":"2025_ForumMathSigma_Anastos.pdf","date_updated":"2025-04-03T11:24:35Z","success":1,"checksum":"f396270ad78c1ed67095c8e5a66fca26"}],"oa":1,"article_type":"original","publication_status":"published","project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"},{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"author":[{"last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"},{"full_name":"Jin, Zhihan","first_name":"Zhihan","last_name":"Jin"},{"last_name":"Kwan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"full_name":"Sudakov, Benny","first_name":"Benny","last_name":"Sudakov"}],"title":"Extremal, enumerative and probabilistic results on ordered hypergraph matchings","_id":"19433","year":"2025","oa_version":"Published Version","month":"03","article_processing_charge":"Yes"},{"article_processing_charge":"Yes (via OA deal)","month":"04","oa_version":"Published Version","issue":"4","_id":"19554","year":"2025","title":"A central limit theorem for the matching number of a sparse random graph","license":"https://creativecommons.org/licenses/by-nc/4.0/","author":[{"full_name":"Glasgow, Margalit","first_name":"Margalit","last_name":"Glasgow"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"first_name":"Ashwin","full_name":"Sah, Ashwin","last_name":"Sah"},{"full_name":"Sawhney, Mehtaab","first_name":"Mehtaab","last_name":"Sawhney"}],"publication_status":"published","article_type":"original","project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"file":[{"checksum":"69ce9feaf64e776b99f3afd1041b1b11","success":1,"file_name":"2025_JourLondMathSoc_Glasgow.pdf","date_updated":"2025-04-15T13:18:43Z","date_created":"2025-04-15T13:18:43Z","creator":"dernst","access_level":"open_access","content_type":"application/pdf","file_size":392208,"relation":"main_file","file_id":"19564"}],"status":"public","date_published":"2025-04-01T00:00:00Z","scopus_import":"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"}],"arxiv":1,"ddc":["510"],"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Ö.","OA_type":"hybrid","publication":"Journal of the London Mathematical Society","volume":111,"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.” Journal of the London Mathematical Society. Wiley, 2025. https://doi.org/10.1112/jlms.70101.","ama":"Glasgow M, Kwan MA, Sah A, Sawhney M. A central limit theorem for the matching number of a sparse random graph. Journal of the London Mathematical Society. 2025;111(4). doi:10.1112/jlms.70101","apa":"Glasgow, M., Kwan, M. A., Sah, A., & Sawhney, M. (2025). A central limit theorem for the matching number of a sparse random graph. Journal of the London Mathematical Society. Wiley. https://doi.org/10.1112/jlms.70101","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.","mla":"Glasgow, Margalit, et al. “A Central Limit Theorem for the Matching Number of a Sparse Random Graph.” Journal of the London Mathematical Society, vol. 111, no. 4, e70101, Wiley, 2025, doi:10.1112/jlms.70101.","ieee":"M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “A central limit theorem for the matching number of a sparse random graph,” Journal of the London Mathematical Society, vol. 111, no. 4. Wiley, 2025.","short":"M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the London Mathematical Society 111 (2025)."},"type":"journal_article","doi":"10.1112/jlms.70101","publisher":"Wiley","day":"01","department":[{"_id":"MaKw"}],"article_number":"e70101","file_date_updated":"2025-04-15T13:18:43Z","date_created":"2025-04-13T22:01:19Z","tmp":{"short":"CC BY-NC (4.0)","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"publication_identifier":{"eissn":["1469-7750"],"issn":["0024-6107"]},"quality_controlled":"1","language":[{"iso":"eng"}],"intvolume":" 111","corr_author":"1","external_id":{"isi":["001473087200024"],"arxiv":["2402.05851"]},"has_accepted_license":"1","OA_place":"publisher","date_updated":"2025-09-30T11:35:55Z"},{"external_id":{"arxiv":["2303.05435"]},"corr_author":"1","date_updated":"2026-02-23T10:44:41Z","OA_place":"publisher","has_accepted_license":"1","publication_identifier":{"eissn":["1435-9863"],"issn":["1435-9855"]},"quality_controlled":"1","language":[{"iso":"eng"}],"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)"},"PlanS_conform":"1","department":[{"_id":"MaKw"}],"date_created":"2026-02-17T07:41:59Z","type":"journal_article","publisher":"European Mathematical Society Press","day":"02","doi":"10.4171/jems/1692","DOAJ_listed":"1","citation":{"chicago":"Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney. “The Exact Rank of Sparse Random Graphs.” Journal of the European Mathematical Society. European Mathematical Society Press, 2025. https://doi.org/10.4171/jems/1692.","ama":"Glasgow M, Kwan MA, Sah A, Sawhney M. The exact rank of sparse random graphs. Journal of the European Mathematical Society. 2025. doi:10.4171/jems/1692","ieee":"M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “The exact rank of sparse random graphs,” Journal of the European Mathematical Society. European Mathematical Society Press, 2025.","ista":"Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. The exact rank of sparse random graphs. Journal of the European Mathematical Society.","apa":"Glasgow, M., Kwan, M. A., Sah, A., & Sawhney, M. (2025). The exact rank of sparse random graphs. Journal of the European Mathematical Society. European Mathematical Society Press. https://doi.org/10.4171/jems/1692","mla":"Glasgow, Margalit, et al. “The Exact Rank of Sparse Random Graphs.” Journal of the European Mathematical Society, European Mathematical Society Press, 2025, doi:10.4171/jems/1692.","short":"M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the European Mathematical Society (2025)."},"main_file_link":[{"url":"https://doi.org/10.4171/JEMS/1692","open_access":"1"}],"publication":"Journal of the European Mathematical Society","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","arxiv":1,"ddc":["510"],"OA_type":"diamond","status":"public","date_published":"2025-09-02T00:00:00Z","abstract":[{"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).","lang":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Glasgow","full_name":"Glasgow, Margalit","first_name":"Margalit"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"full_name":"Sah, Ashwin","first_name":"Ashwin","last_name":"Sah"},{"last_name":"Sawhney","first_name":"Mehtaab","full_name":"Sawhney, Mehtaab"}],"project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"publication_status":"epub_ahead","article_type":"original","title":"The exact rank of sparse random graphs","oa_version":"Published Version","year":"2025","_id":"21263","month":"09","article_processing_charge":"No"},{"title":"Resolution of the quadratic Littlewood–Offord problem","oa_version":"Published Version","_id":"21706","issue":"12","year":"2025","month":"12","article_processing_charge":"Yes (via OA deal)","arxiv":1,"ddc":["510"],"acknowledgement":"We would like to thank the anonymous referee for a number of helpful comments and suggestions. Matthew Kwan was supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Lisa Sauermann was supported in part by NSF Award DMS-2100157 and a Sloan Research Fellowship, and in part by the DFG Heisenberg Program.","OA_type":"hybrid","status":"public","date_published":"2025-12-01T00:00:00Z","scopus_import":"1","abstract":[{"text":"Consider a quadratic polynomial Q(ξ1, . . . , ξn) of independent Rademacher random variables ξ1, . . . , ξn. To what extent can Q(ξ1, . . . , ξn) concentrate on a single value? This quadratic version of the classical Littlewood–Offord problem was popularised by Costello, Tao and Vu in their study of symmetric random matrices. In this paper, we obtain an essentially optimal bound for this problem, as conjectured by Nguyen and Vu. Specifically, if Q(ξ1, . . . , ξn) ‘robustly depends on at least m of the ξi’ in the sense that there is no way to pin down the value of Q(ξ1, . . . , ξn) by fixing values for fewer than m of the variables ξi, then we have Pr[Q(ξ1, . . . , ξn) = 0] ≤ O(1/√m). This also implies a similar result in the case where ξ1, . . . , ξn have arbitrary distributions. Our proof combines a number of ideas that may be of independent interest, including an inductive decoupling scheme that reduces quadratic anticoncentration problems\r\nto high-dimensional linear anticoncentration problems. Also, one application of our main result is the resolution of a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn related to graph inducibility. ","lang":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"success":1,"checksum":"bd3415bb435da9d0b39f6f9a18c61abb","file_name":"2025_CompositioMath_Kwan.pdf","date_updated":"2026-05-04T09:41:25Z","content_type":"application/pdf","creator":"dernst","date_created":"2026-05-04T09:41:25Z","access_level":"open_access","file_id":"21787","file_size":858727,"relation":"main_file"}],"author":[{"last_name":"Kwan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"full_name":"Sauermann, Lisa","first_name":"Lisa","last_name":"Sauermann"}],"article_type":"original","publication_status":"published","project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"type":"journal_article","doi":"10.1112/S0010437X25102789","publisher":"Cambridge University Press","day":"01","page":"3089-3139","volume":161,"citation":{"chicago":"Kwan, Matthew Alan, and Lisa Sauermann. “Resolution of the Quadratic Littlewood–Offord Problem.” Compositio Mathematica. Cambridge University Press, 2025. https://doi.org/10.1112/S0010437X25102789.","ama":"Kwan MA, Sauermann L. Resolution of the quadratic Littlewood–Offord problem. Compositio Mathematica. 2025;161(12):3089-3139. doi:10.1112/S0010437X25102789","mla":"Kwan, Matthew Alan, and Lisa Sauermann. “Resolution of the Quadratic Littlewood–Offord Problem.” Compositio Mathematica, vol. 161, no. 12, Cambridge University Press, 2025, pp. 3089–139, doi:10.1112/S0010437X25102789.","apa":"Kwan, M. A., & Sauermann, L. (2025). Resolution of the quadratic Littlewood–Offord problem. Compositio Mathematica. Cambridge University Press. https://doi.org/10.1112/S0010437X25102789","ista":"Kwan MA, Sauermann L. 2025. Resolution of the quadratic Littlewood–Offord problem. Compositio Mathematica. 161(12), 3089–3139.","ieee":"M. A. Kwan and L. Sauermann, “Resolution of the quadratic Littlewood–Offord problem,” Compositio Mathematica, vol. 161, no. 12. Cambridge University Press, pp. 3089–3139, 2025.","short":"M.A. Kwan, L. Sauermann, Compositio Mathematica 161 (2025) 3089–3139."},"publication":"Compositio Mathematica","corr_author":"1","external_id":{"arxiv":["2312.13826"]},"has_accepted_license":"1","OA_place":"publisher","date_updated":"2026-05-04T09:42:57Z","publication_identifier":{"issn":["0010-437X"],"eissn":["1570-5846"]},"language":[{"iso":"eng"}],"quality_controlled":"1","intvolume":" 161","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"}],"PlanS_conform":"1","file_date_updated":"2026-05-04T09:41:25Z","date_created":"2026-04-12T22:01:48Z"},{"date_created":"2024-11-17T23:01:48Z","department":[{"_id":"MaKw"}],"OA_place":"repository","date_updated":"2025-09-08T14:40:55Z","corr_author":"1","external_id":{"arxiv":["2201.04554"],"isi":["001366233800004"]},"language":[{"iso":"eng"}],"quality_controlled":"1","intvolume":" 200","publication_identifier":{"eissn":["1939-8980"],"issn":["0003-486X"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2201.04554"}],"publication":"Annals of Mathematics","day":"01","publisher":"Princeton University","doi":"10.4007/annals.2024.200.3.4","page":"1059-1156","type":"journal_article","citation":{"ama":"Kwan MA, Sah A, Sawhney M, Simkin M. High-girth Steiner triple systems. Annals of Mathematics. 2024;200(3):1059-1156. doi:10.4007/annals.2024.200.3.4","chicago":"Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “High-Girth Steiner Triple Systems.” Annals of Mathematics. Princeton University, 2024. https://doi.org/10.4007/annals.2024.200.3.4.","short":"M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Annals of Mathematics 200 (2024) 1059–1156.","ieee":"M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “High-girth Steiner triple systems,” Annals of Mathematics, vol. 200, no. 3. Princeton University, pp. 1059–1156, 2024.","ista":"Kwan MA, Sah A, Sawhney M, Simkin M. 2024. High-girth Steiner triple systems. Annals of Mathematics. 200(3), 1059–1156.","apa":"Kwan, M. A., Sah, A., Sawhney, M., & Simkin, M. (2024). High-girth Steiner triple systems. Annals of Mathematics. Princeton University. https://doi.org/10.4007/annals.2024.200.3.4","mla":"Kwan, Matthew Alan, et al. “High-Girth Steiner Triple Systems.” Annals of Mathematics, vol. 200, no. 3, Princeton University, 2024, pp. 1059–156, doi:10.4007/annals.2024.200.3.4."},"volume":200,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"oa":1,"article_type":"original","publication_status":"published","author":[{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"last_name":"Sah","first_name":"Ashwin","full_name":"Sah, Ashwin"},{"last_name":"Sawhney","first_name":"Mehtaab","full_name":"Sawhney, Mehtaab"},{"last_name":"Simkin","first_name":"Michael","full_name":"Simkin, Michael"}],"OA_type":"green","arxiv":1,"acknowledgement":"Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE1745302. Sah was supported by the PD Soros Fellowship. Simkin was supported by the Center of Mathematical Sciences and Applications at Harvard University.","abstract":[{"text":"We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth.","lang":"eng"}],"date_published":"2024-11-01T00:00:00Z","scopus_import":"1","status":"public","month":"11","article_processing_charge":"No","title":"High-girth Steiner triple systems","_id":"18559","issue":"3","year":"2024","oa_version":"Preprint"},{"article_processing_charge":"Yes (via OA deal)","month":"12","oa_version":"Published Version","_id":"18583","issue":"6","year":"2024","title":"Partitioning problems via random processes","author":[{"last_name":"Anastos","first_name":"Michael","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"},{"last_name":"Cooley","first_name":"Oliver","full_name":"Cooley, Oliver","id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d"},{"full_name":"Kang, Mihyun","first_name":"Mihyun","last_name":"Kang"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"}],"publication_status":"published","article_type":"original","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"},{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"oa":1,"isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"success":1,"checksum":"98e301e0565d75e3fb50e10e982a5018","date_updated":"2024-12-10T08:10:39Z","file_name":"2024_JournLondonMathSoc_Anastos.pdf","content_type":"application/pdf","access_level":"open_access","creator":"dernst","date_created":"2024-12-10T08:10:39Z","file_id":"18639","relation":"main_file","file_size":539891}],"status":"public","date_published":"2024-12-01T00:00:00Z","scopus_import":"1","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"}],"arxiv":1,"ddc":["510"],"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.","OA_type":"hybrid","publication":"Journal of the London Mathematical Society","volume":110,"citation":{"short":"M. Anastos, O. Cooley, M. Kang, M.A. Kwan, Journal of the London Mathematical Society 110 (2024).","ieee":"M. Anastos, O. Cooley, M. Kang, and M. A. Kwan, “Partitioning problems via random processes,” Journal of the London Mathematical Society, vol. 110, no. 6. Wiley, 2024.","ista":"Anastos M, Cooley O, Kang M, Kwan MA. 2024. Partitioning problems via random processes. Journal of the London Mathematical Society. 110(6), e70010.","apa":"Anastos, M., Cooley, O., Kang, M., & Kwan, M. A. (2024). Partitioning problems via random processes. Journal of the London Mathematical Society. Wiley. https://doi.org/10.1112/jlms.70010","mla":"Anastos, Michael, et al. “Partitioning Problems via Random Processes.” Journal of the London Mathematical Society, vol. 110, no. 6, e70010, Wiley, 2024, doi:10.1112/jlms.70010.","ama":"Anastos M, Cooley O, Kang M, Kwan MA. Partitioning problems via random processes. Journal of the London Mathematical Society. 2024;110(6). doi:10.1112/jlms.70010","chicago":"Anastos, Michael, Oliver Cooley, Mihyun Kang, and Matthew Alan Kwan. “Partitioning Problems via Random Processes.” Journal of the London Mathematical Society. Wiley, 2024. https://doi.org/10.1112/jlms.70010."},"ec_funded":1,"type":"journal_article","day":"01","publisher":"Wiley","doi":"10.1112/jlms.70010","department":[{"_id":"MaKw"}],"article_number":"e70010","file_date_updated":"2024-12-10T08:10:39Z","date_created":"2024-11-24T23:01:48Z","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)"},"publication_identifier":{"issn":["0024-6107"],"eissn":["1469-7750"]},"quality_controlled":"1","language":[{"iso":"eng"}],"intvolume":" 110","corr_author":"1","external_id":{"isi":["001374738100001"],"arxiv":["2307.06453"]},"has_accepted_license":"1","OA_place":"publisher","date_updated":"2025-12-02T13:52:26Z"},{"page":"413-443","publisher":"Springer Nature","doi":"10.1007/978-3-031-78011-0_14","day":"02","type":"conference","citation":{"short":"M. Anastos, B. Auerbach, M.A. Baig, M. Cueto Noval, M.A. Kwan, G. Pascual Perez, K.Z. Pietrzak, in:, 22nd International Conference on Theory of Cryptography, Springer Nature, 2024, pp. 413–443.","ieee":"M. Anastos et al., “The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging,” in 22nd International Conference on Theory of Cryptography, Milan, Italy, 2024, vol. 15364, pp. 413–443.","ista":"Anastos M, Auerbach B, Baig MA, Cueto Noval M, Kwan MA, Pascual Perez G, Pietrzak KZ. 2024. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. 22nd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 15364, 413–443.","mla":"Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” 22nd International Conference on Theory of Cryptography, vol. 15364, Springer Nature, 2024, pp. 413–43, doi:10.1007/978-3-031-78011-0_14.","apa":"Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual Perez, G., & Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In 22nd International Conference on Theory of Cryptography (Vol. 15364, pp. 413–443). Milan, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-78011-0_14","ama":"Anastos M, Auerbach B, Baig MA, et al. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In: 22nd International Conference on Theory of Cryptography. Vol 15364. Springer Nature; 2024:413-443. doi:10.1007/978-3-031-78011-0_14","chicago":"Anastos, Michael, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Matthew Alan Kwan, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” In 22nd International Conference on Theory of Cryptography, 15364:413–43. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-78011-0_14."},"volume":15364,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2024/1097"}],"publication":"22nd International Conference on Theory of Cryptography","date_updated":"2025-12-02T13:55:46Z","OA_place":"repository","external_id":{"isi":["001545628900014"]},"corr_author":"1","intvolume":" 15364","language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031780103"],"eissn":["1611-3349"]},"date_created":"2024-12-22T23:01:47Z","department":[{"_id":"MaKw"},{"_id":"KrPi"}],"title":"The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging","year":"2024","_id":"18702","oa_version":"Preprint","month":"12","alternative_title":["LNCS"],"article_processing_charge":"No","OA_type":"green","conference":{"location":"Milan, Italy","name":"TCC: Theory of Cryptography","end_date":"2024-12-06","start_date":"2024-12-02"},"scopus_import":"1","abstract":[{"text":"In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. ","lang":"eng"}],"date_published":"2024-12-02T00:00:00Z","status":"public","isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publication_status":"published","author":[{"first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos"},{"first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","full_name":"Auerbach, Benedikt","last_name":"Auerbach","orcid":"0000-0002-7553-6606"},{"last_name":"Baig","first_name":"Mirza Ahad","full_name":"Baig, Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"orcid":"0000-0002-2505-4246","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","first_name":"Miguel"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}]},{"volume":56,"citation":{"chicago":"Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” Bulletin of the London Mathematical Society. London Mathematical Society, 2024. https://doi.org/10.1112/blms.13127.","ama":"Kwan MA, Wigderson Y. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 2024;56(10):3196-3208. doi:10.1112/blms.13127","ieee":"M. A. Kwan and Y. Wigderson, “The inertia bound is far from tight,” Bulletin of the London Mathematical Society, vol. 56, no. 10. London Mathematical Society, pp. 3196–3208, 2024.","apa":"Kwan, M. A., & Wigderson, Y. (2024). The inertia bound is far from tight. Bulletin of the London Mathematical Society. London Mathematical Society. https://doi.org/10.1112/blms.13127","mla":"Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” Bulletin of the London Mathematical Society, vol. 56, no. 10, London Mathematical Society, 2024, pp. 3196–208, doi:10.1112/blms.13127.","ista":"Kwan MA, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 56(10), 3196–3208.","short":"M.A. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024) 3196–3208."},"type":"journal_article","page":"3196-3208","publisher":"London Mathematical Society","doi":"10.1112/blms.13127","day":"01","publication":"Bulletin of the London Mathematical Society","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"intvolume":" 56","language":[{"iso":"eng"}],"quality_controlled":"1","external_id":{"isi":["001279563300001"],"arxiv":["2312.04925"]},"date_updated":"2025-09-08T08:45:39Z","OA_place":"publisher","has_accepted_license":"1","department":[{"_id":"MaKw"}],"date_created":"2024-08-04T22:01:22Z","file_date_updated":"2025-01-09T13:36:53Z","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)"},"oa_version":"Published Version","year":"2024","issue":"10","_id":"17376","title":"The inertia bound is far from tight","article_processing_charge":"Yes (via OA deal)","month":"10","status":"public","scopus_import":"1","date_published":"2024-10-01T00:00:00Z","abstract":[{"lang":"eng","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."}],"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.","arxiv":1,"ddc":["510"],"OA_type":"hybrid","author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan"},{"last_name":"Wigderson","first_name":"Yuval","full_name":"Wigderson, Yuval"}],"project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"article_type":"original","publication_status":"published","oa":1,"file":[{"date_updated":"2025-01-09T13:36:53Z","file_name":"2024_BulletinLondonMathSoc_Kwan.pdf","success":1,"checksum":"7117f9819eaeb45eef1b0a226f9c2709","file_id":"18814","file_size":175966,"relation":"main_file","content_type":"application/pdf","access_level":"open_access","date_created":"2025-01-09T13:36:53Z","creator":"dernst"}],"isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"corr_author":"1","external_id":{"isi":["001249741500001"],"arxiv":["2309.09788"]},"has_accepted_license":"1","date_updated":"2025-09-08T09:09:41Z","publication_identifier":{"eissn":["1464-3847"],"issn":["0033-5606"]},"language":[{"iso":"eng"}],"quality_controlled":"1","intvolume":" 75","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"},{"_id":"VaKa"}],"file_date_updated":"2024-09-06T12:23:57Z","date_created":"2024-09-01T22:01:07Z","type":"journal_article","doi":"10.1093/qmath/haae030","publisher":"Oxford University Press","day":"19","page":"869-899","volume":75,"citation":{"short":"I. Koval, M.A. Kwan, Quarterly Journal of Mathematics 75 (2024) 869–899.","ieee":"I. Koval and M. A. Kwan, “Exponentially many graphs are determined by their spectrum,” Quarterly Journal of Mathematics, vol. 75, no. 3. Oxford University Press, pp. 869–899, 2024.","apa":"Koval, I., & Kwan, M. A. (2024). Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. Oxford University Press. https://doi.org/10.1093/qmath/haae030","mla":"Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” Quarterly Journal of Mathematics, vol. 75, no. 3, Oxford University Press, 2024, pp. 869–99, doi:10.1093/qmath/haae030.","ista":"Koval I, Kwan MA. 2024. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 75(3), 869–899.","ama":"Koval I, Kwan MA. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 2024;75(3):869-899. doi:10.1093/qmath/haae030","chicago":"Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” Quarterly Journal of Mathematics. Oxford University Press, 2024. https://doi.org/10.1093/qmath/haae030."},"publication":"Quarterly Journal of Mathematics","arxiv":1,"ddc":["500"],"acknowledgement":"Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777.","status":"public","date_published":"2024-06-19T00:00:00Z","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"}],"scopus_import":"1","oa":1,"isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","file":[{"content_type":"application/pdf","access_level":"open_access","date_created":"2024-09-06T12:23:57Z","creator":"cchlebak","file_id":"17851","file_size":946411,"relation":"main_file","success":1,"checksum":"abf200d37ad69e6f2c0750a30296ad97","date_updated":"2024-09-06T12:23:57Z","file_name":"2024_QuJofMath_Koval.pdf"}],"author":[{"last_name":"Koval","first_name":"Illya","id":"2eed1f3b-896a-11ed-bdf8-93c7c4bf159e","full_name":"Koval, Illya"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan"}],"publication_status":"published","article_type":"original","project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"title":"Exponentially many graphs are determined by their spectrum","oa_version":"Published Version","_id":"17475","issue":"3","year":"2024","month":"06","article_processing_charge":"Yes (via OA deal)"},{"article_processing_charge":"Yes (in subscription journal)","month":"09","year":"2023","_id":"14444","issue":"2","oa_version":"Preprint","title":"Substructures in Latin squares","article_type":"original","publication_status":"published","author":[{"orcid":"0000-0002-4003-7567","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan"},{"first_name":"Ashwin","full_name":"Sah, Ashwin","last_name":"Sah"},{"last_name":"Sawhney","full_name":"Sawhney, Mehtaab","first_name":"Mehtaab"},{"first_name":"Michael","full_name":"Simkin, Michael","last_name":"Simkin"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"oa":1,"date_published":"2023-09-01T00:00:00Z","scopus_import":"1","abstract":[{"lang":"eng","text":"We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares, resolving a conjecture of Linial that there exist Latin squares with arbitrarily high girth. As a consequence, we see that the number of order- n Latin squares with no intercalate (i.e., no 2×2 Latin subsquare) is at least (e−9/4n−o(n))n2. Equivalently, P[N=0]≥e−n2/4−o(n2)=e−(1+o(1))EN\r\n , where N is the number of intercalates in a uniformly random order- n Latin square. \r\nIn fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant 0<δ≤1 we have P[N≤(1−δ)EN]=exp(−Θ(n2)) and for any constant δ>0 we have P[N≥(1+δ)EN]=exp(−Θ(n4/3logn)). \r\nFinally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order- n Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate 2×2 submatrices with the same arrangement of symbols) is of order n4, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative'' the quasigroup associated with the Latin square is."}],"status":"public","acknowledgement":"Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302. Sah was supported by the PD Soros Fellowship. Simkin was supported by the Center of Mathematical Sciences and Applications at Harvard University.","arxiv":1,"publication":"Israel Journal of Mathematics","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2202.05088"}],"citation":{"ieee":"M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “Substructures in Latin squares,” Israel Journal of Mathematics, vol. 256, no. 2. Springer Nature, pp. 363–416, 2023.","mla":"Kwan, Matthew Alan, et al. “Substructures in Latin Squares.” Israel Journal of Mathematics, vol. 256, no. 2, Springer Nature, 2023, pp. 363–416, doi:10.1007/s11856-023-2513-9.","apa":"Kwan, M. A., Sah, A., Sawhney, M., & Simkin, M. (2023). Substructures in Latin squares. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-023-2513-9","ista":"Kwan MA, Sah A, Sawhney M, Simkin M. 2023. Substructures in Latin squares. Israel Journal of Mathematics. 256(2), 363–416.","short":"M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Israel Journal of Mathematics 256 (2023) 363–416.","chicago":"Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “Substructures in Latin Squares.” Israel Journal of Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2513-9.","ama":"Kwan MA, Sah A, Sawhney M, Simkin M. Substructures in Latin squares. Israel Journal of Mathematics. 2023;256(2):363-416. doi:10.1007/s11856-023-2513-9"},"volume":256,"page":"363-416","publisher":"Springer Nature","day":"01","doi":"10.1007/s11856-023-2513-9","type":"journal_article","date_created":"2023-10-22T22:01:14Z","department":[{"_id":"MaKw"}],"intvolume":" 256","quality_controlled":"1","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1565-8511"],"issn":["0021-2172"]},"date_updated":"2025-09-09T13:08:47Z","external_id":{"arxiv":["2202.05088"],"isi":["001081646400001"]}},{"author":[{"first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","last_name":"Kwan"},{"first_name":"Ashwin","full_name":"Sah, Ashwin","last_name":"Sah"},{"full_name":"Sauermann, Lisa","first_name":"Lisa","last_name":"Sauermann"},{"last_name":"Sawhney","first_name":"Mehtaab","full_name":"Sawhney, Mehtaab"}],"article_type":"original","publication_status":"published","project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"file":[{"content_type":"application/pdf","date_created":"2023-11-07T09:16:23Z","creator":"dernst","access_level":"open_access","file_id":"14500","relation":"main_file","file_size":1218719,"success":1,"checksum":"54b824098d59073cc87a308d458b0a3e","file_name":"2023_ForumMathematics_Kwan.pdf","date_updated":"2023-11-07T09:16:23Z"}],"status":"public","date_published":"2023-08-24T00:00:00Z","scopus_import":"1","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"}],"ddc":["510"],"arxiv":1,"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.","article_processing_charge":"Yes","month":"08","oa_version":"Published Version","_id":"14499","year":"2023","keyword":["Discrete Mathematics and Combinatorics","Geometry and Topology","Mathematical Physics","Statistics and Probability","Algebra and Number Theory","Analysis"],"title":"Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture","department":[{"_id":"MaKw"}],"article_number":"e21","file_date_updated":"2023-11-07T09:16:23Z","date_created":"2023-11-07T09:02:48Z","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)"},"publication_identifier":{"issn":["2050-5086"]},"language":[{"iso":"eng"}],"quality_controlled":"1","intvolume":" 11","corr_author":"1","external_id":{"arxiv":["2208.02874"],"isi":["001123866200001"]},"has_accepted_license":"1","date_updated":"2025-09-09T13:16:15Z","publication":"Forum of Mathematics, Pi","volume":11,"citation":{"ama":"Kwan MA, Sah A, Sauermann L, Sawhney M. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. 2023;11. doi:10.1017/fmp.2023.17","chicago":"Kwan, Matthew Alan, Ashwin Sah, Lisa Sauermann, and Mehtaab Sawhney. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” Forum of Mathematics, Pi. Cambridge University Press, 2023. https://doi.org/10.1017/fmp.2023.17.","short":"M.A. Kwan, A. Sah, L. Sauermann, M. Sawhney, Forum of Mathematics, Pi 11 (2023).","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.","apa":"Kwan, M. A., Sah, A., Sauermann, L., & Sawhney, M. (2023). Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. Cambridge University Press. https://doi.org/10.1017/fmp.2023.17","mla":"Kwan, Matthew Alan, et al. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” Forum of Mathematics, Pi, vol. 11, e21, Cambridge University Press, 2023, doi:10.1017/fmp.2023.17.","ieee":"M. A. Kwan, A. Sah, L. Sauermann, and M. Sawhney, “Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture,” Forum of Mathematics, Pi, vol. 11. Cambridge University Press, 2023."},"type":"journal_article","day":"24","doi":"10.1017/fmp.2023.17","publisher":"Cambridge University Press"},{"publication":"Comptes Rendus Mathematique","citation":{"short":"M.A. Kwan, A. Sah, M. Sawhney, Comptes Rendus Mathematique 361 (2023) 565–575.","ieee":"M. A. Kwan, A. Sah, and M. Sawhney, “Enumerating matroids and linear spaces,” Comptes Rendus Mathematique, vol. 361, no. G2. Academie des Sciences, pp. 565–575, 2023.","ista":"Kwan MA, Sah A, Sawhney M. 2023. Enumerating matroids and linear spaces. Comptes Rendus Mathematique. 361(G2), 565–575.","mla":"Kwan, Matthew Alan, et al. “Enumerating Matroids and Linear Spaces.” Comptes Rendus Mathematique, vol. 361, no. G2, Academie des Sciences, 2023, pp. 565–75, doi:10.5802/crmath.423.","apa":"Kwan, M. A., Sah, A., & Sawhney, M. (2023). Enumerating matroids and linear spaces. Comptes Rendus Mathematique. Academie des Sciences. https://doi.org/10.5802/crmath.423","ama":"Kwan MA, Sah A, Sawhney M. Enumerating matroids and linear spaces. Comptes Rendus Mathematique. 2023;361(G2):565-575. doi:10.5802/crmath.423","chicago":"Kwan, Matthew Alan, Ashwin Sah, and Mehtaab Sawhney. “Enumerating Matroids and Linear Spaces.” Comptes Rendus Mathematique. Academie des Sciences, 2023. https://doi.org/10.5802/crmath.423."},"volume":361,"page":"565-575","doi":"10.5802/crmath.423","day":"01","publisher":"Academie des Sciences","type":"journal_article","file_date_updated":"2024-03-25T07:21:52Z","date_created":"2024-03-24T23:01:00Z","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)"},"intvolume":" 361","quality_controlled":"1","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1778-3569"],"issn":["1631-073X"]},"date_updated":"2025-09-09T14:26:32Z","has_accepted_license":"1","external_id":{"isi":["001167671400009"],"arxiv":["2112.03788"]},"article_processing_charge":"Yes","month":"02","year":"2023","_id":"15173","issue":"G2","oa_version":"Published Version","title":"Enumerating matroids and linear spaces","publication_status":"published","article_type":"original","author":[{"first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan"},{"first_name":"Ashwin","full_name":"Sah, Ashwin","last_name":"Sah"},{"last_name":"Sawhney","full_name":"Sawhney, Mehtaab","first_name":"Mehtaab"}],"file":[{"file_id":"15174","relation":"main_file","file_size":598097,"content_type":"application/pdf","creator":"dernst","date_created":"2024-03-25T07:21:52Z","access_level":"open_access","file_name":"2023_ComptesRendusMath_Kwan.pdf","date_updated":"2024-03-25T07:21:52Z","success":1,"checksum":"d1d0e0a854a79ae95fb66d75d9117a68"}],"isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"abstract":[{"text":"We show that the number of linear spaces on a set of n points and the number of rank-3 matroids on a ground set of size n are both of the form (cn+o(n))n2/6, where c=e3√/2−3(1+3–√)/2. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: the numbers of rank-1 and rank-2 matroids on a ground set of size n have exact representations in terms of well-known combinatorial functions, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant r≥4 there are (e1−rn+o(n))nr−1/r! rank-r matroids on a ground set of size n. In our proof, we introduce a new approach for bounding the number of clique decompositions of a complete graph, using quasirandomness instead of the so-called entropy method that is common in this area.","lang":"eng"}],"scopus_import":"1","date_published":"2023-02-01T00:00:00Z","status":"public","acknowledgement":"Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302. Sah was supported by the PD Soros Fellowship.\r\nWe thank Michael Simkin for helpful comments on the manuscript. We thank Zach Hunter for\r\nseveral corrections.","arxiv":1,"ddc":["510"]},{"date_updated":"2024-10-09T21:02:31Z","corr_author":"1","external_id":{"arxiv":["2006.08836"],"isi":["000798461500001"]},"language":[{"iso":"eng"}],"quality_controlled":"1","intvolume":" 375","publication_identifier":{"issn":["0002-9947"],"eissn":["1088-6850"]},"date_created":"2022-06-12T22:01:45Z","department":[{"_id":"MaKw"}],"day":"01","doi":"10.1090/tran/8614","publisher":"American Mathematical Society","page":"4209-4250","type":"journal_article","citation":{"ieee":"M. A. Kwan, L. Sauermann, and Y. Zhao, “Extension complexity of low-dimensional polytopes,” Transactions of the American Mathematical Society, vol. 375, no. 6. American Mathematical Society, pp. 4209–4250, 2022.","ista":"Kwan MA, Sauermann L, Zhao Y. 2022. Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. 375(6), 4209–4250.","apa":"Kwan, M. A., Sauermann, L., & Zhao, Y. (2022). Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. American Mathematical Society. https://doi.org/10.1090/tran/8614","mla":"Kwan, Matthew Alan, et al. “Extension Complexity of Low-Dimensional Polytopes.” Transactions of the American Mathematical Society, vol. 375, no. 6, American Mathematical Society, 2022, pp. 4209–50, doi:10.1090/tran/8614.","short":"M.A. Kwan, L. Sauermann, Y. Zhao, Transactions of the American Mathematical Society 375 (2022) 4209–4250.","chicago":"Kwan, Matthew Alan, Lisa Sauermann, and Yufei Zhao. “Extension Complexity of Low-Dimensional Polytopes.” Transactions of the American Mathematical Society. American Mathematical Society, 2022. https://doi.org/10.1090/tran/8614.","ama":"Kwan MA, Sauermann L, Zhao Y. Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. 2022;375(6):4209-4250. doi:10.1090/tran/8614"},"volume":375,"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2006.08836","open_access":"1"}],"publication":"Transactions of the American Mathematical Society","arxiv":1,"acknowledgement":"The research of the first author was supported by SNSF Project 178493 and NSF Award DMS-1953990. The research of the second author supported by NSF Award DMS-1953772.\r\nThe research of the third author was supported by NSF Award DMS-1764176, NSF CAREER Award DMS-2044606, a Sloan Research Fellowship, and the MIT Solomon Buchsbaum Fund. ","scopus_import":"1","date_published":"2022-06-01T00:00:00Z","abstract":[{"lang":"eng","text":"Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes. First, we prove that for a fixed dimension d, the extension complexity of a random d-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie on a circle) has extension complexity at most 24√n. This bound is tight up to the constant factor 24. Finally, we show that there exists an no(1)-dimensional polytope with at most n vertices and extension complexity n1−o(1). Our theorems are proved with a range of different techniques, which we hope will be of further interest."}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"oa":1,"publication_status":"published","article_type":"original","author":[{"last_name":"Kwan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"first_name":"Lisa","full_name":"Sauermann, Lisa","last_name":"Sauermann"},{"full_name":"Zhao, Yufei","first_name":"Yufei","last_name":"Zhao"}],"title":"Extension complexity of low-dimensional polytopes","issue":"6","_id":"11443","year":"2022","oa_version":"Preprint","month":"06","article_processing_charge":"No"},{"related_material":{"record":[{"status":"public","id":"11145","relation":"earlier_version"}]},"type":"journal_article","page":"3823-3828","day":"01","doi":"10.1109/TIT.2022.3148779","publisher":"IEEE","volume":68,"citation":{"ama":"Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. IEEE Transactions on Information Theory. 2022;68(6):3823-3828. doi:10.1109/TIT.2022.3148779","chicago":"Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” IEEE Transactions on Information Theory. IEEE, 2022. https://doi.org/10.1109/TIT.2022.3148779.","short":"A. Ferber, M.A. Kwan, L. Sauermann, IEEE Transactions on Information Theory 68 (2022) 3823–3828.","apa":"Ferber, A., Kwan, M. A., & Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. IEEE Transactions on Information Theory. IEEE. https://doi.org/10.1109/TIT.2022.3148779","mla":"Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” IEEE Transactions on Information Theory, vol. 68, no. 6, IEEE, 2022, pp. 3823–28, doi:10.1109/TIT.2022.3148779.","ista":"Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius for Reed-Solomon codes. IEEE Transactions on Information Theory. 68(6), 3823–3828.","ieee":"A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” IEEE Transactions on Information Theory, vol. 68, no. 6. IEEE, pp. 3823–3828, 2022."},"main_file_link":[{"url":"https://arxiv.org/abs/2012.10584","open_access":"1"}],"publication":"IEEE Transactions on Information Theory","external_id":{"isi":["000799622500022"],"arxiv":["2012.10584"]},"corr_author":"1","date_updated":"2025-07-10T11:50:08Z","publication_identifier":{"issn":["0018-9448"],"eissn":["1557-9654"]},"intvolume":" 68","quality_controlled":"1","language":[{"iso":"eng"}],"department":[{"_id":"MaKw"}],"date_created":"2022-02-20T23:01:34Z","title":"List-decodability with large radius for Reed-Solomon codes","oa_version":"Preprint","year":"2022","issue":"6","_id":"10775","month":"06","article_processing_charge":"No","acknowledgement":"Research supported by NSF Award DMS-1953990.","arxiv":1,"status":"public","abstract":[{"lang":"eng","text":"List-decodability of Reed–Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r = 1-ε for ε tending to zero. Our main result states that there exist Reed–Solomon codes with rate Ω(ε) which are (1 - ε, O(1/ε))-list-decodable, meaning that any Hamming ball of radius 1-ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance."}],"scopus_import":"1","date_published":"2022-06-01T00:00:00Z","oa":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"author":[{"full_name":"Ferber, Asaf","first_name":"Asaf","last_name":"Ferber"},{"full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan"},{"last_name":"Sauermann","full_name":"Sauermann, Lisa","first_name":"Lisa"}],"publication_status":"published","article_type":"original"},{"month":"02","article_processing_charge":"No","title":"List-decodability with large radius for Reed-Solomon codes","year":"2022","_id":"11145","oa_version":"Preprint","isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"publication_status":"published","author":[{"last_name":"Ferber","full_name":"Ferber, Asaf","first_name":"Asaf"},{"full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567"},{"full_name":"Sauermann, Lisa","first_name":"Lisa","last_name":"Sauermann"}],"conference":{"location":"Denver, CO, United States","start_date":"2022-02-07","end_date":"2022-02-10","name":"FOCS: Foundations of Computer Science"},"arxiv":1,"abstract":[{"text":"List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.","lang":"eng"}],"date_published":"2022-02-01T00:00:00Z","scopus_import":"1","status":"public","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2012.10584","open_access":"1"}],"publication":"62nd Annual IEEE Symposium on Foundations of Computer Science","page":"720-726","day":"01","publisher":"IEEE","doi":"10.1109/FOCS52979.2021.00075","related_material":{"record":[{"id":"10775","relation":"later_version","status":"public"}]},"type":"conference","citation":{"short":"A. Ferber, M.A. Kwan, L. Sauermann, in:, 62nd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2022, pp. 720–726.","ieee":"A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” in 62nd Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.","mla":"Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” 62nd Annual IEEE Symposium on Foundations of Computer Science, vol. 2022, IEEE, 2022, pp. 720–26, doi:10.1109/FOCS52979.2021.00075.","ista":"Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2022, 720–726.","apa":"Ferber, A., Kwan, M. A., & Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. In 62nd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE. https://doi.org/10.1109/FOCS52979.2021.00075","ama":"Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. In: 62nd Annual IEEE Symposium on Foundations of Computer Science. Vol 2022. IEEE; 2022:720-726. doi:10.1109/FOCS52979.2021.00075","chicago":"Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” In 62nd Annual IEEE Symposium on Foundations of Computer Science, 2022:720–26. IEEE, 2022. https://doi.org/10.1109/FOCS52979.2021.00075."},"volume":2022,"date_created":"2022-04-10T22:01:40Z","department":[{"_id":"MaKw"}],"date_updated":"2025-07-10T11:50:08Z","external_id":{"isi":["000802209600065"],"arxiv":["2012.10584"]},"intvolume":" 2022","language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"issn":["0272-5428"],"isbn":["9781665420556"]}},{"department":[{"_id":"MaKw"}],"date_created":"2022-04-17T22:01:48Z","file_date_updated":"2023-02-03T09:43:38Z","tmp":{"short":"CC BY-NC (4.0)","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"intvolume":" 54","quality_controlled":"1","language":[{"iso":"eng"}],"external_id":{"isi":["000779920900001"],"arxiv":["2106.11932"]},"corr_author":"1","date_updated":"2024-10-09T21:02:21Z","has_accepted_license":"1","publication":"Bulletin of the London Mathematical Society","volume":54,"citation":{"short":"M.A. Kwan, A. Sah, M. Sawhney, Bulletin of the London Mathematical Society 54 (2022) 1420–1438.","apa":"Kwan, M. A., Sah, A., & Sawhney, M. (2022). Large deviations in random latin squares. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.12638","ista":"Kwan MA, Sah A, Sawhney M. 2022. Large deviations in random latin squares. Bulletin of the London Mathematical Society. 54(4), 1420–1438.","mla":"Kwan, Matthew Alan, et al. “Large Deviations in Random Latin Squares.” Bulletin of the London Mathematical Society, vol. 54, no. 4, Wiley, 2022, pp. 1420–38, doi:10.1112/blms.12638.","ieee":"M. A. Kwan, A. Sah, and M. Sawhney, “Large deviations in random latin squares,” Bulletin of the London Mathematical Society, vol. 54, no. 4. Wiley, pp. 1420–1438, 2022.","ama":"Kwan MA, Sah A, Sawhney M. Large deviations in random latin squares. Bulletin of the London Mathematical Society. 2022;54(4):1420-1438. doi:10.1112/blms.12638","chicago":"Kwan, Matthew Alan, Ashwin Sah, and Mehtaab Sawhney. “Large Deviations in Random Latin Squares.” Bulletin of the London Mathematical Society. Wiley, 2022. https://doi.org/10.1112/blms.12638."},"type":"journal_article","page":"1420-1438","publisher":"Wiley","day":"01","doi":"10.1112/blms.12638","author":[{"full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567"},{"last_name":"Sah","first_name":"Ashwin","full_name":"Sah, Ashwin"},{"last_name":"Sawhney","full_name":"Sawhney, Mehtaab","first_name":"Mehtaab"}],"publication_status":"published","article_type":"original","oa":1,"file":[{"date_updated":"2023-02-03T09:43:38Z","file_name":"2022_BulletinMathSociety_Kwan.pdf","checksum":"02d74e7ae955ba3c808e2a8aebe6ef98","success":1,"file_size":233758,"relation":"main_file","file_id":"12499","access_level":"open_access","creator":"dernst","date_created":"2023-02-03T09:43:38Z","content_type":"application/pdf"}],"isi":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","abstract":[{"lang":"eng","text":"In this note, we study large deviations of the number 𝐍 of intercalates ( 2×2 combinatorial subsquares which are themselves Latin squares) in a random 𝑛×𝑛 Latin square. In particular, for constant 𝛿>0 we prove that exp(−𝑂(𝑛2log𝑛))⩽Pr(𝐍⩽(1−𝛿)𝑛2/4)⩽exp(−Ω(𝑛2)) and exp(−𝑂(𝑛4/3(log𝑛)))⩽Pr(𝐍⩾(1+𝛿)𝑛2/4)⩽exp(−Ω(𝑛4/3(log𝑛)2/3)) . As a consequence, we deduce that a typical order- 𝑛 Latin square has (1+𝑜(1))𝑛2/4 intercalates, matching a lower bound due to Kwan and Sudakov and resolving an old conjecture of McKay and Wanless."}],"scopus_import":"1","date_published":"2022-08-01T00:00:00Z","acknowledgement":"We thank Zach Hunter for pointing out some important typographical errors. We also thank the referee for several remarks which helped improve the paper substantially.\r\nKwan was supported by NSF grant DMS-1953990. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302.","arxiv":1,"ddc":["510"],"article_processing_charge":"No","month":"08","oa_version":"Published Version","year":"2022","_id":"11186","issue":"4","title":"Large deviations in random latin squares"}]