[{"publication_status":"published","isi":1,"department":[{"_id":"MaKw"}],"author":[{"first_name":"Zdeněk","full_name":"Dvořák, Zdeněk","last_name":"Dvořák"},{"id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","first_name":"Benjamin","full_name":"Moore, Benjamin","last_name":"Moore"},{"last_name":"Seifrtová","full_name":"Seifrtová, Michaela","first_name":"Michaela"},{"last_name":"Šámal","full_name":"Šámal, Robert","first_name":"Robert"}],"volume":127,"month":"06","ddc":["510"],"intvolume":"       127","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)","language":[{"iso":"eng"}],"oa_version":"Published Version","OA_place":"publisher","article_number":"104138","corr_author":"1","citation":{"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>","short":"Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics 127 (2025).","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>.","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.","ista":"Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138."},"OA_type":"hybrid","has_accepted_license":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"journal_article","publication":"European Journal of Combinatorics","article_processing_charge":"Yes (via OA deal)","day":"01","year":"2025","file_date_updated":"2025-06-24T06:33:30Z","date_created":"2025-06-23T13:54:46Z","date_published":"2025-06-01T00:00:00Z","external_id":{"isi":["001443061400001"],"arxiv":["2312.13061"]},"_id":"19879","article_type":"original","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"arxiv":1,"doi":"10.1016/j.ejc.2025.104138","status":"public","date_updated":"2025-09-30T13:42:59Z","publication_identifier":{"issn":["0195-6698"]},"publisher":"Elsevier","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."}],"title":"Precoloring extension in planar near-Eulerian-triangulations","quality_controlled":"1","file":[{"access_level":"open_access","file_size":564203,"creator":"dernst","relation":"main_file","date_created":"2025-06-24T06:33:30Z","file_name":"2025_EuropJournCombinatorics_Dvorak.pdf","date_updated":"2025-06-24T06:33:30Z","content_type":"application/pdf","checksum":"8b3585df45b25091fba9bee9854b7d01","file_id":"19887","success":1}]},{"language":[{"iso":"eng"}],"oa_version":"Published Version","page":"2098-2106","scopus_import":"1","ddc":["000"],"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.","department":[{"_id":"MaKw"}],"conference":{"start_date":"2025-06-23","location":"Prague, Czechia","end_date":"2025-06-27","name":"STOC: Symposium on Theory of Computing"},"author":[{"last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"},{"orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin","last_name":"Moore"}],"publication_status":"published","month":"06","has_accepted_license":"1","ec_funded":1,"citation":{"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.","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>","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>","ista":"Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 2098–2106.","ieee":"M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 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>.","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>."},"corr_author":"1","OA_type":"hybrid","OA_place":"publisher","date_created":"2025-07-13T22:01:23Z","external_id":{"arxiv":["2410.06095"]},"_id":"20007","date_published":"2025-06-15T00:00:00Z","year":"2025","file_date_updated":"2025-07-14T06:13:10Z","day":"15","article_processing_charge":"Yes (via OA deal)","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","title":"Smoothed analysis for graph isomorphism","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."}],"quality_controlled":"1","publisher":"Association for Computing Machinery","file":[{"date_created":"2025-07-14T06:13:10Z","relation":"main_file","file_size":706445,"creator":"dernst","access_level":"open_access","file_name":"2025_STOC_Anastos.pdf","date_updated":"2025-07-14T06:13:10Z","success":1,"checksum":"cf0ab9cb9c6abda188de13dc3f9a4c9b","file_id":"20012","content_type":"application/pdf"}],"publication_identifier":{"isbn":["9798400715105"],"issn":["0737-8017"]},"arxiv":1,"status":"public","date_updated":"2025-07-14T06:33:50Z","doi":"10.1145/3717823.3718173","project":[{"name":"Randomness and structure in combinatorics","grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"},{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"},{"grant_number":"ESP3863424","name":"Combinatorial Optimisation Problems on Sparse Random Graphs","_id":"8f906bd2-16d5-11f0-9cad-e07be8aa9ac9"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1},{"date_created":"2025-09-10T05:36:50Z","date_published":"2025-12-01T00:00:00Z","external_id":{"arxiv":["2310.00931"],"isi":["001529769300002"]},"_id":"20320","year":"2025","file_date_updated":"2025-12-30T10:18:56Z","article_processing_charge":"Yes (via OA deal)","day":"01","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"European Journal of Combinatorics","publisher":"Elsevier","quality_controlled":"1","PlanS_conform":"1","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."}],"title":"Beyond the pseudoforest strong Nine Dragon Tree theorem","file":[{"success":1,"content_type":"application/pdf","file_id":"20913","checksum":"b1536e9256c4510a0e21452032e43a26","date_updated":"2025-12-30T10:18:56Z","file_name":"2025_EuropJournCombinatorics_Mies.pdf","date_created":"2025-12-30T10:18:56Z","relation":"main_file","access_level":"open_access","file_size":737845,"creator":"dernst"}],"publication_identifier":{"issn":["0195-6698"]},"arxiv":1,"doi":"10.1016/j.ejc.2025.104214","date_updated":"2025-12-30T10:19:10Z","status":"public","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","oa":1,"language":[{"iso":"eng"}],"oa_version":"Published Version","intvolume":"       130","ddc":["500"],"scopus_import":"1","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.","publication_status":"published","isi":1,"department":[{"_id":"MaKw"}],"author":[{"first_name":"Sebastian","last_name":"Mies","full_name":"Mies, Sebastian"},{"full_name":"Moore, Benjamin","last_name":"Moore","first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6"},{"first_name":"Evelyne","full_name":"Smith-Roberge, Evelyne","last_name":"Smith-Roberge"}],"month":"12","volume":130,"has_accepted_license":"1","article_number":"104214","corr_author":"1","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.","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>.","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.","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>.","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>"},"OA_type":"hybrid","issue":"12","OA_place":"publisher"},{"file_date_updated":"2025-10-21T07:36:56Z","year":"2025","date_published":"2025-09-11T00:00:00Z","external_id":{"arxiv":["2505.03954"],"isi":["001575137400001"]},"_id":"20504","date_created":"2025-10-20T11:08:57Z","publication":"International Mathematics Research Notices","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","article_processing_charge":"Yes (via OA deal)","day":"11","publication_identifier":{"eissn":["1687-0247"],"issn":["1073-7928"]},"file":[{"success":1,"content_type":"application/pdf","file_id":"20511","checksum":"016aa4df9453dc180ae7504ac77bf72f","date_updated":"2025-10-21T07:36:56Z","file_name":"2025_IMRN_Jain.pdf","date_created":"2025-10-21T07:36:56Z","relation":"main_file","file_size":774323,"creator":"dernst","access_level":"open_access"}],"publisher":"Oxford University Press","abstract":[{"lang":"eng","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)."}],"quality_controlled":"1","title":"The edge-statistics conjecture for hypergraphs","PlanS_conform":"1","oa":1,"article_type":"original","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"project":[{"name":"Randomness and structure in combinatorics","grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"date_updated":"2025-12-01T13:00:35Z","doi":"10.1093/imrn/rnaf273","status":"public","arxiv":1,"oa_version":"Published Version","language":[{"iso":"eng"}],"month":"09","volume":2025,"publication_status":"published","isi":1,"author":[{"last_name":"Jain","full_name":"Jain, Vishesh","first_name":"Vishesh"},{"orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan"},{"first_name":"Dhruv","full_name":"Mubayi, Dhruv","last_name":"Mubayi"},{"first_name":"Tuan","full_name":"Tran, Tuan","last_name":"Tran"}],"department":[{"_id":"MaKw"}],"acknowledgement":"This work was supported by NSF CAREER award DMS-2237646 [to V.J.], ERC Starting Grant “RANDSTRUCT” [no. 101076777 to M.K.], NSF grant DMS-2153576 [to D.M.], and the National Key Research and Development Program of China [2023YFA101020 to T.T.].\r\nWe would like to thank Lisa Sauermann for her helpful comments. We would also like to thank Alex Grebennikov for identifying an oversight in the application of Theorem 7.1 (in a previous version of this paper).","ddc":["510"],"intvolume":"      2025","scopus_import":"1","issue":"18","OA_type":"hybrid","corr_author":"1","article_number":"rnaf273","citation":{"ama":"Jain V, Kwan MA, Mubayi D, Tran T. The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. 2025;2025(18). doi:<a href=\"https://doi.org/10.1093/imrn/rnaf273\">10.1093/imrn/rnaf273</a>","apa":"Jain, V., Kwan, M. A., Mubayi, D., &#38; Tran, T. (2025). The edge-statistics conjecture for hypergraphs. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rnaf273\">https://doi.org/10.1093/imrn/rnaf273</a>","short":"V. Jain, M.A. Kwan, D. Mubayi, T. Tran, International Mathematics Research Notices 2025 (2025).","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>.","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.","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>.","ista":"Jain V, Kwan MA, Mubayi D, Tran T. 2025. The edge-statistics conjecture for hypergraphs. International Mathematics Research Notices. 2025(18), rnaf273."},"has_accepted_license":"1","OA_place":"publisher"},{"language":[{"iso":"eng"}],"page":"52-65","oa_version":"Published Version","publication_status":"published","isi":1,"author":[{"full_name":"Brunck, Florestan R","last_name":"Brunck","id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","first_name":"Florestan R"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","last_name":"Kwan"}],"department":[{"_id":"UlWa"},{"_id":"MaKw"}],"volume":47,"month":"03","intvolume":"        47","ddc":["510"],"scopus_import":"1","acknowledgement":"Open access funding provided by Copenhagen University.","citation":{"ista":"Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note on sliding block puzzles. Mathematical Intelligencer. 47, 52–65.","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>.","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.","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.","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>","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>"},"OA_type":"hybrid","has_accepted_license":"1","OA_place":"publisher","year":"2025","file_date_updated":"2025-04-08T11:17:45Z","date_created":"2024-09-29T22:01:38Z","date_published":"2025-03-01T00:00:00Z","external_id":{"arxiv":["2303.09459"],"isi":["001318056000001"]},"_id":"18157","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","publication":"Mathematical Intelligencer","article_processing_charge":"Yes (via OA deal)","day":"01","publication_identifier":{"issn":["0343-6993"]},"publisher":"Springer Nature","title":"Books, Hallways, and social butterflies: A note on sliding block puzzles","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."}],"quality_controlled":"1","file":[{"date_updated":"2025-04-08T11:17:45Z","checksum":"c932ebe45c460d4a73f5b2dcca643db1","file_id":"19530","content_type":"application/pdf","success":1,"access_level":"open_access","file_size":1760643,"creator":"dernst","relation":"main_file","date_created":"2025-04-08T11:17:45Z","file_name":"2025_MathIntelligencer_Brunck.pdf"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","oa":1,"arxiv":1,"status":"public","date_updated":"2025-05-19T14:00:09Z","doi":"10.1007/s00283-024-10358-x"},{"das_tickbox":"1","OA_place":"publisher","citation":{"ista":"Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. The exact rank of sparse random graphs. Journal of the European Mathematical Society.","ieee":"M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “The exact rank of sparse random graphs,” <i>Journal of the European Mathematical Society</i>. EMS Press, 2025.","chicago":"Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney. “The Exact Rank of Sparse Random Graphs.” <i>Journal of the European Mathematical Society</i>. EMS Press, 2025. <a href=\"https://doi.org/10.4171/jems/1692\">https://doi.org/10.4171/jems/1692</a>.","mla":"Glasgow, Margalit, et al. “The Exact Rank of Sparse Random Graphs.” <i>Journal of the European Mathematical Society</i>, EMS Press, 2025, doi:<a href=\"https://doi.org/10.4171/jems/1692\">10.4171/jems/1692</a>.","short":"M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the European Mathematical Society (2025).","ama":"Glasgow M, Kwan MA, Sah A, Sawhney M. The exact rank of sparse random graphs. <i>Journal of the European Mathematical Society</i>. 2025. doi:<a href=\"https://doi.org/10.4171/jems/1692\">10.4171/jems/1692</a>","apa":"Glasgow, M., Kwan, M. A., Sah, A., &#38; Sawhney, M. (2025). The exact rank of sparse random graphs. <i>Journal of the European Mathematical Society</i>. EMS Press. <a href=\"https://doi.org/10.4171/jems/1692\">https://doi.org/10.4171/jems/1692</a>"},"corr_author":"1","OA_type":"diamond","has_accepted_license":"1","author":[{"first_name":"Margalit","last_name":"Glasgow","full_name":"Glasgow, Margalit"},{"last_name":"Kwan","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"full_name":"Sah, Ashwin","last_name":"Sah","first_name":"Ashwin"},{"first_name":"Mehtaab","full_name":"Sawhney, Mehtaab","last_name":"Sawhney"}],"department":[{"_id":"MaKw"}],"publication_status":"epub_ahead","month":"09","ddc":["510"],"acknowledgement":"We would like to thank Noga Alon for suggesting that our main result gives\r\na linear-time algorithm for computing the rank. We also thank the referees for a number of thoughtful comments and suggestions. Glasgow was supported by NSF graduate research fellowship program award DGE1656518. Kwan was supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-1745302.\r\n","language":[{"iso":"eng"}],"oa_version":"Published Version","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","oa":1,"arxiv":1,"doi":"10.4171/jems/1692","date_updated":"2026-07-06T11:51:31Z","status":"public","project":[{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"DOAJ_listed":"1","publication_identifier":{"issn":["1435-9855"],"eissn":["1435-9863"]},"main_file_link":[{"url":"https://doi.org/10.4171/JEMS/1692","open_access":"1"}],"title":"The exact rank of sparse random graphs","PlanS_conform":"1","quality_controlled":"1","abstract":[{"text":"Two landmark results in combinatorial random matrix theory, due to Komlós and Costello–Tao–Vu, show that discrete random matrices and symmetric discrete random matrices are typically nonsingular. In particular, in the language of graph theory, when p is a fixed constant, the biadjacency matrix of a random Erdős–Rényi bipartite graph G(n,n,p) and the adjacency matrix of an Erdős–Rényi random graph G(n,p) are both nonsingular with high probability. However, very sparse random graphs (i.e., where p is allowed to decay rapidly with n) are typically singular, due to the presence of “local” dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbour. In this paper, we give a combinatorial description of the rank of a sparse random graph G(n,n,c/n) or G(n,c/n) in terms of such local dependencies, for all constants c=e (and we present some evidence that the situation is very different for c=e). This gives an essentially complete answer to a question raised by Vu (2014). As applications of our main theorem and its proof, we also determine the asymptotic singularity probability of the 2-core of a sparse random graph, we show that the rank of a sparse random graph is extremely well approximated by its matching number, and we deduce a central limit theorem for the rank of G(n,c/n).","lang":"eng"}],"publisher":"EMS Press","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Journal of the European Mathematical Society","day":"02","article_processing_charge":"No","year":"2025","date_created":"2026-02-17T07:41:59Z","external_id":{"arxiv":["2303.05435"]},"_id":"21263","date_published":"2025-09-02T00:00:00Z"},{"oa_version":"Published Version","page":"1517-1535","language":[{"iso":"eng"}],"volume":15,"month":"11","department":[{"_id":"MaKw"},{"_id":"KrCh"}],"author":[{"last_name":"Attia","full_name":"Attia, Luc","first_name":"Luc"},{"id":"9aa8388e-d003-11ee-8458-c4c1d7447977","first_name":"Lyuben","full_name":"Lichev, Lyuben","last_name":"Lichev"},{"first_name":"Dieter","last_name":"Mitsche","full_name":"Mitsche, Dieter"},{"full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"full_name":"Ziliotto, Bruno","last_name":"Ziliotto","first_name":"Bruno"}],"publication_status":"published","isi":1,"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was supported by the French Agence Nationale de la Recherche (ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002 (GrHyDy), by Fondecyt grant 1220174, by ANID Chile grant ACT210005, and by the ERC CoG 863818 (ForM-SMArt) grant. This collaboration was mainly conducted during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at University of Chile in 2023, under the IRL program of CNRS. This work was supported by Fondation CFM pour la Recherche. This paper has also been funded by the Agence Nationale de la Recherche under grant ANR-17-EURE-0010 (Investissements d’Avenir program).","scopus_import":"1","ddc":["000"],"intvolume":"        15","OA_type":"hybrid","citation":{"short":"L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic Games and Applications 15 (2025) 1517–1535.","apa":"Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2025). Random zero-sum dynamic games on infinite directed graphs. <i>Dynamic Games and Applications</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s13235-025-00636-4\">https://doi.org/10.1007/s13235-025-00636-4</a>","ama":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Random zero-sum dynamic games on infinite directed graphs. <i>Dynamic Games and Applications</i>. 2025;15:1517-1535. doi:<a href=\"https://doi.org/10.1007/s13235-025-00636-4\">10.1007/s13235-025-00636-4</a>","ista":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. 2025. Random zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications. 15, 1517–1535.","mla":"Attia, Luc, et al. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” <i>Dynamic Games and Applications</i>, vol. 15, Springer Nature, 2025, pp. 1517–35, doi:<a href=\"https://doi.org/10.1007/s13235-025-00636-4\">10.1007/s13235-025-00636-4</a>.","ieee":"L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Random zero-sum dynamic games on infinite directed graphs,” <i>Dynamic Games and Applications</i>, vol. 15. Springer Nature, pp. 1517–1535, 2025.","chicago":"Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” <i>Dynamic Games and Applications</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s13235-025-00636-4\">https://doi.org/10.1007/s13235-025-00636-4</a>."},"corr_author":"1","related_material":{"record":[{"id":"20234","status":"public","relation":"dissertation_contains"}]},"ec_funded":1,"has_accepted_license":"1","OA_place":"publisher","file_date_updated":"2025-12-30T08:13:04Z","year":"2025","_id":"19508","external_id":{"isi":["001449708900001"]},"date_published":"2025-11-01T00:00:00Z","date_created":"2025-04-06T22:01:32Z","publication":"Dynamic Games and Applications","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","article_processing_charge":"Yes (via OA deal)","publication_identifier":{"issn":["2153-0785"],"eissn":["2153-0793"]},"file":[{"file_name":"2025_DynGamesAppl_Attia.pdf","access_level":"open_access","creator":"dernst","file_size":570994,"date_created":"2025-12-30T08:13:04Z","relation":"main_file","checksum":"b3a1b7eef40c9ac2acf3fef563081694","file_id":"20891","content_type":"application/pdf","success":1,"date_updated":"2025-12-30T08:13:04Z"}],"title":"Random zero-sum dynamic games on infinite directed graphs","PlanS_conform":"1","quality_controlled":"1","abstract":[{"text":"We consider random two-player zero-sum dynamic games with perfect information on a class of infinite directed graphs. Starting from a fixed vertex, the players take turns to move a token along the edges of the graph. Every vertex is assigned a payoff known in advance by both players. Every time the token visits a vertex, Player 2 pays Player 1 the corresponding payoff. We consider a distribution over such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that, when the duration of the game tends to infinity, the value converges almost surely to a constant at an exponential rate dominated in terms of the expansion. On the other hand, for the infinite d-ary tree (that does not fall into the previous class of graphs), we show convergence at a double-exponential rate.","lang":"eng"}],"publisher":"Springer Nature","oa":1,"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","status":"public","date_updated":"2026-07-29T13:14:36Z","doi":"10.1007/s13235-025-00636-4","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}]},{"publication_identifier":{"issn":["0012-365X"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2301.11615"}],"title":"Decompositions into two linear forests of bounded lengths","quality_controlled":"1","abstract":[{"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.","lang":"eng"}],"publisher":"Elsevier","article_type":"original","oa":1,"arxiv":1,"date_updated":"2025-09-04T13:10:26Z","status":"public","doi":"10.1016/j.disc.2024.113962","year":"2024","date_created":"2024-03-24T23:00:58Z","external_id":{"arxiv":["2301.11615"],"isi":["001226893800001"]},"_id":"15163","date_published":"2024-06-01T00:00:00Z","type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"Discrete Mathematics","day":"01","article_processing_charge":"No","citation":{"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>.","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.","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>.","ista":"Campbell R, Hörsch F, Moore B. 2024. Decompositions into two linear forests of bounded lengths. Discrete Mathematics. 347(6), 113962.","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>","short":"R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024)."},"article_number":"113962","corr_author":"1","issue":"6","language":[{"iso":"eng"}],"oa_version":"Preprint","author":[{"first_name":"Rutger","last_name":"Campbell","full_name":"Campbell, Rutger"},{"last_name":"Hörsch","full_name":"Hörsch, Florian","first_name":"Florian"},{"first_name":"Benjamin","id":"6dc1a1be-bf1c-11ed-8d2b-d044840f49d6","full_name":"Moore, Benjamin","last_name":"Moore"}],"department":[{"_id":"MaKw"}],"isi":1,"publication_status":"published","volume":347,"month":"06","scopus_import":"1","intvolume":"       347","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."},{"OA_type":"green","issue":"3","citation":{"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>","short":"M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Annals of Mathematics 200 (2024) 1059–1156.","ieee":"M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “High-girth Steiner triple systems,” <i>Annals of Mathematics</i>, vol. 200, no. 3. Princeton University, pp. 1059–1156, 2024.","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>.","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>.","ista":"Kwan MA, Sah A, Sawhney M, Simkin M. 2024. High-girth Steiner triple systems. Annals of Mathematics. 200(3), 1059–1156."},"corr_author":"1","OA_place":"repository","oa_version":"Preprint","page":"1059-1156","language":[{"iso":"eng"}],"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","intvolume":"       200","volume":200,"month":"11","author":[{"last_name":"Kwan","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"first_name":"Ashwin","last_name":"Sah","full_name":"Sah, Ashwin"},{"first_name":"Mehtaab","full_name":"Sawhney, Mehtaab","last_name":"Sawhney"},{"last_name":"Simkin","full_name":"Simkin, Michael","first_name":"Michael"}],"department":[{"_id":"MaKw"}],"isi":1,"publication_status":"published","abstract":[{"text":"We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth.","lang":"eng"}],"title":"High-girth Steiner triple systems","quality_controlled":"1","publisher":"Princeton University","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2201.04554"}],"publication_identifier":{"issn":["0003-486X"],"eissn":["1939-8980"]},"date_updated":"2025-09-08T14:40:55Z","doi":"10.4007/annals.2024.200.3.4","status":"public","arxiv":1,"oa":1,"article_type":"original","external_id":{"isi":["001366233800004"],"arxiv":["2201.04554"]},"_id":"18559","date_published":"2024-11-01T00:00:00Z","date_created":"2024-11-17T23:01:48Z","year":"2024","day":"01","article_processing_charge":"No","publication":"Annals of Mathematics","type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"arxiv":1,"date_updated":"2025-12-02T13:52:26Z","status":"public","doi":"10.1112/jlms.70010","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","call_identifier":"H2020"},{"_id":"bd95085b-d553-11ed-ba76-e55d3349be45","grant_number":"101076777","name":"Randomness and structure in combinatorics"}],"article_type":"original","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"title":"Partitioning problems via random processes","quality_controlled":"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"}],"publisher":"Wiley","file":[{"date_updated":"2024-12-10T08:10:39Z","success":1,"content_type":"application/pdf","file_id":"18639","checksum":"98e301e0565d75e3fb50e10e982a5018","relation":"main_file","date_created":"2024-12-10T08:10:39Z","file_size":539891,"creator":"dernst","access_level":"open_access","file_name":"2024_JournLondonMathSoc_Anastos.pdf"}],"publication_identifier":{"issn":["0024-6107"],"eissn":["1469-7750"]},"day":"01","article_processing_charge":"Yes (via OA deal)","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","publication":"Journal of the London Mathematical Society","date_created":"2024-11-24T23:01:48Z","_id":"18583","external_id":{"isi":["001374738100001"],"arxiv":["2307.06453"]},"date_published":"2024-12-01T00:00:00Z","year":"2024","file_date_updated":"2024-12-10T08:10:39Z","OA_place":"publisher","has_accepted_license":"1","ec_funded":1,"citation":{"ista":"Anastos M, Cooley O, Kang M, Kwan MA. 2024. Partitioning problems via random processes. Journal of the London Mathematical Society. 110(6), e70010.","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>.","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>.","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.","short":"M. Anastos, O. Cooley, M. Kang, M.A. Kwan, Journal of the London Mathematical Society 110 (2024).","apa":"Anastos, M., Cooley, O., Kang, M., &#38; Kwan, M. A. (2024). Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. Wiley. <a href=\"https://doi.org/10.1112/jlms.70010\">https://doi.org/10.1112/jlms.70010</a>","ama":"Anastos M, Cooley O, Kang M, Kwan MA. Partitioning problems via random processes. <i>Journal of the London Mathematical Society</i>. 2024;110(6). doi:<a href=\"https://doi.org/10.1112/jlms.70010\">10.1112/jlms.70010</a>"},"article_number":"e70010","corr_author":"1","OA_type":"hybrid","issue":"6","scopus_import":"1","ddc":["510"],"intvolume":"       110","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.","department":[{"_id":"MaKw"}],"author":[{"first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","full_name":"Anastos, Michael"},{"id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","first_name":"Oliver","full_name":"Cooley, Oliver","last_name":"Cooley"},{"last_name":"Kang","full_name":"Kang, Mihyun","first_name":"Mihyun"},{"full_name":"Kwan, Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"}],"publication_status":"published","isi":1,"volume":110,"month":"12","language":[{"iso":"eng"}],"oa_version":"Published Version"},{"article_processing_charge":"Yes","day":"24","type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"Electronic Communications in Probability","date_created":"2024-12-15T23:01:51Z","date_published":"2024-11-24T00:00:00Z","external_id":{"arxiv":["2311.16631"],"isi":["001356019700001"]},"_id":"18655","year":"2024","file_date_updated":"2024-12-16T07:33:34Z","arxiv":1,"DOAJ_listed":"1","project":[{"grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020"}],"doi":"10.1214/24-ECP639","status":"public","date_updated":"2025-09-09T11:46:53Z","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","oa":1,"publisher":"Duke University Press","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."}],"title":"Climbing up a random subgraph of the hypercube","quality_controlled":"1","file":[{"file_name":"2024_ElectrCommProbability_Anastos.pdf","creator":"dernst","access_level":"open_access","file_size":530169,"date_created":"2024-12-16T07:33:34Z","relation":"main_file","file_id":"18657","content_type":"application/pdf","checksum":"307a9d049325e6ca9bfe8b4a1f275983","success":1,"date_updated":"2024-12-16T07:33:34Z"}],"publication_identifier":{"eissn":["1083-589X"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2311.16631"}],"intvolume":"        29","ddc":["510"],"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.","isi":1,"publication_status":"published","author":[{"full_name":"Anastos, Michael","last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"},{"last_name":"Diskin","full_name":"Diskin, Sahar","first_name":"Sahar"},{"first_name":"Dor","last_name":"Elboim","full_name":"Elboim, Dor"},{"last_name":"Krivelevich","full_name":"Krivelevich, Michael","first_name":"Michael"}],"department":[{"_id":"MaKw"}],"month":"11","volume":29,"language":[{"iso":"eng"}],"oa_version":"Published Version","OA_place":"repository","has_accepted_license":"1","ec_funded":1,"corr_author":"1","article_number":"70","citation":{"short":"M. Anastos, S. Diskin, D. Elboim, M. Krivelevich, Electronic Communications in Probability 29 (2024).","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>","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>","ista":"Anastos M, Diskin S, Elboim D, Krivelevich M. 2024. Climbing up a random subgraph of the hypercube. Electronic Communications in Probability. 29, 70.","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>.","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.","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>."},"OA_type":"gold"},{"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773539"]},"file":[{"file_name":"2024_LIPIcs_Lill.pdf","creator":"dernst","file_size":927326,"access_level":"open_access","relation":"main_file","date_created":"2025-01-08T09:14:59Z","content_type":"application/pdf","checksum":"a64b9a0e41f7b867d25cb155825ccd53","file_id":"18775","success":1,"date_updated":"2025-01-08T09:14:59Z"}],"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)."}],"quality_controlled":"1","title":"Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","date_updated":"2026-01-05T13:46:07Z","doi":"10.4230/LIPIcs.IPEC.2024.2","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","call_identifier":"H2020"}],"arxiv":1,"file_date_updated":"2025-01-08T09:14:59Z","year":"2024","external_id":{"arxiv":["2407.01071"],"isi":["001534851900002"]},"_id":"18758","date_published":"2024-12-05T00:00:00Z","date_created":"2025-01-05T23:01:57Z","publication":"19th International Symposium on Parameterized and Exact Computation","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"05","article_processing_charge":"Yes","OA_type":"gold","citation":{"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>.","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.","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>.","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.","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>","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."},"article_number":"2","corr_author":"1","related_material":{"record":[{"relation":"later_version","id":"19603","status":"public"}]},"alternative_title":["LIPIcs"],"ec_funded":1,"has_accepted_license":"1","OA_place":"publisher","oa_version":"Published Version","language":[{"iso":"eng"}],"month":"12","volume":321,"department":[{"_id":"MaKw"}],"conference":{"start_date":"2024-09-04","location":"Egham, United Kingdom","end_date":"2024-09-06","name":"IPEC: Symposium on Parameterized and Exact Computation"},"author":[{"first_name":"Jonas","full_name":"Lill, Jonas","last_name":"Lill"},{"id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","first_name":"Kalina H","full_name":"Petrova, Kalina H","last_name":"Petrova"},{"full_name":"Weber, Simon","last_name":"Weber","first_name":"Simon"}],"isi":1,"publication_status":"published","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","scopus_import":"1","intvolume":"       321","ddc":["500"]},{"OA_place":"publisher","OA_type":"hybrid","issue":"10","citation":{"short":"M.A. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024) 3196–3208.","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>","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>","ista":"Kwan MA, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of the London Mathematical Society. 56(10), 3196–3208.","mla":"Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.” <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10, London Mathematical Society, 2024, pp. 3196–208, doi:<a href=\"https://doi.org/10.1112/blms.13127\">10.1112/blms.13127</a>.","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>.","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."},"has_accepted_license":"1","month":"10","volume":56,"department":[{"_id":"MaKw"}],"author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan"},{"first_name":"Yuval","full_name":"Wigderson, Yuval","last_name":"Wigderson"}],"publication_status":"published","isi":1,"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","intvolume":"        56","ddc":["510"],"oa_version":"Published Version","page":"3196-3208","language":[{"iso":"eng"}],"oa":1,"article_type":"original","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","date_updated":"2025-09-08T08:45:39Z","doi":"10.1112/blms.13127","project":[{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"arxiv":1,"publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"file":[{"success":1,"content_type":"application/pdf","checksum":"7117f9819eaeb45eef1b0a226f9c2709","file_id":"18814","date_updated":"2025-01-09T13:36:53Z","file_name":"2024_BulletinLondonMathSoc_Kwan.pdf","relation":"main_file","date_created":"2025-01-09T13:36:53Z","creator":"dernst","file_size":175966,"access_level":"open_access"}],"title":"The inertia bound is far from tight","quality_controlled":"1","abstract":[{"text":"The inertia bound and ratio bound (also known as the Cvetković bound and Hoffman bound) are two fundamental inequalities in spectral graph theory, giving upper bounds on the independence number α(G) of a graph G in terms of spectral information about a weighted adjacency matrix of G. For both inequalities, given a graph G, one needs to make a judicious choice of weighted adjacency matrix to obtain as strong a bound as possible.\r\nWhile there is a well-established theory surrounding the ratio bound, the inertia bound is much more mysterious, and its limits are rather unclear. In fact, only recently did Sinkovic find the first example of a graph for which the inertia bound is not tight (for any weighted adjacency matrix), answering a longstanding question of Godsil. We show that the inertia bound can be extremely far from tight, and in fact can significantly underperform the ratio bound: for example, one of our results is that for infinitely many n, there is an n-vertex graph for which even the unweighted ratio bound can prove α(G)≤4n3/4, but the inertia bound is always at least n/4. In particular, these results address questions of Rooney, Sinkovic, and Wocjan--Elphick--Abiad.","lang":"eng"}],"publisher":"London Mathematical Society","publication":"Bulletin of the London Mathematical Society","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"journal_article","day":"01","article_processing_charge":"Yes (via OA deal)","file_date_updated":"2025-01-09T13:36:53Z","year":"2024","_id":"17376","external_id":{"isi":["001279563300001"],"arxiv":["2312.04925"]},"date_published":"2024-10-01T00:00:00Z","date_created":"2024-08-04T22:01:22Z"},{"article_processing_charge":"Yes (via OA deal)","day":"19","type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"Quarterly Journal of Mathematics","date_created":"2024-09-01T22:01:07Z","date_published":"2024-06-19T00:00:00Z","external_id":{"isi":["001249741500001"],"arxiv":["2309.09788"]},"_id":"17475","year":"2024","file_date_updated":"2024-09-06T12:23:57Z","arxiv":1,"project":[{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"status":"public","doi":"10.1093/qmath/haae030","date_updated":"2025-09-08T09:09:41Z","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","oa":1,"publisher":"Oxford University Press","quality_controlled":"1","abstract":[{"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","lang":"eng"}],"title":"Exponentially many graphs are determined by their spectrum","file":[{"date_updated":"2024-09-06T12:23:57Z","file_id":"17851","checksum":"abf200d37ad69e6f2c0750a30296ad97","content_type":"application/pdf","success":1,"creator":"cchlebak","file_size":946411,"access_level":"open_access","date_created":"2024-09-06T12:23:57Z","relation":"main_file","file_name":"2024_QuJofMath_Koval.pdf"}],"publication_identifier":{"eissn":["1464-3847"],"issn":["0033-5606"]},"intvolume":"        75","ddc":["500"],"scopus_import":"1","acknowledgement":"Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777.","isi":1,"publication_status":"published","department":[{"_id":"MaKw"},{"_id":"VaKa"}],"author":[{"first_name":"Illya","id":"2eed1f3b-896a-11ed-bdf8-93c7c4bf159e","last_name":"Koval","full_name":"Koval, Illya"},{"first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","last_name":"Kwan","orcid":"0000-0002-4003-7567"}],"month":"06","volume":75,"language":[{"iso":"eng"}],"page":"869-899","oa_version":"Published Version","has_accepted_license":"1","corr_author":"1","citation":{"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>","short":"I. Koval, M.A. Kwan, Quarterly Journal of Mathematics 75 (2024) 869–899.","ieee":"I. Koval and M. A. Kwan, “Exponentially many graphs are determined by their spectrum,” <i>Quarterly Journal of Mathematics</i>, vol. 75, no. 3. Oxford University Press, pp. 869–899, 2024.","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>.","ista":"Koval I, Kwan MA. 2024. Exponentially many graphs are determined by their spectrum. Quarterly Journal of Mathematics. 75(3), 869–899."},"issue":"3"},{"month":"08","author":[{"first_name":"Ivailo","full_name":"Hartarsky, Ivailo","last_name":"Hartarsky"},{"last_name":"Lichev","full_name":"Lichev, Lyuben","first_name":"Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977"},{"last_name":"Toninelli","full_name":"Toninelli, Fabio Lucio","first_name":"Fabio Lucio"}],"department":[{"_id":"MaKw"}],"publication_status":"epub_ahead","scopus_import":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"OA_place":"repository","das_tickbox":"1","OA_type":"gold","citation":{"short":"I. Hartarsky, L. Lichev, F.L. Toninelli, Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions (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>","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.","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>.","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>.","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."},"publication":"Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","day":"26","article_processing_charge":"Yes","year":"2024","_id":"18951","external_id":{"arxiv":["2304.10930"]},"date_published":"2024-08-26T00:00:00Z","date_created":"2025-01-29T10:57:09Z","oa":1,"article_type":"original","status":"public","doi":"10.4171/aihpd/200","date_updated":"2026-07-23T05:41:50Z","DOAJ_listed":"1","mathsc":["05B50","05C70","82C20"],"arxiv":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2304.10930"}],"publication_identifier":{"eissn":["2308-5835"],"issn":["2308-5827"]},"title":"Local dimer dynamics in higher dimensions","quality_controlled":"1","abstract":[{"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.","lang":"eng"}],"publisher":"EMS Press"},{"intvolume":"     15364","scopus_import":"1","isi":1,"publication_status":"published","department":[{"_id":"MaKw"},{"_id":"KrPi"}],"conference":{"end_date":"2024-12-06","location":"Milan, Italy","start_date":"2024-12-02","name":"TCC: Theory of Cryptography"},"author":[{"full_name":"Anastos, Michael","last_name":"Anastos","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"},{"first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606"},{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad","last_name":"Baig","full_name":"Baig, Mirza Ahad"},{"orcid":"0000-0002-2505-4246","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"orcid":"0000-0002-4003-7567","last_name":"Kwan","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"month":"12","volume":15364,"language":[{"iso":"eng"}],"page":"413-443","oa_version":"Preprint","OA_place":"repository","alternative_title":["LNCS"],"related_material":{"record":[{"relation":"dissertation_contains","id":"22664","status":"public"}]},"corr_author":"1","citation":{"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>.","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.","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>.","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.","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>","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."},"OA_type":"green","article_processing_charge":"No","day":"02","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"22nd International Conference on Theory of Cryptography","date_created":"2024-12-22T23:01:47Z","date_published":"2024-12-02T00:00:00Z","_id":"18702","external_id":{"isi":["001545628900014"]},"year":"2024","doi":"10.1007/978-3-031-78011-0_14","date_updated":"2026-08-21T10:53:16Z","status":"public","oa":1,"publisher":"Springer Nature","abstract":[{"text":"In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. ","lang":"eng"}],"quality_controlled":"1","title":"The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031780103"],"eissn":["1611-3349"]},"main_file_link":[{"url":"https://eprint.iacr.org/2024/1097","open_access":"1"}]},{"article_processing_charge":"Yes (in subscription journal)","day":"01","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Random Structures and Algorithms","date_created":"2022-07-31T22:01:49Z","license":"https://creativecommons.org/licenses/by-nc/4.0/","date_published":"2023-07-01T00:00:00Z","external_id":{"isi":["000828530400001"]},"_id":"11706","year":"2023","file_date_updated":"2023-10-04T09:37:26Z","status":"public","date_updated":"2023-10-04T09:38:45Z","doi":"10.1002/rsa.21106","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","short":"CC BY-NC (4.0)","image":"/images/cc_by_nc.png"},"article_type":"original","oa":1,"publisher":"Wiley","title":"Asymmetric Ramsey properties of random graphs involving cliques and cycles","quality_controlled":"1","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"}],"file":[{"relation":"main_file","date_created":"2023-10-04T09:37:26Z","access_level":"open_access","file_size":1362334,"creator":"dernst","file_name":"2023_RandomStructureAlgorithms_Liebenau.pdf","date_updated":"2023-10-04T09:37:26Z","success":1,"file_id":"14389","checksum":"3a5969d0c512aef01c30f3dc81c6d59b","content_type":"application/pdf"}],"publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"intvolume":"        62","ddc":["510"],"scopus_import":"1","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.","publication_status":"published","isi":1,"author":[{"last_name":"Liebenau","full_name":"Liebenau, Anita","first_name":"Anita"},{"last_name":"Mattos","full_name":"Mattos, Letícia","first_name":"Letícia"},{"last_name":"Mendonca Dos Santos","full_name":"Mendonca Dos Santos, Walner","first_name":"Walner","id":"12c6bd4d-2cd0-11ec-a0da-e28f42f65ebd"},{"first_name":"Jozef","full_name":"Skokan, Jozef","last_name":"Skokan"}],"department":[{"_id":"MaKw"}],"month":"07","volume":62,"language":[{"iso":"eng"}],"page":"1035-1055","oa_version":"Published Version","has_accepted_license":"1","citation":{"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.","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>.","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>.","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.","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>","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>","short":"A. Liebenau, L. Mattos, W. Mendonca dos Santos, J. Skokan, Random Structures and Algorithms 62 (2023) 1035–1055."},"issue":"4"},{"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"article_type":"original","oa":1,"arxiv":1,"status":"public","date_updated":"2024-10-09T21:05:26Z","doi":"10.37236/11471","publication_identifier":{"eissn":["1077-8926"]},"abstract":[{"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→∞.","lang":"eng"}],"title":"A note on long cycles in sparse random graphs","quality_controlled":"1","publisher":"Electronic Journal of Combinatorics","file":[{"creator":"dernst","file_size":448736,"access_level":"open_access","date_created":"2023-05-22T07:43:19Z","relation":"main_file","file_name":"2023_JourCombinatorics_Anastos.pdf","date_updated":"2023-05-22T07:43:19Z","file_id":"13046","checksum":"6269ed3b3eded6536d3d9d6baad2d5b9","content_type":"application/pdf","success":1}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","type":"journal_article","publication":"Electronic Journal of Combinatorics","day":"05","article_processing_charge":"No","year":"2023","file_date_updated":"2023-05-22T07:43:19Z","date_created":"2023-05-21T22:01:05Z","_id":"13042","external_id":{"arxiv":["2105.13828"],"isi":["000988285500001"]},"date_published":"2023-05-05T00:00:00Z","citation":{"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>.","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.","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>.","ista":"Anastos M. 2023. A note on long cycles in sparse random graphs. Electronic Journal of Combinatorics. 30(2), P2.21.","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>","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>","short":"M. Anastos, Electronic Journal of Combinatorics 30 (2023)."},"corr_author":"1","article_number":"P2.21","issue":"2","has_accepted_license":"1","author":[{"last_name":"Anastos","full_name":"Anastos, Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael"}],"department":[{"_id":"MaKw"}],"publication_status":"published","isi":1,"volume":30,"month":"05","scopus_import":"1","intvolume":"        30","ddc":["510"],"acknowledgement":"We would like to thank the reviewers for their helpful comments and remarks.","language":[{"iso":"eng"}],"oa_version":"Published Version"},{"arxiv":1,"project":[{"call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"date_updated":"2025-09-09T12:54:51Z","status":"public","doi":"10.37236/11714","tmp":{"name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","image":"/image/cc_by_nd.png","short":"CC BY-ND (4.0)"},"article_type":"original","oa":1,"publisher":"Electronic Journal of Combinatorics","title":"Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets","quality_controlled":"1","abstract":[{"lang":"eng","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."}],"file":[{"date_created":"2023-09-15T08:02:09Z","relation":"main_file","creator":"dernst","access_level":"open_access","file_size":247917,"file_name":"2023_elecJournCombinatorics_Anastos.pdf","date_updated":"2023-09-15T08:02:09Z","success":1,"content_type":"application/pdf","file_id":"14338","checksum":"52c46c8cb329f9aaee9ade01525f317b"}],"publication_identifier":{"eissn":["1077-8926"]},"article_processing_charge":"Yes","day":"28","type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"Electronic Journal of Combinatorics","date_created":"2023-09-10T22:01:12Z","license":"https://creativecommons.org/licenses/by-nd/4.0/","date_published":"2023-07-28T00:00:00Z","_id":"14319","external_id":{"isi":["001042382200001"],"arxiv":["2212.03100"]},"year":"2023","file_date_updated":"2023-09-15T08:02:09Z","has_accepted_license":"1","ec_funded":1,"article_number":"P3.10","citation":{"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.","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>.","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>.","short":"M. Anastos, D. Fabian, A. Müyesser, T. Szabó, Electronic Journal of Combinatorics 30 (2023).","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>","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>"},"issue":"3","ddc":["510"],"intvolume":"        30","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).","isi":1,"publication_status":"published","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","full_name":"Anastos, Michael","last_name":"Anastos"},{"full_name":"Fabian, David","last_name":"Fabian","first_name":"David"},{"first_name":"Alp","full_name":"Müyesser, Alp","last_name":"Müyesser"},{"last_name":"Szabó","full_name":"Szabó, Tibor","first_name":"Tibor"}],"department":[{"_id":"MaKw"}],"volume":30,"month":"07","language":[{"iso":"eng"}],"oa_version":"Published Version"},{"day":"01","article_processing_charge":"No","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","_id":"14344","external_id":{"arxiv":["2111.14759"]},"date_published":"2023-01-01T00:00:00Z","date_created":"2023-09-17T22:01:10Z","year":"2023","status":"public","doi":"10.1137/1.9781611977554.ch88","date_updated":"2024-10-09T21:07:01Z","arxiv":1,"oa":1,"title":"Fast algorithms for solving the Hamilton cycle problem with high probability","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"}],"quality_controlled":"1","publisher":"Society for Industrial and Applied Mathematics","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2111.14759"}],"publication_identifier":{"isbn":["9781611977554"]},"scopus_import":"1","intvolume":"      2023","month":"01","volume":2023,"author":[{"full_name":"Anastos, Michael","last_name":"Anastos","first_name":"Michael","id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb"}],"department":[{"_id":"MaKw"}],"conference":{"end_date":"2023-01-25","location":"Florence, Italy","start_date":"2023-01-22","name":"SODA: Symposium on Discrete Algorithms"},"publication_status":"published","oa_version":"Preprint","page":"2286-2323","language":[{"iso":"eng"}],"citation":{"short":"M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 2286–2323.","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>","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>","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.","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>.","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.","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>."},"corr_author":"1"}]