[{"title":"Substructures in Latin squares","arxiv":1,"day":"01","author":[{"first_name":"Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"full_name":"Sah, Ashwin","last_name":"Sah","first_name":"Ashwin"},{"full_name":"Sawhney, Mehtaab","first_name":"Mehtaab","last_name":"Sawhney"},{"full_name":"Simkin, Michael","last_name":"Simkin","first_name":"Michael"}],"scopus_import":"1","article_processing_charge":"Yes (in subscription journal)","article_type":"original","publication":"Israel Journal of Mathematics","department":[{"_id":"MaKw"}],"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.1007/s11856-023-2513-9","publication_identifier":{"eissn":["1565-8511"],"issn":["0021-2172"]},"language":[{"iso":"eng"}],"issue":"2","date_created":"2023-10-22T22:01:14Z","volume":256,"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."}],"date_updated":"2023-10-31T11:27:30Z","month":"09","type":"journal_article","oa_version":"Preprint","page":"363-416","_id":"14444","year":"2023","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.","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2202.05088","open_access":"1"}],"date_published":"2023-09-01T00:00:00Z","oa":1,"publication_status":"published","citation":{"ieee":"M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “Substructures in Latin squares,” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2. Springer Nature, pp. 363–416, 2023.","chicago":"Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “Substructures in Latin Squares.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s11856-023-2513-9\">https://doi.org/10.1007/s11856-023-2513-9</a>.","short":"M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Israel Journal of Mathematics 256 (2023) 363–416.","ama":"Kwan MA, Sah A, Sawhney M, Simkin M. Substructures in Latin squares. <i>Israel Journal of Mathematics</i>. 2023;256(2):363-416. doi:<a href=\"https://doi.org/10.1007/s11856-023-2513-9\">10.1007/s11856-023-2513-9</a>","mla":"Kwan, Matthew Alan, et al. “Substructures in Latin Squares.” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 363–416, doi:<a href=\"https://doi.org/10.1007/s11856-023-2513-9\">10.1007/s11856-023-2513-9</a>.","ista":"Kwan MA, Sah A, Sawhney M, Simkin M. 2023. Substructures in Latin squares. Israel Journal of Mathematics. 256(2), 363–416.","apa":"Kwan, M. A., Sah, A., Sawhney, M., &#38; Simkin, M. (2023). Substructures in Latin squares. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11856-023-2513-9\">https://doi.org/10.1007/s11856-023-2513-9</a>"},"intvolume":"       256","external_id":{"arxiv":["2202.05088"]},"status":"public"},{"doi":"10.1017/fmp.2023.17","quality_controlled":"1","publication_identifier":{"issn":["2050-5086"]},"keyword":["Discrete Mathematics and Combinatorics","Geometry and Topology","Mathematical Physics","Statistics and Probability","Algebra and Number Theory","Analysis"],"language":[{"iso":"eng"}],"project":[{"grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics"}],"article_number":"e21","arxiv":1,"title":"Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture","author":[{"full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","first_name":"Matthew Alan"},{"full_name":"Sah, Ashwin","first_name":"Ashwin","last_name":"Sah"},{"full_name":"Sauermann, Lisa","first_name":"Lisa","last_name":"Sauermann"},{"first_name":"Mehtaab","last_name":"Sawhney","full_name":"Sawhney, Mehtaab"}],"file":[{"date_created":"2023-11-07T09:16:23Z","access_level":"open_access","file_id":"14500","date_updated":"2023-11-07T09:16:23Z","checksum":"54b824098d59073cc87a308d458b0a3e","file_size":1218719,"content_type":"application/pdf","relation":"main_file","creator":"dernst","file_name":"2023_ForumMathematics_Kwan.pdf","success":1}],"day":"24","publication":"Forum of Mathematics, Pi","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)"},"article_type":"original","article_processing_charge":"Yes","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Cambridge University Press","department":[{"_id":"MaKw"}],"date_published":"2023-08-24T00:00:00Z","ddc":["510"],"publication_status":"published","oa":1,"has_accepted_license":"1","intvolume":"        11","citation":{"short":"M.A. Kwan, A. Sah, L. Sauermann, M. Sawhney, Forum of Mathematics, Pi 11 (2023).","ieee":"M. A. Kwan, A. Sah, L. Sauermann, and M. Sawhney, “Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture,” <i>Forum of Mathematics, Pi</i>, vol. 11. Cambridge University Press, 2023.","chicago":"Kwan, Matthew Alan, Ashwin Sah, Lisa Sauermann, and Mehtaab Sawhney. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” <i>Forum of Mathematics, Pi</i>. Cambridge University Press, 2023. <a href=\"https://doi.org/10.1017/fmp.2023.17\">https://doi.org/10.1017/fmp.2023.17</a>.","mla":"Kwan, Matthew Alan, et al. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” <i>Forum of Mathematics, Pi</i>, vol. 11, e21, Cambridge University Press, 2023, doi:<a href=\"https://doi.org/10.1017/fmp.2023.17\">10.1017/fmp.2023.17</a>.","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., &#38; Sawhney, M. (2023). Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. <i>Forum of Mathematics, Pi</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fmp.2023.17\">https://doi.org/10.1017/fmp.2023.17</a>","ama":"Kwan MA, Sah A, Sauermann L, Sawhney M. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. <i>Forum of Mathematics, Pi</i>. 2023;11. doi:<a href=\"https://doi.org/10.1017/fmp.2023.17\">10.1017/fmp.2023.17</a>"},"status":"public","external_id":{"arxiv":["2208.02874"]},"volume":11,"date_created":"2023-11-07T09:02:48Z","file_date_updated":"2023-11-07T09:16:23Z","oa_version":"Published Version","month":"08","type":"journal_article","date_updated":"2023-11-07T09:18:57Z","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"}],"_id":"14499","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.","year":"2023"},{"status":"public","external_id":{"arxiv":["2012.10584"],"isi":["000799622500022"]},"intvolume":"        68","related_material":{"record":[{"id":"11145","status":"public","relation":"earlier_version"}]},"citation":{"ama":"Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. <i>IEEE Transactions on Information Theory</i>. 2022;68(6):3823-3828. doi:<a href=\"https://doi.org/10.1109/TIT.2022.3148779\">10.1109/TIT.2022.3148779</a>","mla":"Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” <i>IEEE Transactions on Information Theory</i>, vol. 68, no. 6, IEEE, 2022, pp. 3823–28, doi:<a href=\"https://doi.org/10.1109/TIT.2022.3148779\">10.1109/TIT.2022.3148779</a>.","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.","apa":"Ferber, A., Kwan, M. A., &#38; Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/TIT.2022.3148779\">https://doi.org/10.1109/TIT.2022.3148779</a>","ieee":"A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” <i>IEEE Transactions on Information Theory</i>, vol. 68, no. 6. IEEE, pp. 3823–3828, 2022.","chicago":"Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2022. <a href=\"https://doi.org/10.1109/TIT.2022.3148779\">https://doi.org/10.1109/TIT.2022.3148779</a>.","short":"A. Ferber, M.A. Kwan, L. Sauermann, IEEE Transactions on Information Theory 68 (2022) 3823–3828."},"oa":1,"publication_status":"published","date_published":"2022-06-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/2012.10584","open_access":"1"}],"acknowledgement":"Research supported by NSF Award DMS-1953990.","year":"2022","_id":"10775","page":"3823-3828","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."}],"date_updated":"2023-08-03T06:57:01Z","oa_version":"Preprint","month":"06","type":"journal_article","volume":68,"date_created":"2022-02-20T23:01:34Z","isi":1,"language":[{"iso":"eng"}],"issue":"6","publication_identifier":{"issn":["0018-9448"],"eissn":["1557-9654"]},"doi":"10.1109/TIT.2022.3148779","quality_controlled":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"IEEE","department":[{"_id":"MaKw"}],"publication":"IEEE Transactions on Information Theory","scopus_import":"1","article_processing_charge":"No","article_type":"original","author":[{"full_name":"Ferber, Asaf","first_name":"Asaf","last_name":"Ferber"},{"first_name":"Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan"},{"full_name":"Sauermann, Lisa","last_name":"Sauermann","first_name":"Lisa"}],"day":"01","arxiv":1,"title":"List-decodability with large radius for Reed-Solomon codes"},{"related_material":{"record":[{"relation":"later_version","id":"10775","status":"public"}]},"intvolume":"      2022","citation":{"ama":"Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. In: <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2022. IEEE; 2022:720-726. doi:<a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">10.1109/FOCS52979.2021.00075</a>","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: Symposium on Foundations of Computer Science vol. 2022, 720–726.","mla":"Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2022, IEEE, 2022, pp. 720–26, doi:<a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">10.1109/FOCS52979.2021.00075</a>.","apa":"Ferber, A., Kwan, M. A., &#38; Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. In <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE. <a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">https://doi.org/10.1109/FOCS52979.2021.00075</a>","ieee":"A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” in <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.","chicago":"Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” In <i>62nd Annual IEEE Symposium on Foundations of Computer Science</i>, 2022:720–26. IEEE, 2022. <a href=\"https://doi.org/10.1109/FOCS52979.2021.00075\">https://doi.org/10.1109/FOCS52979.2021.00075</a>.","short":"A. Ferber, M.A. Kwan, L. Sauermann, in:, 62nd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2022, pp. 720–726."},"status":"public","external_id":{"arxiv":["2012.10584"],"isi":["000802209600065"]},"date_published":"2022-02-01T00:00:00Z","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2012.10584","open_access":"1"}],"oa":1,"publication_status":"published","_id":"11145","year":"2022","volume":2022,"date_created":"2022-04-10T22:01:40Z","page":"720-726","date_updated":"2023-08-03T06:57:02Z","abstract":[{"lang":"eng","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."}],"oa_version":"Preprint","month":"02","type":"conference","isi":1,"conference":{"start_date":"2022-02-07","name":"FOCS: Symposium on Foundations of Computer Science","location":"Denver, CO, United States","end_date":"2022-02-10"},"language":[{"iso":"eng"}],"doi":"10.1109/FOCS52979.2021.00075","quality_controlled":"1","publication_identifier":{"issn":["0272-5428"],"isbn":["9781665420556"]},"publication":"62nd Annual IEEE Symposium on Foundations of Computer Science","article_processing_charge":"No","scopus_import":"1","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"IEEE","department":[{"_id":"MaKw"}],"title":"List-decodability with large radius for Reed-Solomon codes","arxiv":1,"author":[{"last_name":"Ferber","first_name":"Asaf","full_name":"Ferber, Asaf"},{"last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"first_name":"Lisa","last_name":"Sauermann","full_name":"Sauermann, Lisa"}],"day":"01"},{"external_id":{"arxiv":["2106.11932"],"isi":["000779920900001"]},"status":"public","intvolume":"        54","citation":{"apa":"Kwan, M. A., Sah, A., &#38; Sawhney, M. (2022). Large deviations in random latin squares. <i>Bulletin of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/blms.12638\">https://doi.org/10.1112/blms.12638</a>","mla":"Kwan, Matthew Alan, et al. “Large Deviations in Random Latin Squares.” <i>Bulletin of the London Mathematical Society</i>, vol. 54, no. 4, Wiley, 2022, pp. 1420–38, doi:<a href=\"https://doi.org/10.1112/blms.12638\">10.1112/blms.12638</a>.","ista":"Kwan MA, Sah A, Sawhney M. 2022. Large deviations in random latin squares. Bulletin of the London Mathematical Society. 54(4), 1420–1438.","ama":"Kwan MA, Sah A, Sawhney M. Large deviations in random latin squares. <i>Bulletin of the London Mathematical Society</i>. 2022;54(4):1420-1438. doi:<a href=\"https://doi.org/10.1112/blms.12638\">10.1112/blms.12638</a>","short":"M.A. Kwan, A. Sah, M. Sawhney, Bulletin of the London Mathematical Society 54 (2022) 1420–1438.","chicago":"Kwan, Matthew Alan, Ashwin Sah, and Mehtaab Sawhney. “Large Deviations in Random Latin Squares.” <i>Bulletin of the London Mathematical Society</i>. Wiley, 2022. <a href=\"https://doi.org/10.1112/blms.12638\">https://doi.org/10.1112/blms.12638</a>.","ieee":"M. A. Kwan, A. Sah, and M. Sawhney, “Large deviations in random latin squares,” <i>Bulletin of the London Mathematical Society</i>, vol. 54, no. 4. Wiley, pp. 1420–1438, 2022."},"oa":1,"publication_status":"published","has_accepted_license":"1","ddc":["510"],"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.","year":"2022","_id":"11186","page":"1420-1438","date_updated":"2023-08-03T06:47:29Z","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."}],"type":"journal_article","month":"08","oa_version":"Published Version","volume":54,"file_date_updated":"2023-02-03T09:43:38Z","date_created":"2022-04-17T22:01:48Z","isi":1,"language":[{"iso":"eng"}],"issue":"4","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"doi":"10.1112/blms.12638","quality_controlled":"1","publisher":"Wiley","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","department":[{"_id":"MaKw"}],"publication":"Bulletin of the London Mathematical Society","article_processing_charge":"No","scopus_import":"1","article_type":"original","tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)","image":"/images/cc_by_nc.png","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode"},"author":[{"last_name":"Kwan","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"full_name":"Sah, Ashwin","last_name":"Sah","first_name":"Ashwin"},{"last_name":"Sawhney","first_name":"Mehtaab","full_name":"Sawhney, Mehtaab"}],"file":[{"file_id":"12499","date_updated":"2023-02-03T09:43:38Z","checksum":"02d74e7ae955ba3c808e2a8aebe6ef98","date_created":"2023-02-03T09:43:38Z","access_level":"open_access","file_name":"2022_BulletinMathSociety_Kwan.pdf","success":1,"file_size":233758,"relation":"main_file","content_type":"application/pdf","creator":"dernst"}],"license":"https://creativecommons.org/licenses/by-nc/4.0/","day":"01","title":"Large deviations in random latin squares","arxiv":1},{"date_updated":"2023-08-03T07:17:37Z","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."}],"type":"journal_article","month":"06","oa_version":"Preprint","page":"4209-4250","date_created":"2022-06-12T22:01:45Z","volume":375,"year":"2022","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. ","_id":"11443","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2006.08836"}],"date_published":"2022-06-01T00:00:00Z","status":"public","external_id":{"isi":["000798461500001"],"arxiv":["2006.08836"]},"citation":{"chicago":"Kwan, Matthew Alan, Lisa Sauermann, and Yufei Zhao. “Extension Complexity of Low-Dimensional Polytopes.” <i>Transactions of the American Mathematical Society</i>. American Mathematical Society, 2022. <a href=\"https://doi.org/10.1090/tran/8614\">https://doi.org/10.1090/tran/8614</a>.","ieee":"M. A. Kwan, L. Sauermann, and Y. Zhao, “Extension complexity of low-dimensional polytopes,” <i>Transactions of the American Mathematical Society</i>, vol. 375, no. 6. American Mathematical Society, pp. 4209–4250, 2022.","short":"M.A. Kwan, L. Sauermann, Y. Zhao, Transactions of the American Mathematical Society 375 (2022) 4209–4250.","ama":"Kwan MA, Sauermann L, Zhao Y. Extension complexity of low-dimensional polytopes. <i>Transactions of the American Mathematical Society</i>. 2022;375(6):4209-4250. doi:<a href=\"https://doi.org/10.1090/tran/8614\">10.1090/tran/8614</a>","apa":"Kwan, M. A., Sauermann, L., &#38; Zhao, Y. (2022). Extension complexity of low-dimensional polytopes. <i>Transactions of the American Mathematical Society</i>. American Mathematical Society. <a href=\"https://doi.org/10.1090/tran/8614\">https://doi.org/10.1090/tran/8614</a>","mla":"Kwan, Matthew Alan, et al. “Extension Complexity of Low-Dimensional Polytopes.” <i>Transactions of the American Mathematical Society</i>, vol. 375, no. 6, American Mathematical Society, 2022, pp. 4209–50, doi:<a href=\"https://doi.org/10.1090/tran/8614\">10.1090/tran/8614</a>.","ista":"Kwan MA, Sauermann L, Zhao Y. 2022. Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society. 375(6), 4209–4250."},"intvolume":"       375","day":"01","author":[{"last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan"},{"full_name":"Sauermann, Lisa","last_name":"Sauermann","first_name":"Lisa"},{"full_name":"Zhao, Yufei","last_name":"Zhao","first_name":"Yufei"}],"arxiv":1,"title":"Extension complexity of low-dimensional polytopes","department":[{"_id":"MaKw"}],"publisher":"American Mathematical Society","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","scopus_import":"1","article_processing_charge":"No","article_type":"original","publication":"Transactions of the American Mathematical Society","publication_identifier":{"eissn":["1088-6850"],"issn":["0002-9947"]},"quality_controlled":"1","doi":"10.1090/tran/8614","language":[{"iso":"eng"}],"issue":"6","isi":1},{"title":"Acyclic subgraphs of tournaments with high chromatic number","arxiv":1,"author":[{"first_name":"Jacob","last_name":"Fox","full_name":"Fox, Jacob"},{"last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"last_name":"Sudakov","first_name":"Benny","full_name":"Sudakov, Benny"}],"day":"03","publication":"Bulletin of the London Mathematical Society","article_processing_charge":"No","scopus_import":"1","article_type":"original","publisher":"Wiley","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","doi":"10.1112/blms.12446","quality_controlled":"1","publication_identifier":{"eissn":["1469-2120"],"issn":["0024-6093"]},"language":[{"iso":"eng"}],"issue":"2","volume":53,"date_created":"2021-06-21T06:11:56Z","page":"619-630","abstract":[{"lang":"eng","text":"We prove that every n-vertex tournament G has an acyclic subgraph with chromatic number at least n5/9−o(1), while there exists an n-vertex tournament G whose every acyclic subgraph has chromatic number at most n3/4+o(1). This establishes in a strong form a conjecture of Nassar and Yuster and improves on another result of theirs. Our proof combines probabilistic and spectral techniques together with some additional ideas. In particular, we prove a lemma showing that every tournament with many transitive subtournaments has a large subtournament that is almost transitive. This may be of independent interest."}],"date_updated":"2023-02-23T14:01:21Z","oa_version":"Preprint","type":"journal_article","month":"04","_id":"9572","year":"2021","date_published":"2021-04-03T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1912.07722","open_access":"1"}],"oa":1,"publication_status":"published","intvolume":"        53","extern":"1","citation":{"ieee":"J. Fox, M. A. Kwan, and B. Sudakov, “Acyclic subgraphs of tournaments with high chromatic number,” <i>Bulletin of the London Mathematical Society</i>, vol. 53, no. 2. Wiley, pp. 619–630, 2021.","chicago":"Fox, Jacob, Matthew Alan Kwan, and Benny Sudakov. “Acyclic Subgraphs of Tournaments with High Chromatic Number.” <i>Bulletin of the London Mathematical Society</i>. Wiley, 2021. <a href=\"https://doi.org/10.1112/blms.12446\">https://doi.org/10.1112/blms.12446</a>.","short":"J. Fox, M.A. Kwan, B. Sudakov, Bulletin of the London Mathematical Society 53 (2021) 619–630.","ama":"Fox J, Kwan MA, Sudakov B. Acyclic subgraphs of tournaments with high chromatic number. <i>Bulletin of the London Mathematical Society</i>. 2021;53(2):619-630. doi:<a href=\"https://doi.org/10.1112/blms.12446\">10.1112/blms.12446</a>","ista":"Fox J, Kwan MA, Sudakov B. 2021. Acyclic subgraphs of tournaments with high chromatic number. Bulletin of the London Mathematical Society. 53(2), 619–630.","mla":"Fox, Jacob, et al. “Acyclic Subgraphs of Tournaments with High Chromatic Number.” <i>Bulletin of the London Mathematical Society</i>, vol. 53, no. 2, Wiley, 2021, pp. 619–30, doi:<a href=\"https://doi.org/10.1112/blms.12446\">10.1112/blms.12446</a>.","apa":"Fox, J., Kwan, M. A., &#38; Sudakov, B. (2021). Acyclic subgraphs of tournaments with high chromatic number. <i>Bulletin of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/blms.12446\">https://doi.org/10.1112/blms.12446</a>"},"external_id":{"arxiv":["1912.07722"]},"status":"public"},{"volume":52,"date_created":"2021-06-21T06:23:42Z","page":"515-529","oa_version":"Preprint","month":"06","type":"journal_article","abstract":[{"lang":"eng","text":"It is a classical fact that for any ε>0, a random permutation of length n=(1+ε)k2/4 typically contains a monotone subsequence of length k. As a far-reaching generalization, Alon conjectured that a random permutation of this same length n is typically k-universal, meaning that it simultaneously contains every pattern of length k. He also made the simple observation that for n=O(k2logk), a random length-n permutation is typically k-universal. We make the first significant progress towards Alon's conjecture by showing that n=2000k2loglogk suffices."}],"date_updated":"2023-02-23T14:01:23Z","_id":"9573","year":"2020","date_published":"2020-06-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1911.12878","open_access":"1"}],"publication_status":"published","oa":1,"intvolume":"        52","extern":"1","citation":{"ieee":"X. He and M. A. Kwan, “Universality of random permutations,” <i>Bulletin of the London Mathematical Society</i>, vol. 52, no. 3. Wiley, pp. 515–529, 2020.","chicago":"He, Xiaoyu, and Matthew Alan Kwan. “Universality of Random Permutations.” <i>Bulletin of the London Mathematical Society</i>. Wiley, 2020. <a href=\"https://doi.org/10.1112/blms.12345\">https://doi.org/10.1112/blms.12345</a>.","short":"X. He, M.A. Kwan, Bulletin of the London Mathematical Society 52 (2020) 515–529.","ama":"He X, Kwan MA. Universality of random permutations. <i>Bulletin of the London Mathematical Society</i>. 2020;52(3):515-529. doi:<a href=\"https://doi.org/10.1112/blms.12345\">10.1112/blms.12345</a>","ista":"He X, Kwan MA. 2020. Universality of random permutations. Bulletin of the London Mathematical Society. 52(3), 515–529.","mla":"He, Xiaoyu, and Matthew Alan Kwan. “Universality of Random Permutations.” <i>Bulletin of the London Mathematical Society</i>, vol. 52, no. 3, Wiley, 2020, pp. 515–29, doi:<a href=\"https://doi.org/10.1112/blms.12345\">10.1112/blms.12345</a>.","apa":"He, X., &#38; Kwan, M. A. (2020). Universality of random permutations. <i>Bulletin of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/blms.12345\">https://doi.org/10.1112/blms.12345</a>"},"status":"public","external_id":{"arxiv":["1911.12878"]},"title":"Universality of random permutations","arxiv":1,"author":[{"first_name":"Xiaoyu","last_name":"He","full_name":"He, Xiaoyu"},{"last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"}],"day":"01","publication":"Bulletin of the London Mathematical Society","article_type":"original","article_processing_charge":"No","scopus_import":"1","publisher":"Wiley","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","doi":"10.1112/blms.12345","quality_controlled":"1","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"issue":"3","language":[{"iso":"eng"}]},{"publication_identifier":{"issn":["1073-7928"],"eissn":["1687-0247"]},"doi":"10.1093/imrn/rnaa004","quality_controlled":"1","language":[{"iso":"eng"}],"issue":"21","author":[{"last_name":"Bucić","first_name":"Matija","full_name":"Bucić, Matija"},{"full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","last_name":"Kwan","first_name":"Matthew Alan"},{"first_name":"Alexey","last_name":"Pokrovskiy","full_name":"Pokrovskiy, Alexey"},{"last_name":"Sudakov","first_name":"Benny","full_name":"Sudakov, Benny"}],"day":"01","title":"Halfway to Rota’s basis conjecture","arxiv":1,"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Oxford University Press","publication":"International Mathematics Research Notices","article_processing_charge":"No","scopus_import":"1","article_type":"original","oa":1,"publication_status":"published","date_published":"2020-11-01T00:00:00Z","main_file_link":[{"url":"http://arxiv-export-lb.library.cornell.edu/abs/1810.07462","open_access":"1"}],"status":"public","external_id":{"arxiv":["1810.07462"]},"extern":"1","intvolume":"      2020","citation":{"chicago":"Bucić, Matija, Matthew Alan Kwan, Alexey Pokrovskiy, and Benny Sudakov. “Halfway to Rota’s Basis Conjecture.” <i>International Mathematics Research Notices</i>. Oxford University Press, 2020. <a href=\"https://doi.org/10.1093/imrn/rnaa004\">https://doi.org/10.1093/imrn/rnaa004</a>.","ieee":"M. Bucić, M. A. Kwan, A. Pokrovskiy, and B. Sudakov, “Halfway to Rota’s basis conjecture,” <i>International Mathematics Research Notices</i>, vol. 2020, no. 21. Oxford University Press, pp. 8007–8026, 2020.","short":"M. Bucić, M.A. Kwan, A. Pokrovskiy, B. Sudakov, International Mathematics Research Notices 2020 (2020) 8007–8026.","ama":"Bucić M, Kwan MA, Pokrovskiy A, Sudakov B. Halfway to Rota’s basis conjecture. <i>International Mathematics Research Notices</i>. 2020;2020(21):8007-8026. doi:<a href=\"https://doi.org/10.1093/imrn/rnaa004\">10.1093/imrn/rnaa004</a>","apa":"Bucić, M., Kwan, M. A., Pokrovskiy, A., &#38; Sudakov, B. (2020). Halfway to Rota’s basis conjecture. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rnaa004\">https://doi.org/10.1093/imrn/rnaa004</a>","mla":"Bucić, Matija, et al. “Halfway to Rota’s Basis Conjecture.” <i>International Mathematics Research Notices</i>, vol. 2020, no. 21, Oxford University Press, 2020, pp. 8007–26, doi:<a href=\"https://doi.org/10.1093/imrn/rnaa004\">10.1093/imrn/rnaa004</a>.","ista":"Bucić M, Kwan MA, Pokrovskiy A, Sudakov B. 2020. Halfway to Rota’s basis conjecture. International Mathematics Research Notices. 2020(21), 8007–8026."},"page":"8007-8026","date_updated":"2023-02-23T14:01:30Z","abstract":[{"lang":"eng","text":"In 1989, Rota made the following conjecture. Given n bases B1,…,Bn in an n-dimensional vector space V⁠, one can always find n disjoint bases of V⁠, each containing exactly one element from each Bi (we call such bases transversal bases). Rota’s basis conjecture remains wide open despite its apparent simplicity and the efforts of many researchers (e.g., the conjecture was recently the subject of the collaborative “Polymath” project). In this paper we prove that one can always find (1/2−o(1))n disjoint transversal bases, improving on the previous best bound of Ω(n/logn)⁠. Our results also apply to the more general setting of matroids."}],"oa_version":"Preprint","type":"journal_article","month":"11","volume":2020,"date_created":"2021-06-21T08:12:30Z","year":"2020","_id":"9576"},{"page":"1621–1638","abstract":[{"text":"An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clogn⁠. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. Motivated by an old problem of Erd̋s and McKay, recently Narayanan, Sahasrabudhe, and Tomon conjectured that for any fixed C, every n-vertex C-Ramsey graph induces subgraphs of Θ(n2) different sizes. In this paper we prove this conjecture.","lang":"eng"}],"date_updated":"2023-02-23T14:01:33Z","type":"journal_article","month":"03","oa_version":"Published Version","volume":2020,"date_created":"2021-06-21T08:30:12Z","year":"2020","_id":"9577","publication_status":"published","oa":1,"date_published":"2020-03-01T00:00:00Z","main_file_link":[{"url":"https://doi.org/10.1093/imrn/rny064","open_access":"1"}],"status":"public","external_id":{"arxiv":["1711.02937"]},"extern":"1","intvolume":"      2020","citation":{"short":"M.A. Kwan, B. Sudakov, International Mathematics Research Notices 2020 (2020) 1621–1638.","ieee":"M. A. Kwan and B. Sudakov, “Ramsey graphs induce subgraphs of quadratically many sizes,” <i>International Mathematics Research Notices</i>, vol. 2020, no. 6. Oxford University Press, pp. 1621–1638, 2020.","chicago":"Kwan, Matthew Alan, and Benny Sudakov. “Ramsey Graphs Induce Subgraphs of Quadratically Many Sizes.” <i>International Mathematics Research Notices</i>. Oxford University Press, 2020. <a href=\"https://doi.org/10.1093/imrn/rny064\">https://doi.org/10.1093/imrn/rny064</a>.","ista":"Kwan MA, Sudakov B. 2020. Ramsey graphs induce subgraphs of quadratically many sizes. International Mathematics Research Notices. 2020(6), 1621–1638.","mla":"Kwan, Matthew Alan, and Benny Sudakov. “Ramsey Graphs Induce Subgraphs of Quadratically Many Sizes.” <i>International Mathematics Research Notices</i>, vol. 2020, no. 6, Oxford University Press, 2020, pp. 1621–1638, doi:<a href=\"https://doi.org/10.1093/imrn/rny064\">10.1093/imrn/rny064</a>.","apa":"Kwan, M. A., &#38; Sudakov, B. (2020). Ramsey graphs induce subgraphs of quadratically many sizes. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rny064\">https://doi.org/10.1093/imrn/rny064</a>","ama":"Kwan MA, Sudakov B. Ramsey graphs induce subgraphs of quadratically many sizes. <i>International Mathematics Research Notices</i>. 2020;2020(6):1621–1638. doi:<a href=\"https://doi.org/10.1093/imrn/rny064\">10.1093/imrn/rny064</a>"},"author":[{"first_name":"Matthew Alan","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567"},{"full_name":"Sudakov, Benny","last_name":"Sudakov","first_name":"Benny"}],"day":"01","title":"Ramsey graphs induce subgraphs of quadratically many sizes","arxiv":1,"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Oxford University Press","publication":"International Mathematics Research Notices","article_processing_charge":"No","scopus_import":"1","article_type":"original","publication_identifier":{"issn":["1073-7928"],"eissn":["1687-0247"]},"doi":"10.1093/imrn/rny064","quality_controlled":"1","language":[{"iso":"eng"}],"issue":"6"},{"oa_version":"Preprint","month":"07","type":"journal_article","abstract":[{"text":"How long a monotone path can one always find in any edge-ordering of the complete graph Kn? This appealing question was first asked by Chvátal and Komlós in 1971, and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was n2/3-o(1). In this paper we almost close this gap, proving that any edge-ordering of the complete graph contains a monotone path of length n1-o(1).","lang":"eng"}],"date_updated":"2023-02-23T14:01:35Z","page":"663-685","date_created":"2021-06-21T13:24:35Z","volume":238,"year":"2020","_id":"9578","oa":1,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1809.01468"}],"date_published":"2020-07-01T00:00:00Z","external_id":{"arxiv":["1809.01468"]},"status":"public","citation":{"short":"M. Bucić, M.A. Kwan, A. Pokrovskiy, B. Sudakov, T. Tran, A.Z. Wagner, Israel Journal of Mathematics 238 (2020) 663–685.","chicago":"Bucić, Matija, Matthew Alan Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran, and Adam Zsolt Wagner. “Nearly-Linear Monotone Paths in Edge-Ordered Graphs.” <i>Israel Journal of Mathematics</i>. Springer, 2020. <a href=\"https://doi.org/10.1007/s11856-020-2035-7\">https://doi.org/10.1007/s11856-020-2035-7</a>.","ieee":"M. Bucić, M. A. Kwan, A. Pokrovskiy, B. Sudakov, T. Tran, and A. Z. Wagner, “Nearly-linear monotone paths in edge-ordered graphs,” <i>Israel Journal of Mathematics</i>, vol. 238, no. 2. Springer, pp. 663–685, 2020.","apa":"Bucić, M., Kwan, M. A., Pokrovskiy, A., Sudakov, B., Tran, T., &#38; Wagner, A. Z. (2020). Nearly-linear monotone paths in edge-ordered graphs. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-020-2035-7\">https://doi.org/10.1007/s11856-020-2035-7</a>","ista":"Bucić M, Kwan MA, Pokrovskiy A, Sudakov B, Tran T, Wagner AZ. 2020. Nearly-linear monotone paths in edge-ordered graphs. Israel Journal of Mathematics. 238(2), 663–685.","mla":"Bucić, Matija, et al. “Nearly-Linear Monotone Paths in Edge-Ordered Graphs.” <i>Israel Journal of Mathematics</i>, vol. 238, no. 2, Springer, 2020, pp. 663–85, doi:<a href=\"https://doi.org/10.1007/s11856-020-2035-7\">10.1007/s11856-020-2035-7</a>.","ama":"Bucić M, Kwan MA, Pokrovskiy A, Sudakov B, Tran T, Wagner AZ. Nearly-linear monotone paths in edge-ordered graphs. <i>Israel Journal of Mathematics</i>. 2020;238(2):663-685. doi:<a href=\"https://doi.org/10.1007/s11856-020-2035-7\">10.1007/s11856-020-2035-7</a>"},"extern":"1","intvolume":"       238","day":"01","author":[{"first_name":"Matija","last_name":"Bucić","full_name":"Bucić, Matija"},{"first_name":"Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"},{"full_name":"Pokrovskiy, Alexey","first_name":"Alexey","last_name":"Pokrovskiy"},{"full_name":"Sudakov, Benny","last_name":"Sudakov","first_name":"Benny"},{"first_name":"Tuan","last_name":"Tran","full_name":"Tran, Tuan"},{"full_name":"Wagner, Adam Zsolt","first_name":"Adam Zsolt","last_name":"Wagner"}],"arxiv":1,"title":"Nearly-linear monotone paths in edge-ordered graphs","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Springer","article_type":"original","scopus_import":"1","article_processing_charge":"No","publication":"Israel Journal of Mathematics","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"quality_controlled":"1","doi":"10.1007/s11856-020-2035-7","issue":"2","language":[{"iso":"eng"}]},{"year":"2020","_id":"9581","oa_version":"Preprint","type":"journal_article","month":"12","abstract":[{"text":"We show that for any  𝑛  divisible by 3, almost all order-  𝑛  Steiner triple systems have a perfect matching (also known as a parallel class or resolution class). In fact, we prove a general upper bound on the number of perfect matchings in a Steiner triple system and show that almost all Steiner triple systems essentially attain this maximum. We accomplish this via a general theorem comparing a uniformly random Steiner triple system to the outcome of the triangle removal process, which we hope will be useful for other problems. Our methods can also be adapted to other types of designs; for example, we sketch a proof of the theorem that almost all Latin squares have transversals.","lang":"eng"}],"date_updated":"2023-02-23T14:01:43Z","page":"1468-1495","date_created":"2021-06-22T06:35:16Z","volume":121,"status":"public","external_id":{"arxiv":["1611.02246"]},"citation":{"short":"M.A. Kwan, Proceedings of the London Mathematical Society 121 (2020) 1468–1495.","ieee":"M. A. Kwan, “Almost all Steiner triple systems have perfect matchings,” <i>Proceedings of the London Mathematical Society</i>, vol. 121, no. 6. Wiley, pp. 1468–1495, 2020.","chicago":"Kwan, Matthew Alan. “Almost All Steiner Triple Systems Have Perfect Matchings.” <i>Proceedings of the London Mathematical Society</i>. Wiley, 2020. <a href=\"https://doi.org/10.1112/plms.12373\">https://doi.org/10.1112/plms.12373</a>.","mla":"Kwan, Matthew Alan. “Almost All Steiner Triple Systems Have Perfect Matchings.” <i>Proceedings of the London Mathematical Society</i>, vol. 121, no. 6, Wiley, 2020, pp. 1468–95, doi:<a href=\"https://doi.org/10.1112/plms.12373\">10.1112/plms.12373</a>.","ista":"Kwan MA. 2020. Almost all Steiner triple systems have perfect matchings. Proceedings of the London Mathematical Society. 121(6), 1468–1495.","apa":"Kwan, M. A. (2020). Almost all Steiner triple systems have perfect matchings. <i>Proceedings of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/plms.12373\">https://doi.org/10.1112/plms.12373</a>","ama":"Kwan MA. Almost all Steiner triple systems have perfect matchings. <i>Proceedings of the London Mathematical Society</i>. 2020;121(6):1468-1495. doi:<a href=\"https://doi.org/10.1112/plms.12373\">10.1112/plms.12373</a>"},"extern":"1","intvolume":"       121","oa":1,"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.02246"}],"date_published":"2020-12-01T00:00:00Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Wiley","article_type":"original","article_processing_charge":"No","scopus_import":"1","publication":"Proceedings of the London Mathematical Society","day":"01","author":[{"first_name":"Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"}],"title":"Almost all Steiner triple systems have perfect matchings","arxiv":1,"issue":"6","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1460-244X"],"issn":["0024-6115"]},"quality_controlled":"1","doi":"10.1112/plms.12373"},{"title":"Dense induced bipartite subgraphs in triangle-free graphs","arxiv":1,"author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","last_name":"Kwan"},{"full_name":"Letzter, Shoham","last_name":"Letzter","first_name":"Shoham"},{"full_name":"Sudakov, Benny","first_name":"Benny","last_name":"Sudakov"},{"full_name":"Tran, Tuan","first_name":"Tuan","last_name":"Tran"}],"day":"01","publication":"Combinatorica","article_processing_charge":"No","scopus_import":"1","article_type":"original","publisher":"Springer","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","doi":"10.1007/s00493-019-4086-0","quality_controlled":"1","publication_identifier":{"eissn":["1439-6912"],"issn":["0209-9683"]},"language":[{"iso":"eng"}],"issue":"2","volume":40,"date_created":"2021-06-22T06:42:26Z","page":"283-305","abstract":[{"text":"The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least cH log d/log log d, thus nearly confirming one and proving another conjecture of Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak and Spencer.","lang":"eng"}],"date_updated":"2023-02-23T14:01:45Z","month":"04","type":"journal_article","oa_version":"Preprint","_id":"9582","year":"2020","date_published":"2020-04-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1810.12144"}],"publication_status":"published","oa":1,"intvolume":"        40","extern":"1","citation":{"ista":"Kwan MA, Letzter S, Sudakov B, Tran T. 2020. Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica. 40(2), 283–305.","mla":"Kwan, Matthew Alan, et al. “Dense Induced Bipartite Subgraphs in Triangle-Free Graphs.” <i>Combinatorica</i>, vol. 40, no. 2, Springer, 2020, pp. 283–305, doi:<a href=\"https://doi.org/10.1007/s00493-019-4086-0\">10.1007/s00493-019-4086-0</a>.","apa":"Kwan, M. A., Letzter, S., Sudakov, B., &#38; Tran, T. (2020). Dense induced bipartite subgraphs in triangle-free graphs. <i>Combinatorica</i>. Springer. <a href=\"https://doi.org/10.1007/s00493-019-4086-0\">https://doi.org/10.1007/s00493-019-4086-0</a>","ama":"Kwan MA, Letzter S, Sudakov B, Tran T. Dense induced bipartite subgraphs in triangle-free graphs. <i>Combinatorica</i>. 2020;40(2):283-305. doi:<a href=\"https://doi.org/10.1007/s00493-019-4086-0\">10.1007/s00493-019-4086-0</a>","short":"M.A. Kwan, S. Letzter, B. Sudakov, T. Tran, Combinatorica 40 (2020) 283–305.","ieee":"M. A. Kwan, S. Letzter, B. Sudakov, and T. Tran, “Dense induced bipartite subgraphs in triangle-free graphs,” <i>Combinatorica</i>, vol. 40, no. 2. Springer, pp. 283–305, 2020.","chicago":"Kwan, Matthew Alan, Shoham Letzter, Benny Sudakov, and Tuan Tran. “Dense Induced Bipartite Subgraphs in Triangle-Free Graphs.” <i>Combinatorica</i>. Springer, 2020. <a href=\"https://doi.org/10.1007/s00493-019-4086-0\">https://doi.org/10.1007/s00493-019-4086-0</a>."},"status":"public","external_id":{"arxiv":["1810.12144"]}},{"pmid":1,"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Cambridge University Press","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","scopus_import":"1","article_processing_charge":"No","publication":"Forum of Mathematics","file":[{"checksum":"5553c596bb4db0f38226a56bee9c87a1","date_updated":"2021-06-22T09:23:59Z","file_id":"9584","access_level":"open_access","date_created":"2021-06-22T09:23:59Z","success":1,"file_name":"2020_CambridgeUniversityPress_Ferber.pdf","creator":"asandaue","content_type":"application/pdf","relation":"main_file","file_size":601516}],"day":"03","author":[{"first_name":"Asaf","last_name":"Ferber","full_name":"Ferber, Asaf"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","last_name":"Kwan"}],"article_number":"e39","title":"Almost all Steiner triple systems are almost resolvable","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2050-5094"]},"quality_controlled":"1","doi":"10.1017/fms.2020.29","year":"2020","_id":"9583","month":"11","type":"journal_article","oa_version":"Published Version","date_updated":"2023-02-23T14:01:48Z","abstract":[{"text":"We show that for any n divisible by 3, almost all order-n Steiner triple systems admit a decomposition of almost all their triples into disjoint perfect matchings (that is, almost all Steiner triple systems are almost resolvable).","lang":"eng"}],"file_date_updated":"2021-06-22T09:23:59Z","date_created":"2021-06-22T09:12:23Z","volume":8,"external_id":{"pmid":["1907.06744"]},"status":"public","citation":{"ista":"Ferber A, Kwan MA. 2020. Almost all Steiner triple systems are almost resolvable. Forum of Mathematics. 8, e39.","mla":"Ferber, Asaf, and Matthew Alan Kwan. “Almost All Steiner Triple Systems Are Almost Resolvable.” <i>Forum of Mathematics</i>, vol. 8, e39, Cambridge University Press, 2020, doi:<a href=\"https://doi.org/10.1017/fms.2020.29\">10.1017/fms.2020.29</a>.","apa":"Ferber, A., &#38; Kwan, M. A. (2020). Almost all Steiner triple systems are almost resolvable. <i>Forum of Mathematics</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2020.29\">https://doi.org/10.1017/fms.2020.29</a>","ama":"Ferber A, Kwan MA. Almost all Steiner triple systems are almost resolvable. <i>Forum of Mathematics</i>. 2020;8. doi:<a href=\"https://doi.org/10.1017/fms.2020.29\">10.1017/fms.2020.29</a>","short":"A. Ferber, M.A. Kwan, Forum of Mathematics 8 (2020).","ieee":"A. Ferber and M. A. Kwan, “Almost all Steiner triple systems are almost resolvable,” <i>Forum of Mathematics</i>, vol. 8. Cambridge University Press, 2020.","chicago":"Ferber, Asaf, and Matthew Alan Kwan. “Almost All Steiner Triple Systems Are Almost Resolvable.” <i>Forum of Mathematics</i>. Cambridge University Press, 2020. <a href=\"https://doi.org/10.1017/fms.2020.29\">https://doi.org/10.1017/fms.2020.29</a>."},"intvolume":"         8","extern":"1","has_accepted_license":"1","publication_status":"published","oa":1,"date_published":"2020-11-03T00:00:00Z","ddc":["510"]},{"title":"Hypergraph cuts above the average","arxiv":1,"day":"01","author":[{"last_name":"Conlon","first_name":"David","full_name":"Conlon, David"},{"first_name":"Jacob","last_name":"Fox","full_name":"Fox, Jacob"},{"first_name":"Matthew Alan","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567"},{"full_name":"Sudakov, Benny","first_name":"Benny","last_name":"Sudakov"}],"article_type":"original","article_processing_charge":"No","scopus_import":"1","publication":"Israel Journal of Mathematics","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Springer","quality_controlled":"1","doi":"10.1007/s11856-019-1897-z","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"issue":"1","language":[{"iso":"eng"}],"date_created":"2021-06-21T13:36:02Z","volume":233,"oa_version":"Preprint","month":"08","type":"journal_article","date_updated":"2023-02-23T14:01:41Z","abstract":[{"lang":"eng","text":"An r-cut of a k-uniform hypergraph H is a partition of the vertex set of H into r parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω)(m−−√) and this is best possible. That is, there exist cuts which exceed the expected size of a random cut by some multiple of the standard deviation. We study analogues of this and related results in hypergraphs. First, we observe that similarly to graphs, every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m−−√) larger than the expected size of a random r-cut. Moreover, in the case where k = 3 and r = 2 this bound is best possible and is attained by Steiner triple systems. Surprisingly, for all other cases (that is, if k ≥ 4 or r ≥ 3), we show that every m-edge k-uniform hypergraph has an r-cut whose size is Ω(m5/9) larger than the expected size of a random r-cut. This is a significant difference in behaviour, since the amount by which the size of the largest cut exceeds the expected size of a random cut is now considerably larger than the standard deviation."}],"page":"67-111","_id":"9580","year":"2019","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.08462"}],"date_published":"2019-08-01T00:00:00Z","publication_status":"published","oa":1,"citation":{"short":"D. Conlon, J. Fox, M.A. Kwan, B. Sudakov, Israel Journal of Mathematics 233 (2019) 67–111.","chicago":"Conlon, David, Jacob Fox, Matthew Alan Kwan, and Benny Sudakov. “Hypergraph Cuts above the Average.” <i>Israel Journal of Mathematics</i>. Springer, 2019. <a href=\"https://doi.org/10.1007/s11856-019-1897-z\">https://doi.org/10.1007/s11856-019-1897-z</a>.","ieee":"D. Conlon, J. Fox, M. A. Kwan, and B. Sudakov, “Hypergraph cuts above the average,” <i>Israel Journal of Mathematics</i>, vol. 233, no. 1. Springer, pp. 67–111, 2019.","apa":"Conlon, D., Fox, J., Kwan, M. A., &#38; Sudakov, B. (2019). Hypergraph cuts above the average. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-019-1897-z\">https://doi.org/10.1007/s11856-019-1897-z</a>","mla":"Conlon, David, et al. “Hypergraph Cuts above the Average.” <i>Israel Journal of Mathematics</i>, vol. 233, no. 1, Springer, 2019, pp. 67–111, doi:<a href=\"https://doi.org/10.1007/s11856-019-1897-z\">10.1007/s11856-019-1897-z</a>.","ista":"Conlon D, Fox J, Kwan MA, Sudakov B. 2019. Hypergraph cuts above the average. Israel Journal of Mathematics. 233(1), 67–111.","ama":"Conlon D, Fox J, Kwan MA, Sudakov B. Hypergraph cuts above the average. <i>Israel Journal of Mathematics</i>. 2019;233(1):67-111. doi:<a href=\"https://doi.org/10.1007/s11856-019-1897-z\">10.1007/s11856-019-1897-z</a>"},"extern":"1","intvolume":"       233","external_id":{"arxiv":["1803.08462"]},"status":"public"},{"doi":"10.1090/tran/7729","quality_controlled":"1","publication_identifier":{"issn":["0002-9947"],"eissn":["1088-6850"]},"language":[{"iso":"eng"}],"issue":"8","title":"Proof of a conjecture on induced subgraphs of Ramsey graphs","arxiv":1,"author":[{"orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan"},{"first_name":"Benny","last_name":"Sudakov","full_name":"Sudakov, Benny"}],"day":"15","publication":"Transactions of the American Mathematical Society","scopus_import":"1","article_processing_charge":"No","article_type":"original","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"American Mathematical Society","date_published":"2019-10-15T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1090/tran/7729"}],"oa":1,"publication_status":"published","intvolume":"       372","extern":"1","citation":{"ama":"Kwan MA, Sudakov B. Proof of a conjecture on induced subgraphs of Ramsey graphs. <i>Transactions of the American Mathematical Society</i>. 2019;372(8):5571-5594. doi:<a href=\"https://doi.org/10.1090/tran/7729\">10.1090/tran/7729</a>","mla":"Kwan, Matthew Alan, and Benny Sudakov. “Proof of a Conjecture on Induced Subgraphs of Ramsey Graphs.” <i>Transactions of the American Mathematical Society</i>, vol. 372, no. 8, American Mathematical Society, 2019, pp. 5571–94, doi:<a href=\"https://doi.org/10.1090/tran/7729\">10.1090/tran/7729</a>.","ista":"Kwan MA, Sudakov B. 2019. Proof of a conjecture on induced subgraphs of Ramsey graphs. Transactions of the American Mathematical Society. 372(8), 5571–5594.","apa":"Kwan, M. A., &#38; Sudakov, B. (2019). Proof of a conjecture on induced subgraphs of Ramsey graphs. <i>Transactions of the American Mathematical Society</i>. American Mathematical Society. <a href=\"https://doi.org/10.1090/tran/7729\">https://doi.org/10.1090/tran/7729</a>","ieee":"M. A. Kwan and B. Sudakov, “Proof of a conjecture on induced subgraphs of Ramsey graphs,” <i>Transactions of the American Mathematical Society</i>, vol. 372, no. 8. American Mathematical Society, pp. 5571–5594, 2019.","chicago":"Kwan, Matthew Alan, and Benny Sudakov. “Proof of a Conjecture on Induced Subgraphs of Ramsey Graphs.” <i>Transactions of the American Mathematical Society</i>. American Mathematical Society, 2019. <a href=\"https://doi.org/10.1090/tran/7729\">https://doi.org/10.1090/tran/7729</a>.","short":"M.A. Kwan, B. Sudakov, Transactions of the American Mathematical Society 372 (2019) 5571–5594."},"status":"public","external_id":{"arxiv":["1712.05656"]},"volume":372,"date_created":"2021-06-22T09:31:45Z","page":"5571-5594","abstract":[{"lang":"eng","text":"An n-vertex graph is called C-Ramsey if it has no clique or independent set of size C log n. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. More than 25 years ago, Erdős, Faudree and Sós conjectured that in any C-Ramsey graph there are Ω(n^5/2) induced subgraphs, no pair of which have the same numbers of vertices and edges. Improving on earlier results of Alon, Balogh, Kostochka and Samotij, in this paper we prove this conjecture."}],"date_updated":"2023-02-23T14:01:50Z","type":"journal_article","oa_version":"Submitted Version","month":"10","_id":"9585","year":"2019"},{"intvolume":"        99","extern":"1","citation":{"short":"M.A. Kwan, B. Sudakov, T. Tran, Journal of the London Mathematical Society 99 (2019) 757–777.","ieee":"M. A. Kwan, B. Sudakov, and T. Tran, “Anticoncentration for subgraph statistics,” <i>Journal of the London Mathematical Society</i>, vol. 99, no. 3. Wiley, pp. 757–777, 2019.","chicago":"Kwan, Matthew Alan, Benny Sudakov, and Tuan Tran. “Anticoncentration for Subgraph Statistics.” <i>Journal of the London Mathematical Society</i>. Wiley, 2019. <a href=\"https://doi.org/10.1112/jlms.12192\">https://doi.org/10.1112/jlms.12192</a>.","mla":"Kwan, Matthew Alan, et al. “Anticoncentration for Subgraph Statistics.” <i>Journal of the London Mathematical Society</i>, vol. 99, no. 3, Wiley, 2019, pp. 757–77, doi:<a href=\"https://doi.org/10.1112/jlms.12192\">10.1112/jlms.12192</a>.","ista":"Kwan MA, Sudakov B, Tran T. 2019. Anticoncentration for subgraph statistics. Journal of the London Mathematical Society. 99(3), 757–777.","apa":"Kwan, M. A., Sudakov, B., &#38; Tran, T. (2019). Anticoncentration for subgraph statistics. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.12192\">https://doi.org/10.1112/jlms.12192</a>","ama":"Kwan MA, Sudakov B, Tran T. Anticoncentration for subgraph statistics. <i>Journal of the London Mathematical Society</i>. 2019;99(3):757-777. doi:<a href=\"https://doi.org/10.1112/jlms.12192\">10.1112/jlms.12192</a>"},"status":"public","external_id":{"arxiv":["1807.05202"]},"date_published":"2019-05-03T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1807.05202"}],"publication_status":"published","oa":1,"_id":"9586","year":"2019","volume":99,"date_created":"2021-06-22T09:46:03Z","page":"757-777","type":"journal_article","month":"05","oa_version":"Preprint","abstract":[{"text":"Consider integers  𝑘,ℓ  such that  0⩽ℓ⩽(𝑘2) . Given a large graph  𝐺 , what is the fraction of  𝑘 -vertex subsets of  𝐺  which span exactly  ℓ  edges? When  𝐺  is empty or complete, and  ℓ  is zero or  (𝑘2) , this fraction can be exactly 1. On the other hand, if  ℓ  is far from these extreme values, one might expect that this fraction is substantially smaller than 1. This was recently proved by Alon, Hefetz, Krivelevich, and Tyomkyn who initiated the systematic study of this question and proposed several natural conjectures.\r\nLet  ℓ∗=min{ℓ,(𝑘2)−ℓ} . Our main result is that for any  𝑘  and  ℓ , the fraction of  𝑘 -vertex subsets that span  ℓ  edges is at most  log𝑂(1)(ℓ∗/𝑘)√ 𝑘/ℓ∗, which is best-possible up to the logarithmic factor. This improves on multiple results of Alon, Hefetz, Krivelevich, and Tyomkyn, and resolves one of their conjectures. In addition, we also make some first steps towards some analogous questions for hypergraphs.\r\nOur proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anticoncentration inequalities, hypercontractivity, and a coupling trick for random variables defined on a ‘slice’ of the Boolean hypercube.","lang":"eng"}],"date_updated":"2023-02-23T14:01:53Z","issue":"3","language":[{"iso":"eng"}],"doi":"10.1112/jlms.12192","quality_controlled":"1","publication_identifier":{"eissn":["1469-7750"],"issn":["0024-6107"]},"publication":"Journal of the London Mathematical Society","article_type":"original","article_processing_charge":"No","scopus_import":"1","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Wiley","arxiv":1,"title":"Anticoncentration for subgraph statistics","author":[{"orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan"},{"full_name":"Sudakov, Benny","last_name":"Sudakov","first_name":"Benny"},{"last_name":"Tran","first_name":"Tuan","full_name":"Tran, Tuan"}],"day":"03"},{"publication":"Random Structures and Algorithms","article_processing_charge":"No","scopus_import":"1","article_type":"original","publisher":"Wiley","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","title":"Counting Hamilton cycles in sparse random directed graphs","arxiv":1,"author":[{"full_name":"Ferber, Asaf","last_name":"Ferber","first_name":"Asaf"},{"last_name":"Kwan","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567"},{"full_name":"Sudakov, Benny","last_name":"Sudakov","first_name":"Benny"}],"day":"01","language":[{"iso":"eng"}],"issue":"4","doi":"10.1002/rsa.20815","quality_controlled":"1","publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"_id":"9565","year":"2018","volume":53,"date_created":"2021-06-18T12:06:28Z","page":"592-603","date_updated":"2023-02-23T14:01:03Z","abstract":[{"text":"Let D(n,p) be the random directed graph on n vertices where each of the n(n-1) possible arcs is present independently with probability p. A celebrated result of Frieze shows that if p≥(logn+ω(1))/n then D(n,p) typically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles in D(n,p) is typically n!(p(1+o(1)))n. We also prove a hitting-time version of this statement, showing that in the random directed graph process, as soon as every vertex has in-/out-degrees at least 1, there are typically n!(logn/n(1+o(1)))n directed Hamilton cycles.","lang":"eng"}],"month":"12","oa_version":"Preprint","type":"journal_article","extern":"1","intvolume":"        53","citation":{"ama":"Ferber A, Kwan MA, Sudakov B. Counting Hamilton cycles in sparse random directed graphs. <i>Random Structures and Algorithms</i>. 2018;53(4):592-603. doi:<a href=\"https://doi.org/10.1002/rsa.20815\">10.1002/rsa.20815</a>","apa":"Ferber, A., Kwan, M. A., &#38; Sudakov, B. (2018). Counting Hamilton cycles in sparse random directed graphs. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.20815\">https://doi.org/10.1002/rsa.20815</a>","ista":"Ferber A, Kwan MA, Sudakov B. 2018. Counting Hamilton cycles in sparse random directed graphs. Random Structures and Algorithms. 53(4), 592–603.","mla":"Ferber, Asaf, et al. “Counting Hamilton Cycles in Sparse Random Directed Graphs.” <i>Random Structures and Algorithms</i>, vol. 53, no. 4, Wiley, 2018, pp. 592–603, doi:<a href=\"https://doi.org/10.1002/rsa.20815\">10.1002/rsa.20815</a>.","chicago":"Ferber, Asaf, Matthew Alan Kwan, and Benny Sudakov. “Counting Hamilton Cycles in Sparse Random Directed Graphs.” <i>Random Structures and Algorithms</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/rsa.20815\">https://doi.org/10.1002/rsa.20815</a>.","ieee":"A. Ferber, M. A. Kwan, and B. Sudakov, “Counting Hamilton cycles in sparse random directed graphs,” <i>Random Structures and Algorithms</i>, vol. 53, no. 4. Wiley, pp. 592–603, 2018.","short":"A. Ferber, M.A. Kwan, B. Sudakov, Random Structures and Algorithms 53 (2018) 592–603."},"status":"public","external_id":{"arxiv":["1708.07746"]},"date_published":"2018-12-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.07746"}],"oa":1,"publication_status":"published"},{"date_created":"2021-06-18T12:37:40Z","volume":53,"date_updated":"2023-02-23T14:01:07Z","abstract":[{"lang":"eng","text":"Let P be a graph property which is preserved by removal of edges, and consider the random graph process that starts with the empty n-vertex graph and then adds edges one-by-one, each chosen uniformly at random subject to the constraint that P is not violated. These types of random processes have been the subject of extensive research over the last 20 years, having striking applications in extremal combinatorics, and leading to the discovery of important probabilistic tools. In this paper we consider the k-matching-free process, where P is the property of not containing a matching of size k. We are able to analyse the behaviour of this process for a wide range of values of k; in particular we prove that if k=o(n) or if n−2k=o(n−−√/logn) then this process is likely to terminate in a k-matching-free graph with the maximum possible number of edges, as characterised by Erdős and Gallai. We also show that these bounds on k are essentially best possible, and we make a first step towards understanding the behaviour of the process in the intermediate regime."}],"type":"journal_article","month":"12","oa_version":"Preprint","page":"692-716","_id":"9567","year":"2018","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1708.01054"}],"date_published":"2018-12-01T00:00:00Z","publication_status":"published","oa":1,"citation":{"ista":"Krivelevich M, Kwan MA, Loh P, Sudakov B. 2018. The random k‐matching‐free process. Random Structures and Algorithms. 53(4), 692–716.","mla":"Krivelevich, Michael, et al. “The Random K‐matching‐free Process.” <i>Random Structures and Algorithms</i>, vol. 53, no. 4, Wiley, 2018, pp. 692–716, doi:<a href=\"https://doi.org/10.1002/rsa.20814\">10.1002/rsa.20814</a>.","apa":"Krivelevich, M., Kwan, M. A., Loh, P., &#38; Sudakov, B. (2018). The random k‐matching‐free process. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.20814\">https://doi.org/10.1002/rsa.20814</a>","ama":"Krivelevich M, Kwan MA, Loh P, Sudakov B. The random k‐matching‐free process. <i>Random Structures and Algorithms</i>. 2018;53(4):692-716. doi:<a href=\"https://doi.org/10.1002/rsa.20814\">10.1002/rsa.20814</a>","short":"M. Krivelevich, M.A. Kwan, P. Loh, B. Sudakov, Random Structures and Algorithms 53 (2018) 692–716.","ieee":"M. Krivelevich, M. A. Kwan, P. Loh, and B. Sudakov, “The random k‐matching‐free process,” <i>Random Structures and Algorithms</i>, vol. 53, no. 4. Wiley, pp. 692–716, 2018.","chicago":"Krivelevich, Michael, Matthew Alan Kwan, Po‐Shen Loh, and Benny Sudakov. “The Random K‐matching‐free Process.” <i>Random Structures and Algorithms</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/rsa.20814\">https://doi.org/10.1002/rsa.20814</a>."},"extern":"1","intvolume":"        53","status":"public","external_id":{"arxiv":["1708.01054"]},"title":"The random k‐matching‐free process","arxiv":1,"day":"01","author":[{"full_name":"Krivelevich, Michael","first_name":"Michael","last_name":"Krivelevich"},{"orcid":"0000-0002-4003-7567","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","last_name":"Kwan"},{"first_name":"Po‐Shen","last_name":"Loh","full_name":"Loh, Po‐Shen"},{"first_name":"Benny","last_name":"Sudakov","full_name":"Sudakov, Benny"}],"article_processing_charge":"No","scopus_import":"1","article_type":"original","publication":"Random Structures and Algorithms","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Wiley","quality_controlled":"1","doi":"10.1002/rsa.20814","publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"language":[{"iso":"eng"}],"issue":"4"},{"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","publisher":"Wiley","publication":"Random Structures and Algorithms","scopus_import":"1","article_processing_charge":"No","article_type":"original","author":[{"last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan"},{"full_name":"Sudakov, Benny","last_name":"Sudakov","first_name":"Benny"}],"day":"01","arxiv":1,"title":"Intercalates and discrepancy in random Latin squares","language":[{"iso":"eng"}],"issue":"2","publication_identifier":{"eissn":["1098-2418"],"issn":["1042-9832"]},"doi":"10.1002/rsa.20742","quality_controlled":"1","year":"2018","_id":"9568","page":"181-196","abstract":[{"text":"An intercalate in a Latin square is a 2×2 Latin subsquare. Let N be the number of intercalates in a uniformly random n×n Latin square. We prove that asymptotically almost surely N≥(1−o(1))n2/4, and that EN≤(1+o(1))n2/2 (therefore asymptotically almost surely N≤fn2 for any f→∞). This significantly improves the previous best lower and upper bounds. We also give an upper tail bound for the number of intercalates in two fixed rows of a random Latin square. In addition, we discuss a problem of Linial and Luria on low-discrepancy Latin squares.","lang":"eng"}],"date_updated":"2023-02-23T14:01:09Z","type":"journal_article","month":"03","oa_version":"Preprint","volume":52,"date_created":"2021-06-18T12:47:25Z","external_id":{"arxiv":["1607.04981"]},"status":"public","extern":"1","intvolume":"        52","citation":{"ama":"Kwan MA, Sudakov B. Intercalates and discrepancy in random Latin squares. <i>Random Structures and Algorithms</i>. 2018;52(2):181-196. doi:<a href=\"https://doi.org/10.1002/rsa.20742\">10.1002/rsa.20742</a>","apa":"Kwan, M. A., &#38; Sudakov, B. (2018). Intercalates and discrepancy in random Latin squares. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.20742\">https://doi.org/10.1002/rsa.20742</a>","mla":"Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random Latin Squares.” <i>Random Structures and Algorithms</i>, vol. 52, no. 2, Wiley, 2018, pp. 181–96, doi:<a href=\"https://doi.org/10.1002/rsa.20742\">10.1002/rsa.20742</a>.","ista":"Kwan MA, Sudakov B. 2018. Intercalates and discrepancy in random Latin squares. Random Structures and Algorithms. 52(2), 181–196.","chicago":"Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random Latin Squares.” <i>Random Structures and Algorithms</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/rsa.20742\">https://doi.org/10.1002/rsa.20742</a>.","ieee":"M. A. Kwan and B. Sudakov, “Intercalates and discrepancy in random Latin squares,” <i>Random Structures and Algorithms</i>, vol. 52, no. 2. Wiley, pp. 181–196, 2018.","short":"M.A. Kwan, B. Sudakov, Random Structures and Algorithms 52 (2018) 181–196."},"oa":1,"publication_status":"published","date_published":"2018-03-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1607.04981"}]}]