[{"OA_place":"publisher","article_type":"original","OA_type":"gold","title":"Color-avoiding percolation on the Erdős–Rényi random graph","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"has_accepted_license":"1","abstract":[{"lang":"eng","text":"We consider a recently introduced model of color-avoiding percolation (abbreviated CA-percolation) defined as follows. Every edge in a graph G is colored in some of k>=2 colors. Two vertices u and v in G are said to be CA-connected if u and v may be connected using any subset of k-1 colors. CA-connectivity defines an equivalence relation on the vertex set of G whose classes are called CA-components.\r\nWe study the component structure of a randomly colored Erdős–Rényi random graph of constant average degree. We distinguish three regimes for the size of the largest component: a supercritical regime, a so-called intermediate regime, and a subcritical regime, in which the largest CA-component has respectively linear, logarithmic, and bounded size. Interestingly, in the subcritical regime, the bound is deterministic and given by the number of colors."}],"publication_identifier":{"eissn":["2644-9463"]},"publication":"Annales Henri Lebesgue","date_created":"2025-06-22T22:02:07Z","file_date_updated":"2025-06-23T11:59:22Z","date_updated":"2025-06-23T12:01:36Z","type":"journal_article","DOAJ_listed":"1","corr_author":"1","month":"06","doi":"10.5802/ahl.228","day":"01","department":[{"_id":"MaKw"}],"publication_status":"published","arxiv":1,"quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"status":"public","citation":{"ieee":"L. Lichev and B. Schapira, “Color-avoiding percolation on the Erdős–Rényi random graph,” <i>Annales Henri Lebesgue</i>, vol. 8. École normale supérieure de Rennes, pp. 35–65, 2025.","ama":"Lichev L, Schapira B. Color-avoiding percolation on the Erdős–Rényi random graph. <i>Annales Henri Lebesgue</i>. 2025;8:35-65. doi:<a href=\"https://doi.org/10.5802/ahl.228\">10.5802/ahl.228</a>","apa":"Lichev, L., &#38; Schapira, B. (2025). Color-avoiding percolation on the Erdős–Rényi random graph. <i>Annales Henri Lebesgue</i>. École normale supérieure de Rennes. <a href=\"https://doi.org/10.5802/ahl.228\">https://doi.org/10.5802/ahl.228</a>","mla":"Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the Erdős–Rényi Random Graph.” <i>Annales Henri Lebesgue</i>, vol. 8, École normale supérieure de Rennes, 2025, pp. 35–65, doi:<a href=\"https://doi.org/10.5802/ahl.228\">10.5802/ahl.228</a>.","short":"L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65.","chicago":"Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the Erdős–Rényi Random Graph.” <i>Annales Henri Lebesgue</i>. École normale supérieure de Rennes, 2025. <a href=\"https://doi.org/10.5802/ahl.228\">https://doi.org/10.5802/ahl.228</a>.","ista":"Lichev L, Schapira B. 2025. Color-avoiding percolation on the Erdős–Rényi random graph. Annales Henri Lebesgue. 8, 35–65."},"file":[{"relation":"main_file","checksum":"cca22d171b7affa010d17f5e793b0045","content_type":"application/pdf","success":1,"access_level":"open_access","file_size":746588,"creator":"dernst","date_updated":"2025-06-23T11:59:22Z","file_name":"2025_AnnalesHenriLebesgue_Lichev.pdf","file_id":"19875","date_created":"2025-06-23T11:59:22Z"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"acknowledgement":"We thank Dieter Mitsche for enlightening discussions, Balázs Ráth for a number of comments\r\nand corrections on a first version of this paper, and an anonymous referee for several useful remarks.","scopus_import":"1","external_id":{"arxiv":["2211.16086 "]},"_id":"19859","author":[{"first_name":"Lyuben","full_name":"Lichev, Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","last_name":"Lichev"},{"first_name":"Bruno","last_name":"Schapira","full_name":"Schapira, Bruno"}],"intvolume":"         8","volume":8,"date_published":"2025-06-01T00:00:00Z","article_processing_charge":"Yes","page":"35-65","publisher":"École normale supérieure de Rennes","ddc":["510"],"year":"2025"},{"publication":"European Journal of Combinatorics","date_created":"2025-06-23T13:54:46Z","publication_identifier":{"issn":["0195-6698"]},"abstract":[{"lang":"eng","text":"We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and exactly the vertices incident with the outer face are precolored. We give a necessary topological condition for the precoloring to extend, and give a complete characterization when the outer face has length at most five and when all vertices of the outer face have odd degree and are colored using only three colors."}],"type":"journal_article","date_updated":"2025-09-30T13:42:59Z","file_date_updated":"2025-06-24T06:33:30Z","title":"Precoloring extension in planar near-Eulerian-triangulations","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_type":"hybrid","article_type":"original","OA_place":"publisher","oa":1,"has_accepted_license":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"file_id":"19887","date_created":"2025-06-24T06:33:30Z","file_name":"2025_EuropJournCombinatorics_Dvorak.pdf","date_updated":"2025-06-24T06:33:30Z","creator":"dernst","file_size":564203,"access_level":"open_access","success":1,"content_type":"application/pdf","checksum":"8b3585df45b25091fba9bee9854b7d01","relation":"main_file"}],"citation":{"mla":"Dvořák, Zdeněk, et al. “Precoloring Extension in Planar Near-Eulerian-Triangulations.” <i>European Journal of Combinatorics</i>, vol. 127, 104138, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">10.1016/j.ejc.2025.104138</a>.","chicago":"Dvořák, Zdeněk, Benjamin Moore, Michaela Seifrtová, and Robert Šámal. “Precoloring Extension in Planar Near-Eulerian-Triangulations.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">https://doi.org/10.1016/j.ejc.2025.104138</a>.","short":"Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics 127 (2025).","ista":"Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138.","ieee":"Z. Dvořák, B. Moore, M. Seifrtová, and R. Šámal, “Precoloring extension in planar near-Eulerian-triangulations,” <i>European Journal of Combinatorics</i>, vol. 127. Elsevier, 2025.","apa":"Dvořák, Z., Moore, B., Seifrtová, M., &#38; Šámal, R. (2025). Precoloring extension in planar near-Eulerian-triangulations. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">https://doi.org/10.1016/j.ejc.2025.104138</a>","ama":"Dvořák Z, Moore B, Seifrtová M, Šámal R. Precoloring extension in planar near-Eulerian-triangulations. <i>European Journal of Combinatorics</i>. 2025;127. doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104138\">10.1016/j.ejc.2025.104138</a>"},"status":"public","scopus_import":"1","acknowledgement":"Supported by project 22-17398S (Flows and cycles in graphs on surfaces) of Czech Science Foundation. An extended abstract appeared in Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’23)","department":[{"_id":"MaKw"}],"publication_status":"published","doi":"10.1016/j.ejc.2025.104138","day":"01","month":"06","corr_author":"1","quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"arxiv":1,"intvolume":"       127","volume":127,"external_id":{"isi":["001443061400001"],"arxiv":["2312.13061"]},"_id":"19879","isi":1,"author":[{"first_name":"Zdeněk","full_name":"Dvořák, Zdeněk","last_name":"Dvořák"},{"first_name":"Benjamin","full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore"},{"full_name":"Seifrtová, Michaela","last_name":"Seifrtová","first_name":"Michaela"},{"last_name":"Šámal","full_name":"Šámal, Robert","first_name":"Robert"}],"ddc":["510"],"publisher":"Elsevier","year":"2025","article_number":"104138","date_published":"2025-06-01T00:00:00Z","article_processing_charge":"Yes (via OA deal)"},{"article_processing_charge":"Yes (via OA deal)","page":"2098-2106","date_published":"2025-06-15T00:00:00Z","year":"2025","publisher":"Association for Computing Machinery","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"},{"_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9","name":"Combinatorial Optimisation Problems on Sparse Random Graphs","grant_number":"ESP3863424"}],"ddc":["000"],"author":[{"first_name":"Michael","last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan"},{"first_name":"Benjamin","last_name":"Moore","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin"}],"_id":"20007","external_id":{"arxiv":["2410.06095"]},"arxiv":1,"oa_version":"Published Version","quality_controlled":"1","language":[{"iso":"eng"}],"month":"06","corr_author":"1","doi":"10.1145/3717823.3718173","day":"15","ec_funded":1,"publication_status":"published","department":[{"_id":"MaKw"}],"scopus_import":"1","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.","status":"public","file":[{"date_updated":"2025-07-14T06:13:10Z","creator":"dernst","file_size":706445,"date_created":"2025-07-14T06:13:10Z","file_id":"20012","file_name":"2025_STOC_Anastos.pdf","content_type":"application/pdf","checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","relation":"main_file","access_level":"open_access","success":1}],"citation":{"ieee":"M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 2098–2106.","apa":"Anastos, M., Kwan, M. A., &#38; Moore, B. (2025). Smoothed analysis for graph isomorphism. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>","ama":"Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:2098-2106. doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>","mla":"Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 2098–106, doi:<a href=\"https://doi.org/10.1145/3717823.3718173\">10.1145/3717823.3718173</a>.","short":"M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 2098–2106.","chicago":"Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis for Graph Isomorphism.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 2098–2106. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718173\">https://doi.org/10.1145/3717823.3718173</a>.","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."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"conference":{"end_date":"2025-06-27","location":"Prague, Czechia","start_date":"2025-06-23","name":"STOC: Symposium on Theory of Computing"},"oa":1,"has_accepted_license":"1","OA_place":"publisher","OA_type":"hybrid","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Smoothed analysis for graph isomorphism","file_date_updated":"2025-07-14T06:13:10Z","date_updated":"2025-07-14T06:33:50Z","type":"conference","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."}],"publication_identifier":{"isbn":["9798400715105"],"issn":["0737-8017"]},"date_created":"2025-07-13T22:01:23Z","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing"},{"doi":"10.1016/j.ejc.2025.104214","day":"01","department":[{"_id":"MaKw"}],"publication_status":"published","corr_author":"1","month":"12","quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Published Version","arxiv":1,"file":[{"access_level":"open_access","success":1,"checksum":"b1536e9256c4510a0e21452032e43a26","relation":"main_file","content_type":"application/pdf","file_name":"2025_EuropJournCombinatorics_Mies.pdf","date_created":"2025-12-30T10:18:56Z","file_id":"20913","creator":"dernst","file_size":737845,"date_updated":"2025-12-30T10:18:56Z"}],"citation":{"ista":"Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.","chicago":"Mies, Sebastian, Benjamin Moore, and Evelyne Smith-Roberge. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">https://doi.org/10.1016/j.ejc.2025.104214</a>.","mla":"Mies, Sebastian, et al. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” <i>European Journal of Combinatorics</i>, vol. 130, no. 12, 104214, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">10.1016/j.ejc.2025.104214</a>.","short":"S. Mies, B. Moore, E. Smith-Roberge, European Journal of Combinatorics 130 (2025).","apa":"Mies, S., Moore, B., &#38; Smith-Roberge, E. (2025). Beyond the pseudoforest strong Nine Dragon Tree theorem. <i>European Journal of Combinatorics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">https://doi.org/10.1016/j.ejc.2025.104214</a>","ama":"Mies S, Moore B, Smith-Roberge E. Beyond the pseudoforest strong Nine Dragon Tree theorem. <i>European Journal of Combinatorics</i>. 2025;130(12). doi:<a href=\"https://doi.org/10.1016/j.ejc.2025.104214\">10.1016/j.ejc.2025.104214</a>","ieee":"S. Mies, B. Moore, and E. Smith-Roberge, “Beyond the pseudoforest strong Nine Dragon Tree theorem,” <i>European Journal of Combinatorics</i>, vol. 130, no. 12. Elsevier, 2025."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"status":"public","acknowledgement":"This work was completed while Benjamin Moore was a postdoc at Charles University, supported by project 22-17398S (Flows and cycles in graphs on surfaces) of Czech Science Foundation, Czechia.","scopus_import":"1","OA_type":"hybrid","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Beyond the pseudoforest strong Nine Dragon Tree theorem","OA_place":"publisher","article_type":"original","oa":1,"has_accepted_license":"1","publication_identifier":{"issn":["0195-6698"]},"date_created":"2025-09-10T05:36:50Z","publication":"European Journal of Combinatorics","abstract":[{"lang":"eng","text":"The pseudoforest version of the Strong Nine Dragon Tree Conjecture states that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most 2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in one pseudoforest F the components of F have at most d edges. This was proven in 2020 in Grout and Moore (2020). We strengthen this\r\ntheorem by showing that we can find such a decomposition where additionally F is acyclic, the diameter of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ + 1 if\r\nd ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N, we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter bounds are best possible as an\r\nextension for both the Strong Nine Dragon Tree Conjecture for pseudoforests and its original conjecture for forests. In fact, they are still optimal even if we only enforce F to have any constant maximum degree, instead of enforcing every component of F to have at most d edges."}],"date_updated":"2025-12-30T10:19:10Z","type":"journal_article","PlanS_conform":"1","file_date_updated":"2025-12-30T10:18:56Z","date_published":"2025-12-01T00:00:00Z","article_processing_charge":"Yes (via OA deal)","ddc":["500"],"publisher":"Elsevier","article_number":"104214","year":"2025","issue":"12","_id":"20320","external_id":{"isi":["001529769300002"],"arxiv":["2310.00931"]},"isi":1,"author":[{"first_name":"Sebastian","last_name":"Mies","full_name":"Mies, Sebastian"},{"last_name":"Moore","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin","first_name":"Benjamin"},{"first_name":"Evelyne","last_name":"Smith-Roberge","full_name":"Smith-Roberge, Evelyne"}],"intvolume":"       130","volume":130},{"intvolume":"      2025","volume":2025,"_id":"20504","issue":"18","external_id":{"arxiv":["2505.03954"],"isi":["001575137400001"]},"author":[{"full_name":"Jain, Vishesh","last_name":"Jain","first_name":"Vishesh"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan"},{"full_name":"Mubayi, Dhruv","last_name":"Mubayi","first_name":"Dhruv"},{"full_name":"Tran, Tuan","last_name":"Tran","first_name":"Tuan"}],"isi":1,"ddc":["510"],"project":[{"name":"Randomness and structure in combinatorics","grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"publisher":"Oxford University Press","year":"2025","article_number":"rnaf273","date_published":"2025-09-11T00:00:00Z","article_processing_charge":"Yes (via OA deal)","date_created":"2025-10-20T11:08:57Z","publication":"International Mathematics Research Notices","publication_identifier":{"eissn":["1687-0247"],"issn":["1073-7928"]},"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"}],"type":"journal_article","date_updated":"2025-12-01T13:00:35Z","file_date_updated":"2025-10-21T07:36:56Z","PlanS_conform":"1","title":"The edge-statistics conjecture for hypergraphs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"hybrid","article_type":"original","OA_place":"publisher","oa":1,"has_accepted_license":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"citation":{"apa":"Jain, V., Kwan, M. A., Mubayi, D., &#38; Tran, T. (2025). The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rnaf273\">https://doi.org/10.1093/imrn/rnaf273</a>","ama":"Jain V, Kwan MA, Mubayi D, Tran T. The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. 2025;2025(18). doi:<a href=\"https://doi.org/10.1093/imrn/rnaf273\">10.1093/imrn/rnaf273</a>","ieee":"V. Jain, M. A. Kwan, D. Mubayi, and T. Tran, “The edge-statistics conjecture for hypergraphs,” <i>International Mathematics Research Notices</i>, vol. 2025, no. 18. Oxford University Press, 2025.","ista":"Jain V, Kwan MA, Mubayi D, Tran T. 2025. The edge-statistics conjecture for hypergraphs. International Mathematics Research Notices. 2025(18), rnaf273.","chicago":"Jain, Vishesh, Matthew Alan Kwan, Dhruv Mubayi, and Tuan Tran. “The Edge-Statistics Conjecture for Hypergraphs.” <i>International Mathematics Research Notices</i>. Oxford University Press, 2025. <a href=\"https://doi.org/10.1093/imrn/rnaf273\">https://doi.org/10.1093/imrn/rnaf273</a>.","mla":"Jain, Vishesh, et al. “The Edge-Statistics Conjecture for Hypergraphs.” <i>International Mathematics Research Notices</i>, vol. 2025, no. 18, rnaf273, Oxford University Press, 2025, doi:<a href=\"https://doi.org/10.1093/imrn/rnaf273\">10.1093/imrn/rnaf273</a>.","short":"V. Jain, M.A. Kwan, D. Mubayi, T. Tran, International Mathematics Research Notices 2025 (2025)."},"file":[{"file_size":774323,"creator":"dernst","date_updated":"2025-10-21T07:36:56Z","file_name":"2025_IMRN_Jain.pdf","date_created":"2025-10-21T07:36:56Z","file_id":"20511","relation":"main_file","checksum":"016aa4df9453dc180ae7504ac77bf72f","content_type":"application/pdf","success":1,"access_level":"open_access"}],"status":"public","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).","scopus_import":"1","publication_status":"published","department":[{"_id":"MaKw"}],"doi":"10.1093/imrn/rnaf273","day":"11","corr_author":"1","month":"09","language":[{"iso":"eng"}],"quality_controlled":"1","oa_version":"Published Version","arxiv":1},{"year":"2025","ddc":["510"],"publisher":"Springer Nature","page":"52-65","article_processing_charge":"Yes (via OA deal)","date_published":"2025-03-01T00:00:00Z","volume":47,"intvolume":"        47","isi":1,"author":[{"first_name":"Florestan R","full_name":"Brunck, Florestan R","id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","last_name":"Brunck"},{"first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan"}],"_id":"18157","external_id":{"arxiv":["2303.09459"],"isi":["001318056000001"]},"scopus_import":"1","acknowledgement":"Open access funding provided by Copenhagen University.","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"citation":{"mla":"Brunck, Florestan R., and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” <i>Mathematical Intelligencer</i>, vol. 47, Springer Nature, 2025, pp. 52–65, doi:<a href=\"https://doi.org/10.1007/s00283-024-10358-x\">10.1007/s00283-024-10358-x</a>.","chicago":"Brunck, Florestan R, and Matthew Alan Kwan. “Books, Hallways, and Social Butterflies: A Note on Sliding Block Puzzles.” <i>Mathematical Intelligencer</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s00283-024-10358-x\">https://doi.org/10.1007/s00283-024-10358-x</a>.","short":"F.R. Brunck, M.A. Kwan, Mathematical Intelligencer 47 (2025) 52–65.","ista":"Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. 47, 52–65.","ieee":"F. R. Brunck and M. A. Kwan, “Books, Hallways, and social butterflies: A note on sliding block puzzles,” <i>Mathematical Intelligencer</i>, vol. 47. Springer Nature, pp. 52–65, 2025.","ama":"Brunck FR, Kwan MA. Books, Hallways, and social butterflies: A note on sliding block puzzles. <i>Mathematical Intelligencer</i>. 2025;47:52-65. doi:<a href=\"https://doi.org/10.1007/s00283-024-10358-x\">10.1007/s00283-024-10358-x</a>","apa":"Brunck, F. R., &#38; Kwan, M. A. (2025). Books, Hallways, and social butterflies: A note on sliding block puzzles. <i>Mathematical Intelligencer</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00283-024-10358-x\">https://doi.org/10.1007/s00283-024-10358-x</a>"},"file":[{"relation":"main_file","checksum":"c932ebe45c460d4a73f5b2dcca643db1","content_type":"application/pdf","success":1,"access_level":"open_access","file_size":1760643,"creator":"dernst","date_updated":"2025-04-08T11:17:45Z","file_name":"2025_MathIntelligencer_Brunck.pdf","file_id":"19530","date_created":"2025-04-08T11:17:45Z"}],"status":"public","oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"publication_status":"published","department":[{"_id":"UlWa"},{"_id":"MaKw"}],"day":"01","doi":"10.1007/s00283-024-10358-x","month":"03","type":"journal_article","date_updated":"2025-05-19T14:00:09Z","file_date_updated":"2025-04-08T11:17:45Z","date_created":"2024-09-29T22:01:38Z","publication":"Mathematical Intelligencer","publication_identifier":{"issn":["0343-6993"]},"abstract":[{"lang":"eng","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."}],"has_accepted_license":"1","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Books, Hallways, and social butterflies: A note on sliding block puzzles","OA_type":"hybrid","article_type":"original","OA_place":"publisher"},{"author":[{"first_name":"Rutger","last_name":"Campbell","full_name":"Campbell, Rutger"},{"full_name":"Hörsch, Florian","last_name":"Hörsch","first_name":"Florian"},{"full_name":"Moore, Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","last_name":"Moore","first_name":"Benjamin"}],"isi":1,"_id":"15163","issue":"6","external_id":{"isi":["001226893800001"],"arxiv":["2301.11615"]},"volume":347,"intvolume":"       347","article_processing_charge":"No","date_published":"2024-06-01T00:00:00Z","article_number":"113962","year":"2024","publisher":"Elsevier","oa":1,"article_type":"original","title":"Decompositions into two linear forests of bounded lengths","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-04T13:10:26Z","type":"journal_article","abstract":[{"lang":"eng","text":"For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs."}],"publication_identifier":{"issn":["0012-365X"]},"publication":"Discrete Mathematics","date_created":"2024-03-24T23:00:58Z","arxiv":1,"quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Preprint","month":"06","corr_author":"1","day":"01","doi":"10.1016/j.disc.2024.113962","publication_status":"published","department":[{"_id":"MaKw"}],"scopus_import":"1","acknowledgement":"We wish to thank Dániel Marx and András Sebő for making us aware of the results in [8] and some clarifications on them.","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2301.11615"}],"citation":{"ama":"Campbell R, Hörsch F, Moore B. Decompositions into two linear forests of bounded lengths. <i>Discrete Mathematics</i>. 2024;347(6). doi:<a href=\"https://doi.org/10.1016/j.disc.2024.113962\">10.1016/j.disc.2024.113962</a>","apa":"Campbell, R., Hörsch, F., &#38; Moore, B. (2024). Decompositions into two linear forests of bounded lengths. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2024.113962\">https://doi.org/10.1016/j.disc.2024.113962</a>","ieee":"R. Campbell, F. Hörsch, and B. Moore, “Decompositions into two linear forests of bounded lengths,” <i>Discrete Mathematics</i>, vol. 347, no. 6. Elsevier, 2024.","ista":"Campbell R, Hörsch F, Moore B. 2024. Decompositions into two linear forests of bounded lengths. Discrete Mathematics. 347(6), 113962.","chicago":"Campbell, Rutger, Florian Hörsch, and Benjamin Moore. “Decompositions into Two Linear Forests of Bounded Lengths.” <i>Discrete Mathematics</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.disc.2024.113962\">https://doi.org/10.1016/j.disc.2024.113962</a>.","mla":"Campbell, Rutger, et al. “Decompositions into Two Linear Forests of Bounded Lengths.” <i>Discrete Mathematics</i>, vol. 347, no. 6, 113962, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.disc.2024.113962\">10.1016/j.disc.2024.113962</a>.","short":"R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024)."}},{"page":"1059-1156","article_processing_charge":"No","date_published":"2024-11-01T00:00:00Z","year":"2024","publisher":"Princeton University","isi":1,"author":[{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan"},{"last_name":"Sah","full_name":"Sah, Ashwin","first_name":"Ashwin"},{"full_name":"Sawhney, Mehtaab","last_name":"Sawhney","first_name":"Mehtaab"},{"full_name":"Simkin, Michael","last_name":"Simkin","first_name":"Michael"}],"_id":"18559","issue":"3","external_id":{"isi":["001366233800004"],"arxiv":["2201.04554"]},"volume":200,"intvolume":"       200","quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"arxiv":1,"publication_status":"published","department":[{"_id":"MaKw"}],"doi":"10.4007/annals.2024.200.3.4","day":"01","corr_author":"1","month":"11","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.","scopus_import":"1","citation":{"ieee":"M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “High-girth Steiner triple systems,” <i>Annals of Mathematics</i>, vol. 200, no. 3. Princeton University, pp. 1059–1156, 2024.","ama":"Kwan MA, Sah A, Sawhney M, Simkin M. High-girth Steiner triple systems. <i>Annals of Mathematics</i>. 2024;200(3):1059-1156. doi:<a href=\"https://doi.org/10.4007/annals.2024.200.3.4\">10.4007/annals.2024.200.3.4</a>","apa":"Kwan, M. A., Sah, A., Sawhney, M., &#38; Simkin, M. (2024). High-girth Steiner triple systems. <i>Annals of Mathematics</i>. Princeton University. <a href=\"https://doi.org/10.4007/annals.2024.200.3.4\">https://doi.org/10.4007/annals.2024.200.3.4</a>","mla":"Kwan, Matthew Alan, et al. “High-Girth Steiner Triple Systems.” <i>Annals of Mathematics</i>, vol. 200, no. 3, Princeton University, 2024, pp. 1059–156, doi:<a href=\"https://doi.org/10.4007/annals.2024.200.3.4\">10.4007/annals.2024.200.3.4</a>.","short":"M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Annals of Mathematics 200 (2024) 1059–1156.","chicago":"Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “High-Girth Steiner Triple Systems.” <i>Annals of Mathematics</i>. Princeton University, 2024. <a href=\"https://doi.org/10.4007/annals.2024.200.3.4\">https://doi.org/10.4007/annals.2024.200.3.4</a>.","ista":"Kwan MA, Sah A, Sawhney M, Simkin M. 2024. High-girth Steiner triple systems. Annals of Mathematics. 200(3), 1059–1156."},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2201.04554","open_access":"1"}],"status":"public","oa":1,"title":"High-girth Steiner triple systems","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_type":"green","article_type":"original","OA_place":"repository","type":"journal_article","date_updated":"2025-09-08T14:40:55Z","publication":"Annals of Mathematics","date_created":"2024-11-17T23:01:48Z","publication_identifier":{"eissn":["1939-8980"],"issn":["0003-486X"]},"abstract":[{"lang":"eng","text":"We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth."}]},{"OA_place":"publisher","article_type":"original","OA_type":"hybrid","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Partitioning problems via random processes","has_accepted_license":"1","oa":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"}],"publication_identifier":{"issn":["0024-6107"],"eissn":["1469-7750"]},"publication":"Journal of the London Mathematical Society","date_created":"2024-11-24T23:01:48Z","file_date_updated":"2024-12-10T08:10:39Z","date_updated":"2025-12-02T13:52:26Z","type":"journal_article","corr_author":"1","month":"12","day":"01","ec_funded":1,"doi":"10.1112/jlms.70010","department":[{"_id":"MaKw"}],"publication_status":"published","arxiv":1,"language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","status":"public","citation":{"apa":"Anastos, M., Cooley, O., Kang, M., &#38; Kwan, M. A. (2024). Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70010\">https://doi.org/10.1112/jlms.70010</a>","ama":"Anastos M, Cooley O, Kang M, Kwan MA. Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. 2024;110(6). doi:<a href=\"https://doi.org/10.1112/jlms.70010\">10.1112/jlms.70010</a>","ieee":"M. Anastos, O. Cooley, M. Kang, and M. A. Kwan, “Partitioning problems via random processes,” <i>Journal of the London Mathematical Society</i>, vol. 110, no. 6. Wiley, 2024.","ista":"Anastos M, Cooley O, Kang M, Kwan MA. 2024. Partitioning problems via random processes. Journal of the London Mathematical Society. 110(6), e70010.","mla":"Anastos, Michael, et al. “Partitioning Problems via Random Processes.” <i>Journal of the London Mathematical Society</i>, vol. 110, no. 6, e70010, Wiley, 2024, doi:<a href=\"https://doi.org/10.1112/jlms.70010\">10.1112/jlms.70010</a>.","short":"M. Anastos, O. Cooley, M. Kang, M.A. Kwan, Journal of the London Mathematical Society 110 (2024).","chicago":"Anastos, Michael, Oliver Cooley, Mihyun Kang, and Matthew Alan Kwan. “Partitioning Problems via Random Processes.” <i>Journal of the London Mathematical Society</i>. Wiley, 2024. <a href=\"https://doi.org/10.1112/jlms.70010\">https://doi.org/10.1112/jlms.70010</a>."},"file":[{"creator":"dernst","file_size":539891,"date_updated":"2024-12-10T08:10:39Z","file_name":"2024_JournLondonMathSoc_Anastos.pdf","date_created":"2024-12-10T08:10:39Z","file_id":"18639","checksum":"98e301e0565d75e3fb50e10e982a5018","relation":"main_file","content_type":"application/pdf","access_level":"open_access","success":1}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"scopus_import":"1","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.","external_id":{"arxiv":["2307.06453"],"isi":["001374738100001"]},"_id":"18583","issue":"6","author":[{"last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","first_name":"Michael"},{"first_name":"Oliver","id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","full_name":"Cooley, Oliver","last_name":"Cooley"},{"last_name":"Kang","full_name":"Kang, Mihyun","first_name":"Mihyun"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"}],"isi":1,"intvolume":"       110","volume":110,"date_published":"2024-12-01T00:00:00Z","article_processing_charge":"Yes (via OA deal)","publisher":"Wiley","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413"},{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics","grant_number":"101076777"}],"ddc":["510"],"article_number":"e70010","year":"2024"},{"_id":"18655","external_id":{"arxiv":["2311.16631"],"isi":["001356019700001"]},"author":[{"first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","full_name":"Anastos, Michael","last_name":"Anastos"},{"first_name":"Sahar","last_name":"Diskin","full_name":"Diskin, Sahar"},{"full_name":"Elboim, Dor","last_name":"Elboim","first_name":"Dor"},{"full_name":"Krivelevich, Michael","last_name":"Krivelevich","first_name":"Michael"}],"isi":1,"intvolume":"        29","volume":29,"date_published":"2024-11-24T00:00:00Z","article_processing_charge":"Yes","ddc":["510"],"publisher":"Duke University Press","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"article_number":"70","year":"2024","OA_type":"gold","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Climbing up a random subgraph of the hypercube","OA_place":"repository","article_type":"original","oa":1,"has_accepted_license":"1","publication_identifier":{"eissn":["1083-589X"]},"date_created":"2024-12-15T23:01:51Z","publication":"Electronic Communications in Probability","abstract":[{"lang":"eng","text":"Let Qd be the d-dimensional binary hypercube. We say that P={v1,…,vk} is an increasing path of length k−1 in Qd, if for every i∈[k−1] the edge vivi+1 is obtained by switching some zero coordinate in vi to a one coordinate in vi+1.\r\nForm a random subgraph Qdp by retaining each edge in E(Qd) independently with probability p. We show that there is a phase transition with respect to the length of a longest increasing path around p=ed. Let α be a constant and let p=αd. When α<e, then there exists a δ∈[0,1) such that whp a longest increasing path in Qdp is of length at most δd. On the other hand, when α>e, whp there is a path of length d−2 in Qdp, and in fact, whether it is of length d−2,d−1, or d depends on whether the all-zero and all-one vertices percolate or not."}],"date_updated":"2025-09-09T11:46:53Z","type":"journal_article","DOAJ_listed":"1","file_date_updated":"2024-12-16T07:33:34Z","ec_funded":1,"day":"24","doi":"10.1214/24-ECP639","publication_status":"published","department":[{"_id":"MaKw"}],"month":"11","corr_author":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"citation":{"ieee":"M. Anastos, S. Diskin, D. Elboim, and M. Krivelevich, “Climbing up a random subgraph of the hypercube,” <i>Electronic Communications in Probability</i>, vol. 29. Duke University Press, 2024.","ama":"Anastos M, Diskin S, Elboim D, Krivelevich M. Climbing up a random subgraph of the hypercube. <i>Electronic Communications in Probability</i>. 2024;29. doi:<a href=\"https://doi.org/10.1214/24-ECP639\">10.1214/24-ECP639</a>","apa":"Anastos, M., Diskin, S., Elboim, D., &#38; Krivelevich, M. (2024). Climbing up a random subgraph of the hypercube. <i>Electronic Communications in Probability</i>. Duke University Press. <a href=\"https://doi.org/10.1214/24-ECP639\">https://doi.org/10.1214/24-ECP639</a>","mla":"Anastos, Michael, et al. “Climbing up a Random Subgraph of the Hypercube.” <i>Electronic Communications in Probability</i>, vol. 29, 70, Duke University Press, 2024, doi:<a href=\"https://doi.org/10.1214/24-ECP639\">10.1214/24-ECP639</a>.","chicago":"Anastos, Michael, Sahar Diskin, Dor Elboim, and Michael Krivelevich. “Climbing up a Random Subgraph of the Hypercube.” <i>Electronic Communications in Probability</i>. Duke University Press, 2024. <a href=\"https://doi.org/10.1214/24-ECP639\">https://doi.org/10.1214/24-ECP639</a>.","short":"M. Anastos, S. Diskin, D. Elboim, M. Krivelevich, Electronic Communications in Probability 29 (2024).","ista":"Anastos M, Diskin S, Elboim D, Krivelevich M. 2024. Climbing up a random subgraph of the hypercube. Electronic Communications in Probability. 29, 70."},"file":[{"date_created":"2024-12-16T07:33:34Z","file_id":"18657","file_name":"2024_ElectrCommProbability_Anastos.pdf","date_updated":"2024-12-16T07:33:34Z","creator":"dernst","file_size":530169,"access_level":"open_access","success":1,"content_type":"application/pdf","checksum":"307a9d049325e6ca9bfe8b4a1f275983","relation":"main_file"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2311.16631","open_access":"1"}],"status":"public","scopus_import":"1","acknowledgement":"Research supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.\r\nThe authors wish to thank Ross Pinsky for his comments on an earlier version of the paper, and for bringing reference [12] to our attention. The authors are grateful to the anonymous referees for their helpful comments and suggestions."},{"external_id":{"isi":["001545628900014"]},"_id":"18702","alternative_title":["LNCS"],"author":[{"first_name":"Michael","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos"},{"orcid":"0000-0002-7553-6606","first_name":"Benedikt","full_name":"Auerbach, Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach"},{"first_name":"Mirza Ahad","last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","full_name":"Baig, Mirza Ahad"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval","first_name":"Miguel","orcid":"0000-0002-2505-4246"},{"last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","first_name":"Guillermo","orcid":"0000-0001-8630-415X"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"}],"isi":1,"intvolume":"     15364","volume":15364,"date_published":"2024-12-02T00:00:00Z","page":"413-443","article_processing_charge":"No","publisher":"Springer Nature","year":"2024","OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging","OA_place":"repository","oa":1,"conference":{"end_date":"2024-12-06","location":"Milan, Italy","start_date":"2024-12-02","name":"TCC: Theory of Cryptography"},"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031780103"],"issn":["0302-9743"]},"publication":"22nd International Conference on Theory of Cryptography","date_created":"2024-12-22T23:01:47Z","abstract":[{"lang":"eng","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. "}],"date_updated":"2025-12-02T13:55:46Z","type":"conference","doi":"10.1007/978-3-031-78011-0_14","day":"02","department":[{"_id":"MaKw"},{"_id":"KrPi"}],"publication_status":"published","corr_author":"1","month":"12","quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Preprint","citation":{"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: <i>22nd International Conference on Theory of Cryptography</i>. Vol 15364. Springer Nature; 2024:413-443. doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>","apa":"Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual Perez, G., &#38; Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In <i>22nd International Conference on Theory of Cryptography</i> (Vol. 15364, pp. 413–443). Milan, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>","ieee":"M. Anastos <i>et al.</i>, “The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging,” in <i>22nd International Conference on Theory of Cryptography</i>, 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.” <i>22nd International Conference on Theory of Cryptography</i>, vol. 15364, Springer Nature, 2024, pp. 413–43, doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>.","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 <i>22nd International Conference on Theory of Cryptography</i>, 15364:413–43. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>.","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."},"status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2024/1097","open_access":"1"}],"scopus_import":"1"},{"intvolume":"       321","volume":321,"_id":"18758","external_id":{"arxiv":["2407.01071"],"isi":["001534851900002"]},"alternative_title":["LIPIcs"],"author":[{"first_name":"Jonas","last_name":"Lill","full_name":"Lill, Jonas"},{"first_name":"Kalina H","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","full_name":"Petrova, Kalina H","last_name":"Petrova"},{"first_name":"Simon","full_name":"Weber, Simon","last_name":"Weber"}],"isi":1,"ddc":["500"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413"}],"article_number":"2","year":"2024","date_published":"2024-12-05T00:00:00Z","article_processing_charge":"Yes","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773539"]},"date_created":"2025-01-05T23:01:57Z","publication":"19th International Symposium on Parameterized and Exact Computation","abstract":[{"lang":"eng","text":"MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f(k)⋅ O(m+n)."}],"date_updated":"2026-01-05T13:46:07Z","type":"conference","file_date_updated":"2025-01-08T09:14:59Z","OA_type":"gold","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound","OA_place":"publisher","oa":1,"has_accepted_license":"1","conference":{"end_date":"2024-09-06","location":"Egham, United Kingdom","start_date":"2024-09-04","name":"IPEC: Symposium on Parameterized and Exact Computation"},"file":[{"date_updated":"2025-01-08T09:14:59Z","creator":"dernst","file_size":927326,"file_id":"18775","date_created":"2025-01-08T09:14:59Z","file_name":"2024_LIPIcs_Lill.pdf","content_type":"application/pdf","checksum":"a64b9a0e41f7b867d25cb155825ccd53","relation":"main_file","access_level":"open_access","success":1}],"citation":{"mla":"Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>19th International Symposium on Parameterized and Exact Computation</i>, vol. 321, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">10.4230/LIPIcs.IPEC.2024.2</a>.","short":"J. Lill, K.H. Petrova, S. Weber, in:, 19th International Symposium on Parameterized and Exact Computation, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” In <i>19th International Symposium on Parameterized and Exact Computation</i>, Vol. 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">https://doi.org/10.4230/LIPIcs.IPEC.2024.2</a>.","ista":"Lill J, Petrova KH, Weber S. 2024. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. 19th International Symposium on Parameterized and Exact Computation. IPEC: Symposium on Parameterized and Exact Computation, LIPIcs, vol. 321, 2.","ieee":"J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound,” in <i>19th International Symposium on Parameterized and Exact Computation</i>, Egham, United Kingdom, 2024, vol. 321.","ama":"Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In: <i>19th International Symposium on Parameterized and Exact Computation</i>. Vol 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">10.4230/LIPIcs.IPEC.2024.2</a>","apa":"Lill, J., Petrova, K. H., &#38; Weber, S. (2024). Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In <i>19th International Symposium on Parameterized and Exact Computation</i> (Vol. 321). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">https://doi.org/10.4230/LIPIcs.IPEC.2024.2</a>"},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"status":"public","scopus_import":"1","acknowledgement":"Kalina Petrova: Swiss National Science Foundation, grant no. CRSII5 173721. This project\r\nhas received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.\r\nSimon Weber: Swiss National Science Foundation under project no. 204320","ec_funded":1,"day":"05","doi":"10.4230/LIPIcs.IPEC.2024.2","department":[{"_id":"MaKw"}],"publication_status":"published","corr_author":"1","month":"12","related_material":{"record":[{"status":"public","id":"19603","relation":"later_version"}]},"oa_version":"Published Version","quality_controlled":"1","language":[{"iso":"eng"}],"arxiv":1},{"external_id":{"arxiv":["2304.10930"]},"_id":"18951","author":[{"last_name":"Hartarsky","full_name":"Hartarsky, Ivailo","first_name":"Ivailo"},{"last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","full_name":"Lichev, Lyuben","first_name":"Lyuben"},{"last_name":"Toninelli","full_name":"Toninelli, Fabio Lucio","first_name":"Fabio Lucio"}],"date_published":"2024-08-26T00:00:00Z","article_processing_charge":"Yes","publisher":"EMS Press","year":"2024","article_type":"original","OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Local dimer dynamics in higher dimensions","OA_type":"gold","oa":1,"abstract":[{"lang":"eng","text":"We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes [n] \r\nd . These consist of successively switching the dimers along alternating cycles of prescribed (small) lengths. We study the connectivity properties of the dimer configuration space equipped with these transitions. Answering a question of Freire, Klivans, Milet, and Saldanha, we show that in three dimensions any configuration admits an alternating cycle of length at most 6. We further establish that any configuration on [n] d  features order n d−2  alternating cycles of length at most 4d−2. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension d is ergodic when switching alternating cycles of length at most 4d−4. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped boxes in the triangular lattice are ergodic for switching alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon and Rémila, which also uses 8-cycles. None of our proofs make reference to height functions."}],"date_created":"2025-01-29T10:57:09Z","publication":"Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions","publication_identifier":{"eissn":["2308-5835"],"issn":["2308-5827"]},"DOAJ_listed":"1","type":"journal_article","date_updated":"2025-07-08T08:39:55Z","month":"08","publication_status":"epub_ahead","department":[{"_id":"MaKw"}],"doi":"10.4171/aihpd/200","day":"26","arxiv":1,"language":[{"iso":"eng"}],"quality_controlled":"1","oa_version":"Preprint","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2304.10930","open_access":"1"}],"status":"public","citation":{"chicago":"Hartarsky, Ivailo, Lyuben Lichev, and Fabio Lucio Toninelli. “Local Dimer Dynamics in Higher Dimensions.” <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions</i>. EMS Press, 2024. <a href=\"https://doi.org/10.4171/aihpd/200\">https://doi.org/10.4171/aihpd/200</a>.","short":"I. Hartarsky, L. Lichev, F.L. Toninelli, Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions (2024).","mla":"Hartarsky, Ivailo, et al. “Local Dimer Dynamics in Higher Dimensions.” <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions</i>, EMS Press, 2024, doi:<a href=\"https://doi.org/10.4171/aihpd/200\">10.4171/aihpd/200</a>.","ista":"Hartarsky I, Lichev L, Toninelli FL. 2024. Local dimer dynamics in higher dimensions. Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions.","ieee":"I. Hartarsky, L. Lichev, and F. L. Toninelli, “Local dimer dynamics in higher dimensions,” <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions</i>. EMS Press, 2024.","apa":"Hartarsky, I., Lichev, L., &#38; Toninelli, F. L. (2024). Local dimer dynamics in higher dimensions. <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions</i>. EMS Press. <a href=\"https://doi.org/10.4171/aihpd/200\">https://doi.org/10.4171/aihpd/200</a>","ama":"Hartarsky I, Lichev L, Toninelli FL. Local dimer dynamics in higher dimensions. <i>Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions</i>. 2024. doi:<a href=\"https://doi.org/10.4171/aihpd/200\">10.4171/aihpd/200</a>"},"scopus_import":"1"},{"has_accepted_license":"1","oa":1,"title":"The inertia bound is far from tight","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_type":"hybrid","article_type":"original","OA_place":"publisher","type":"journal_article","date_updated":"2025-09-08T08:45:39Z","file_date_updated":"2025-01-09T13:36:53Z","publication":"Bulletin of the London Mathematical Society","date_created":"2024-08-04T22:01:22Z","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"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."}],"oa_version":"Published Version","quality_controlled":"1","language":[{"iso":"eng"}],"arxiv":1,"department":[{"_id":"MaKw"}],"publication_status":"published","doi":"10.1112/blms.13127","day":"01","month":"10","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.","scopus_import":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"access_level":"open_access","success":1,"checksum":"7117f9819eaeb45eef1b0a226f9c2709","relation":"main_file","content_type":"application/pdf","file_name":"2024_BulletinLondonMathSoc_Kwan.pdf","file_id":"18814","date_created":"2025-01-09T13:36:53Z","creator":"dernst","file_size":175966,"date_updated":"2025-01-09T13:36:53Z"}],"citation":{"ieee":"M. A. Kwan and Y. Wigderson, “The inertia bound is far from tight,” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10. London Mathematical Society, pp. 3196–3208, 2024.","ama":"Kwan MA, Wigderson Y. The inertia bound is far from tight. <i>Bulletin of the London Mathematical Society</i>. 2024;56(10):3196-3208. doi:<a href=\"https://doi.org/10.1112/blms.13127\">10.1112/blms.13127</a>","apa":"Kwan, M. A., &#38; Wigderson, Y. (2024). The inertia bound is far from tight. <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society. <a href=\"https://doi.org/10.1112/blms.13127\">https://doi.org/10.1112/blms.13127</a>","chicago":"Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society, 2024. <a href=\"https://doi.org/10.1112/blms.13127\">https://doi.org/10.1112/blms.13127</a>.","mla":"Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10, London Mathematical Society, 2024, pp. 3196–208, doi:<a href=\"https://doi.org/10.1112/blms.13127\">10.1112/blms.13127</a>.","short":"M.A. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024) 3196–3208.","ista":"Kwan MA, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 56(10), 3196–3208."},"status":"public","isi":1,"author":[{"last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan"},{"first_name":"Yuval","last_name":"Wigderson","full_name":"Wigderson, Yuval"}],"external_id":{"arxiv":["2312.04925"],"isi":["001279563300001"]},"_id":"17376","issue":"10","volume":56,"intvolume":"        56","page":"3196-3208","article_processing_charge":"Yes (via OA deal)","date_published":"2024-10-01T00:00:00Z","year":"2024","ddc":["510"],"project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","name":"Randomness and structure in combinatorics","grant_number":"101076777"}],"publisher":"London Mathematical Society"},{"oa":1,"has_accepted_license":"1","title":"Exponentially many graphs are determined by their spectrum","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_type":"original","date_updated":"2025-09-08T09:09:41Z","type":"journal_article","file_date_updated":"2024-09-06T12:23:57Z","publication_identifier":{"issn":["0033-5606"],"eissn":["1464-3847"]},"date_created":"2024-09-01T22:01:07Z","publication":"Quarterly Journal of Mathematics","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"}],"language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","arxiv":1,"doi":"10.1093/qmath/haae030","day":"19","publication_status":"published","department":[{"_id":"MaKw"},{"_id":"VaKa"}],"corr_author":"1","month":"06","acknowledgement":"Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777.","scopus_import":"1","file":[{"file_name":"2024_QuJofMath_Koval.pdf","date_created":"2024-09-06T12:23:57Z","file_id":"17851","creator":"cchlebak","file_size":946411,"date_updated":"2024-09-06T12:23:57Z","access_level":"open_access","success":1,"checksum":"abf200d37ad69e6f2c0750a30296ad97","relation":"main_file","content_type":"application/pdf"}],"citation":{"ieee":"I. Koval and M. A. Kwan, “Exponentially many graphs are determined by their spectrum,” <i>Quarterly Journal of Mathematics</i>, vol. 75, no. 3. Oxford University Press, pp. 869–899, 2024.","ama":"Koval I, Kwan MA. Exponentially many graphs are determined by their spectrum. <i>Quarterly Journal of Mathematics</i>. 2024;75(3):869-899. doi:<a href=\"https://doi.org/10.1093/qmath/haae030\">10.1093/qmath/haae030</a>","apa":"Koval, I., &#38; Kwan, M. A. (2024). Exponentially many graphs are determined by their spectrum. <i>Quarterly Journal of Mathematics</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/qmath/haae030\">https://doi.org/10.1093/qmath/haae030</a>","chicago":"Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” <i>Quarterly Journal of Mathematics</i>. Oxford University Press, 2024. <a href=\"https://doi.org/10.1093/qmath/haae030\">https://doi.org/10.1093/qmath/haae030</a>.","mla":"Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined by Their Spectrum.” <i>Quarterly Journal of Mathematics</i>, vol. 75, no. 3, Oxford University Press, 2024, pp. 869–99, doi:<a href=\"https://doi.org/10.1093/qmath/haae030\">10.1093/qmath/haae030</a>.","short":"I. Koval, M.A. Kwan, Quarterly Journal of Mathematics 75 (2024) 869–899.","ista":"Koval I, Kwan MA. 2024. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 75(3), 869–899."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"status":"public","isi":1,"author":[{"first_name":"Illya","full_name":"Koval, Illya","id":"2eed1f3b-896a-11ed-bdf8-93c7c4bf159e","last_name":"Koval"},{"orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"}],"_id":"17475","external_id":{"arxiv":["2309.09788"],"isi":["001249741500001"]},"issue":"3","volume":75,"intvolume":"        75","page":"869-899","article_processing_charge":"Yes (via OA deal)","date_published":"2024-06-19T00:00:00Z","year":"2024","ddc":["500"],"publisher":"Oxford University Press","project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}]},{"day":"01","doi":"10.1002/rsa.21106","publication_status":"published","department":[{"_id":"MaKw"}],"month":"07","language":[{"iso":"eng"}],"quality_controlled":"1","oa_version":"Published Version","file":[{"relation":"main_file","checksum":"3a5969d0c512aef01c30f3dc81c6d59b","content_type":"application/pdf","success":1,"access_level":"open_access","file_size":1362334,"creator":"dernst","date_updated":"2023-10-04T09:37:26Z","file_name":"2023_RandomStructureAlgorithms_Liebenau.pdf","file_id":"14389","date_created":"2023-10-04T09:37:26Z"}],"citation":{"apa":"Liebenau, A., Mattos, L., Mendonca dos Santos, W., &#38; Skokan, J. (2023). Asymmetric Ramsey properties of random graphs involving cliques and cycles. <i>Random Structures and Algorithms</i>. Wiley. <a href=\"https://doi.org/10.1002/rsa.21106\">https://doi.org/10.1002/rsa.21106</a>","ama":"Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. Asymmetric Ramsey properties of random graphs involving cliques and cycles. <i>Random Structures and Algorithms</i>. 2023;62(4):1035-1055. doi:<a href=\"https://doi.org/10.1002/rsa.21106\">10.1002/rsa.21106</a>","ieee":"A. Liebenau, L. Mattos, W. Mendonca dos Santos, and J. Skokan, “Asymmetric Ramsey properties of random graphs involving cliques and cycles,” <i>Random Structures and Algorithms</i>, vol. 62, no. 4. Wiley, pp. 1035–1055, 2023.","ista":"Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. 2023. Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random Structures and Algorithms. 62(4), 1035–1055.","mla":"Liebenau, Anita, et al. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” <i>Random Structures and Algorithms</i>, vol. 62, no. 4, Wiley, 2023, pp. 1035–55, doi:<a href=\"https://doi.org/10.1002/rsa.21106\">10.1002/rsa.21106</a>.","short":"A. Liebenau, L. Mattos, W. Mendonca dos Santos, J. Skokan, Random Structures and Algorithms 62 (2023) 1035–1055.","chicago":"Liebenau, Anita, Letícia Mattos, Walner Mendonca dos Santos, and Jozef Skokan. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.” <i>Random Structures and Algorithms</i>. Wiley, 2023. <a href=\"https://doi.org/10.1002/rsa.21106\">https://doi.org/10.1002/rsa.21106</a>."},"tmp":{"name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","image":"/images/cc_by_nc.png","short":"CC BY-NC (4.0)"},"status":"public","acknowledgement":"This work was started at the thematic program GRAPHS@IMPA (January–March 2018), in Rio de Janeiro. We thank IMPA and the organisers for the hospitality and for providing a pleasant research environment. We thank Rob Morris for helpful discussions, and the anonymous referees for their careful reading and many helpful suggestions. Open Access funding enabled and organized by Projekt DEAL.\r\nA. Liebenau was supported by an ARC DECRA Fellowship Grant DE170100789. L. Mattos was supported by CAPES and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). W. Mendonça was supported by CAPES project 88882.332408/2010-01.","scopus_import":"1","title":"Asymmetric Ramsey properties of random graphs involving cliques and cycles","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","has_accepted_license":"1","oa":1,"publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"publication":"Random Structures and Algorithms","date_created":"2022-07-31T22:01:49Z","abstract":[{"text":"We say that (Formula presented.) if, in every edge coloring (Formula presented.), we can find either a 1-colored copy of (Formula presented.) or a 2-colored copy of (Formula presented.). The well-known states that the threshold for the property (Formula presented.) is equal to (Formula presented.), where (Formula presented.) is given by (Formula presented.) for any pair of graphs (Formula presented.) and (Formula presented.) with (Formula presented.). In this article, we show the 0-statement of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques. ","lang":"eng"}],"date_updated":"2023-10-04T09:38:45Z","type":"journal_article","license":"https://creativecommons.org/licenses/by-nc/4.0/","file_date_updated":"2023-10-04T09:37:26Z","date_published":"2023-07-01T00:00:00Z","page":"1035-1055","article_processing_charge":"Yes (in subscription journal)","ddc":["510"],"publisher":"Wiley","year":"2023","external_id":{"isi":["000828530400001"]},"_id":"11706","issue":"4","isi":1,"author":[{"full_name":"Liebenau, Anita","last_name":"Liebenau","first_name":"Anita"},{"full_name":"Mattos, Letícia","last_name":"Mattos","first_name":"Letícia"},{"first_name":"Walner","last_name":"Mendonca Dos Santos","full_name":"Mendonca Dos Santos, Walner","id":"12c6bd4d-2cd0-11ec-a0da-e28f42f65ebd"},{"first_name":"Jozef","last_name":"Skokan","full_name":"Skokan, Jozef"}],"intvolume":"        62","volume":62},{"article_type":"original","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"A note on long cycles in sparse random graphs","has_accepted_license":"1","oa":1,"abstract":[{"lang":"eng","text":"Let Lc,n denote the size of the longest cycle in G(n, c/n),c >1 constant.  We show that there exists a continuous function f(c) such that Lc,n/n→f(c) a.s.  for c>20,  thus  extending  a  result  of  Frieze  and  the  author  to  smaller  values  of c. Thereafter,  for c>20,  we  determine  the  limit  of  the  probability  that G(n, c/n)contains  cycles  of  every  length  between  the  length  of  its  shortest  and  its  longest cycles as n→∞."}],"date_created":"2023-05-21T22:01:05Z","publication":"Electronic Journal of Combinatorics","publication_identifier":{"eissn":["1077-8926"]},"file_date_updated":"2023-05-22T07:43:19Z","type":"journal_article","date_updated":"2024-10-09T21:05:26Z","month":"05","corr_author":"1","department":[{"_id":"MaKw"}],"publication_status":"published","doi":"10.37236/11471","day":"05","arxiv":1,"quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Published Version","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"citation":{"apa":"Anastos, M. (2023). A note on long cycles in sparse random graphs. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/11471\">https://doi.org/10.37236/11471</a>","ama":"Anastos M. A note on long cycles in sparse random graphs. <i>Electronic Journal of Combinatorics</i>. 2023;30(2). doi:<a href=\"https://doi.org/10.37236/11471\">10.37236/11471</a>","ieee":"M. Anastos, “A note on long cycles in sparse random graphs,” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 2. Electronic Journal of Combinatorics, 2023.","ista":"Anastos M. 2023. A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. 30(2), P2.21.","short":"M. Anastos, Electronic Journal of Combinatorics 30 (2023).","mla":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 2, P2.21, Electronic Journal of Combinatorics, 2023, doi:<a href=\"https://doi.org/10.37236/11471\">10.37236/11471</a>.","chicago":"Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2023. <a href=\"https://doi.org/10.37236/11471\">https://doi.org/10.37236/11471</a>."},"file":[{"file_name":"2023_JourCombinatorics_Anastos.pdf","date_created":"2023-05-22T07:43:19Z","file_id":"13046","file_size":448736,"creator":"dernst","date_updated":"2023-05-22T07:43:19Z","success":1,"access_level":"open_access","relation":"main_file","checksum":"6269ed3b3eded6536d3d9d6baad2d5b9","content_type":"application/pdf"}],"acknowledgement":"We would like to thank the reviewers for their helpful comments and remarks.","scopus_import":"1","_id":"13042","issue":"2","external_id":{"arxiv":["2105.13828"],"isi":["000988285500001"]},"author":[{"full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","first_name":"Michael"}],"isi":1,"intvolume":"        30","volume":30,"date_published":"2023-05-05T00:00:00Z","article_processing_charge":"No","publisher":"Electronic Journal of Combinatorics","ddc":["510"],"year":"2023","article_number":"P2.21"},{"date_updated":"2025-09-09T12:54:51Z","type":"journal_article","license":"https://creativecommons.org/licenses/by-nd/4.0/","file_date_updated":"2023-09-15T08:02:09Z","publication_identifier":{"eissn":["1077-8926"]},"publication":"Electronic Journal of Combinatorics","date_created":"2023-09-10T22:01:12Z","abstract":[{"text":"We study multigraphs whose edge-sets are the union of three perfect matchings, M1, M2, and M3. Given such a graph G and any a1; a2; a3 2 N with a1 +a2 +a3 6 n - 2, we show there exists a matching M of G with jM \\ Mij = ai for each i 2 f1; 2; 3g. The bound n - 2 in the theorem is best possible in general. We conjecture however that if G is bipartite, the same result holds with n - 2 replaced by n - 1. We give a construction that shows such a result would be tight. We\r\nalso make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour\r\nmultiplicities.","lang":"eng"}],"has_accepted_license":"1","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets","article_type":"original","scopus_import":"1","acknowledgement":"Anastos has received funding from the European Union’s Horizon 2020 research and in-novation programme under the Marie Sk lodowska-Curie grant agreement No 101034413.Fabian’s research is supported by the Deutsche Forschungsgemeinschaft (DFG, GermanResearch Foundation) Graduiertenkolleg “Facets of Complexity” (GRK 2434).","citation":{"mla":"Anastos, Michael, et al. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 3, P3.10, Electronic Journal of Combinatorics, 2023, doi:<a href=\"https://doi.org/10.37236/11714\">10.37236/11714</a>.","chicago":"Anastos, Michael, David Fabian, Alp Müyesser, and Tibor Szabó. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2023. <a href=\"https://doi.org/10.37236/11714\">https://doi.org/10.37236/11714</a>.","short":"M. Anastos, D. Fabian, A. Müyesser, T. Szabó, Electronic Journal of Combinatorics 30 (2023).","ista":"Anastos M, Fabian D, Müyesser A, Szabó T. 2023. Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. Electronic Journal of Combinatorics. 30(3), P3.10.","ieee":"M. Anastos, D. Fabian, A. Müyesser, and T. Szabó, “Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets,” <i>Electronic Journal of Combinatorics</i>, vol. 30, no. 3. Electronic Journal of Combinatorics, 2023.","apa":"Anastos, M., Fabian, D., Müyesser, A., &#38; Szabó, T. (2023). Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/11714\">https://doi.org/10.37236/11714</a>","ama":"Anastos M, Fabian D, Müyesser A, Szabó T. Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets. <i>Electronic Journal of Combinatorics</i>. 2023;30(3). doi:<a href=\"https://doi.org/10.37236/11714\">10.37236/11714</a>"},"file":[{"content_type":"application/pdf","checksum":"52c46c8cb329f9aaee9ade01525f317b","relation":"main_file","access_level":"open_access","success":1,"date_updated":"2023-09-15T08:02:09Z","creator":"dernst","file_size":247917,"file_id":"14338","date_created":"2023-09-15T08:02:09Z","file_name":"2023_elecJournCombinatorics_Anastos.pdf"}],"tmp":{"image":"/image/cc_by_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","short":"CC BY-ND (4.0)","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)"},"status":"public","quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"arxiv":1,"day":"28","ec_funded":1,"doi":"10.37236/11714","department":[{"_id":"MaKw"}],"publication_status":"published","month":"07","volume":30,"intvolume":"        30","author":[{"first_name":"Michael","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos"},{"last_name":"Fabian","full_name":"Fabian, David","first_name":"David"},{"first_name":"Alp","last_name":"Müyesser","full_name":"Müyesser, Alp"},{"last_name":"Szabó","full_name":"Szabó, Tibor","first_name":"Tibor"}],"isi":1,"issue":"3","_id":"14319","external_id":{"arxiv":["2212.03100"],"isi":["001042382200001"]},"article_number":"P3.10","year":"2023","ddc":["510"],"publisher":"Electronic Journal of Combinatorics","project":[{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"article_processing_charge":"Yes","date_published":"2023-07-28T00:00:00Z"},{"title":"Fast algorithms for solving the Hamilton cycle problem with high probability","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"conference":{"location":"Florence, Italy","end_date":"2023-01-25","name":"SODA: Symposium on Discrete Algorithms","start_date":"2023-01-22"},"date_created":"2023-09-17T22:01:10Z","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","publication_identifier":{"isbn":["9781611977554"]},"abstract":[{"text":"We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and  respectively, each being best possible in its own setting.","lang":"eng"}],"type":"conference","date_updated":"2024-10-09T21:07:01Z","publication_status":"published","department":[{"_id":"MaKw"}],"doi":"10.1137/1.9781611977554.ch88","day":"01","month":"01","corr_author":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"citation":{"ieee":"M. Anastos, “Fast algorithms for solving the Hamilton cycle problem with high probability,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy, 2023, vol. 2023, pp. 2286–2323.","ama":"Anastos M. Fast algorithms for solving the Hamilton cycle problem with high probability. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2023. Society for Industrial and Applied Mathematics; 2023:2286-2323. doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">10.1137/1.9781611977554.ch88</a>","apa":"Anastos, M. (2023). Fast algorithms for solving the Hamilton cycle problem with high probability. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2023, pp. 2286–2323). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">https://doi.org/10.1137/1.9781611977554.ch88</a>","mla":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2023, Society for Industrial and Applied Mathematics, 2023, pp. 2286–323, doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">10.1137/1.9781611977554.ch88</a>.","short":"M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 2286–2323.","chicago":"Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with High Probability.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2023:2286–2323. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977554.ch88\">https://doi.org/10.1137/1.9781611977554.ch88</a>.","ista":"Anastos M. 2023. Fast algorithms for solving the Hamilton cycle problem with high probability. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2023, 2286–2323."},"status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2111.14759","open_access":"1"}],"scopus_import":"1","external_id":{"arxiv":["2111.14759"]},"_id":"14344","author":[{"full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","first_name":"Michael"}],"intvolume":"      2023","volume":2023,"date_published":"2023-01-01T00:00:00Z","page":"2286-2323","article_processing_charge":"No","publisher":"Society for Industrial and Applied Mathematics","year":"2023"},{"oa":1,"title":"Substructures in Latin squares","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_type":"original","date_updated":"2025-09-09T13:08:47Z","type":"journal_article","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"date_created":"2023-10-22T22:01:14Z","publication":"Israel Journal of Mathematics","abstract":[{"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.","lang":"eng"}],"oa_version":"Preprint","quality_controlled":"1","language":[{"iso":"eng"}],"arxiv":1,"day":"01","doi":"10.1007/s11856-023-2513-9","department":[{"_id":"MaKw"}],"publication_status":"published","month":"09","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.","scopus_import":"1","citation":{"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>.","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.","ista":"Kwan MA, Sah A, Sawhney M, Simkin M. 2023. Substructures in Latin squares. Israel Journal of Mathematics. 256(2), 363–416.","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.","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>","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>"},"status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2202.05088","open_access":"1"}],"author":[{"last_name":"Kwan","full_name":"Kwan, Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan"},{"first_name":"Ashwin","full_name":"Sah, Ashwin","last_name":"Sah"},{"first_name":"Mehtaab","full_name":"Sawhney, Mehtaab","last_name":"Sawhney"},{"full_name":"Simkin, Michael","last_name":"Simkin","first_name":"Michael"}],"isi":1,"external_id":{"arxiv":["2202.05088"],"isi":["001081646400001"]},"_id":"14444","issue":"2","volume":256,"intvolume":"       256","page":"363-416","article_processing_charge":"Yes (in subscription journal)","date_published":"2023-09-01T00:00:00Z","year":"2023","publisher":"Springer Nature"}]