[{"has_accepted_license":"1","publisher":"Wiley","department":[{"_id":"MaKw"},{"_id":"GradSch"}],"file_date_updated":"2026-10-07T07:10:43Z","article_processing_charge":"Yes (via OA deal)","abstract":[{"lang":"eng","text":"A famous conjecture by Itai and Zehavi states that, for every 𝑑\r\n-vertex-connected graph đș\r\n and every vertex 𝑟\r\n in đș\r\n, there are 𝑑\r\n spanning trees of đș\r\n such that, for every vertex 𝑣\r\n in đș ∖{𝑟}\r\n, the paths between 𝑟\r\n and 𝑣\r\n in different trees are internally vertex-disjoint. We show that with high probability the Itai–Zehavi conjecture holds asymptotically for the ErdƑs–RĂ©nyi random graph đș⁥(𝑛,𝑝)\r\n when 𝑛ⁱ𝑝 =𝜔⁡(log⁡𝑛)\r\n and for random regular graphs đș⁥(𝑛,𝑑)\r\n when 𝑑 =𝜔⁡(log⁡𝑛)\r\n. Moreover, we essentially confirm the conjecture up to a constant factor for sparser random regular graphs. This answers a question of Draganić and Krivelevich positively. Our proof makes use of recent developments on sprinkling techniques in random regular graphs."}],"ddc":["500"],"citation":{"chicago":"Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Approximate Itai–Zehavi Conjecture for Random Graphs.” Random Structures and Algorithms. Wiley, 2026. https://doi.org/10.1002/rsa.70095.","ama":"Hollom L, Lichev L, Mond A, Portier J, Wang Y. Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. 2026;69(2). doi:10.1002/rsa.70095","ieee":"L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Approximate Itai–Zehavi conjecture for random graphs,” Random Structures and Algorithms, vol. 69, no. 2. Wiley, 2026.","apa":"Hollom, L., Lichev, L., Mond, A., Portier, J., & Wang, Y. (2026). Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.70095","mla":"Hollom, Lawrence, et al. “Approximate Itai–Zehavi Conjecture for Random Graphs.” Random Structures and Algorithms, vol. 69, no. 2, e70095, Wiley, 2026, doi:10.1002/rsa.70095.","ista":"Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Approximate Itai–Zehavi conjecture for random graphs. Random Structures and Algorithms. 69(2), e70095.","short":"L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Random Structures and Algorithms 69 (2026)."},"doi":"10.1002/rsa.70095","intvolume":" 69","author":[{"last_name":"Hollom","first_name":"Lawrence","full_name":"Hollom, Lawrence"},{"last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","full_name":"Lichev, Lyuben","first_name":"Lyuben"},{"last_name":"Mond","first_name":"Adva","full_name":"Mond, Adva"},{"first_name":"Julien","full_name":"Portier, Julien","last_name":"Portier"},{"id":"1917d194-076e-11ed-97cd-837255f88785","last_name":"Wang","full_name":"Wang, Yiting","first_name":"Yiting"}],"supplementarymaterial":"yes","external_id":{"arxiv":["2506.23970"]},"quality_controlled":"1","status":"public","OA_place":"publisher","OA_type":"hybrid","date_created":"2026-09-27T22:01:52Z","das_tickbox":"0","date_updated":"2026-10-07T07:13:30Z","issue":"2","publication_status":"published","month":"09","project":[{"name":"Randomness and structure in combinatorics","grant_number":"101076777","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"}],"article_type":"original","arxiv":1,"year":"2026","_id":"23001","oa_version":"Published Version","language":[{"iso":"eng"}],"acknowledgement":"Hollom was supported by the Internal Graduate Studentship of Trinity College, Cambridge. Mond was supported by UK Research and Innovation grant MR/W007320/2. Wang was supported by the ERC Starting Grant “RANDSTRUCT” No. 101076777. Lichev was supported by the Austrian Science Fund (FWF) [10.55776/ESP624]. For open access purposes, the authors have applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. Open Access funding provided by Technische Universitat Wien.\r\n\r\nPart of this research was done during a visit of the fourth author to IST Austria. We thank IST Austria for its hospitality. We also thank the anonymous referees for their comments and suggestions. Open Access funding provided by Technische Universitat Wien. This work was supported by the European Research Council, UK Research and Innovation, the Austrian Science Fund, and Trinity College.","PlanS_conform":"1","volume":69,"file":[{"file_id":"23068","date_updated":"2026-10-07T07:10:43Z","relation":"main_file","file_name":"2026_RandomStructAlgorithms_Hollom.pdf","creator":"dernst","file_size":457581,"content_type":"application/pdf","access_level":"open_access","checksum":"9a786460a47542f24576e947987e558a","success":1,"date_created":"2026-10-07T07:10:43Z"}],"type":"journal_article","publication":"Random Structures and Algorithms","researchdata_availability":"no","article_number":"e70095","title":"Approximate Itai–Zehavi conjecture for random graphs","day":"01","date_published":"2026-09-01T00:00:00Z","fulldoi":"https://doi.org/10.1002/rsa.70095","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["1042-9832"],"eissn":["1098-2418"]},"scopus_import":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"}},{"external_id":{"arxiv":["2505.22875"]},"supplementarymaterial":"no","quality_controlled":"1","status":"public","OA_place":"publisher","OA_type":"hybrid","das_tickbox":"0","date_created":"2026-10-18T22:01:52Z","date_updated":"2026-10-19T07:39:17Z","issue":"5","publication_status":"published","month":"10","project":[{"grant_number":"101076777","name":"Randomness and structure in combinatorics","_id":"bd95085b-d553-11ed-ba76-e55d3349be45"},{"grant_number":"E624","name":"THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS","_id":"e19fef4c-1f3d-11f0-ac04-b8b1af6886d8"}],"has_accepted_license":"1","publisher":"Institute of Mathematical Statistics","file_date_updated":"2026-10-19T07:33:58Z","department":[{"_id":"MaKw"},{"_id":"GradSch"}],"mathsc":["05C80"],"abstract":[{"lang":"eng","text":"In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we\r\nshow that, for a wide range of parameters d1 ≀ d2, there exists a coupling of\r\nG(n,d1) and G(n,d2) satisfying that G(n,d1) ⊆ G(n,d2) with high probability, confirming a conjecture of Gao, Isaev and McKay in a new regime.\r\nOur contributions include new tools for analysing contiguity and total variation distance between random regular graph models, a novel procedure for\r\ngenerating unions of random edge-disjoint perfect matchings, and refined estimates of Gao’s bounds on the number of perfect matchings in random regular graphs. In addition, we make progress towards another conjecture of Isaev,\r\nMcKay, Southwell and Zhukovskii."}],"article_processing_charge":"Yes (in subscription journal)","citation":{"short":"L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Annals of Applied Probability 36 (2026) 4716–4738.","ista":"Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. 36(5), 4716–4738.","ieee":"L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Monotonicity and decompositions of random regular graphs,” Annals of Applied Probability, vol. 36, no. 5. Institute of Mathematical Statistics, pp. 4716–4738, 2026.","ama":"Hollom L, Lichev L, Mond A, Portier J, Wang Y. Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. 2026;36(5):4716-4738. doi:10.1214/26-AAP2345","apa":"Hollom, L., Lichev, L., Mond, A., Portier, J., & Wang, Y. (2026). Monotonicity and decompositions of random regular graphs. Annals of Applied Probability. Institute of Mathematical Statistics. https://doi.org/10.1214/26-AAP2345","chicago":"Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting Wang. “Monotonicity and Decompositions of Random Regular Graphs.” Annals of Applied Probability. Institute of Mathematical Statistics, 2026. https://doi.org/10.1214/26-AAP2345.","mla":"Hollom, Lawrence, et al. “Monotonicity and Decompositions of Random Regular Graphs.” Annals of Applied Probability, vol. 36, no. 5, Institute of Mathematical Statistics, 2026, pp. 4716–38, doi:10.1214/26-AAP2345."},"ddc":["500"],"doi":"10.1214/26-AAP2345","intvolume":" 36","author":[{"last_name":"Hollom","full_name":"Hollom, Lawrence","first_name":"Lawrence"},{"full_name":"Lichev, Lyuben","first_name":"Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","last_name":"Lichev"},{"first_name":"Adva","full_name":"Mond, Adva","last_name":"Mond"},{"first_name":"Julien","full_name":"Portier, Julien","last_name":"Portier"},{"id":"1917d194-076e-11ed-97cd-837255f88785","last_name":"Wang","first_name":"Yiting","full_name":"Wang, Yiting"}],"publication":"Annals of Applied Probability","researchdata_availability":"no","title":"Monotonicity and decompositions of random regular graphs","day":"01","date_published":"2026-10-01T00:00:00Z","fulldoi":"https://doi.org/10.1214/26-AAP2345","oa":1,"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["1050-5164"],"eissn":["2168-8737"]},"page":"4716-4738","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"keyword":["Random regular graphs","coupling","contiguity","total variation distance","decomposition"],"article_type":"original","year":"2026","arxiv":1,"oa_version":"Published Version","_id":"23155","language":[{"iso":"eng"}],"acknowledgement":"We are grateful to BĂ©la BollobĂĄs, to Matthew Kwan and to Fabio\r\nToninelli for their helpful comments and suggestions, and to Nicholas Wormald for useful\r\nremarks on a preliminary version of this work and pointing us towards the reference [29].\r\nThe authors would also like to thank several anonymous referees for many useful suggestions,\r\nincluding pointing out that Lemma 2.10 already appeared in [11].\r\nPart of this research was done during a visit of the fourth author to IST Austria. We thank\r\nIST Austria for its hospitality.\r\nFor open access purposes, the authors have applied a CC BY public copyright license to\r\nany author accepted manuscript version arising from this submission. L. Hollom was supported by the Internal Graduate Studentship of Trinity College, Cambridge.\r\nL. Lichev was supported by the Austrian Science Fund (FWF) grant No. 10.55776/ESP624.\r\nA. Mond was supported by UK Research and Innovation grant MR/W007320/2. Wang was\r\nsupported by the ERC Starting Grant “RANDSTRUCT” No. 101076777.","PlanS_conform":"1","volume":36,"file":[{"file_size":320593,"creator":"dernst","access_level":"open_access","checksum":"46101e61d29cf40f0a204801d15a848f","content_type":"application/pdf","date_updated":"2026-10-19T07:33:58Z","file_id":"23165","relation":"main_file","file_name":"2026_AnnalsAppliedProbability_Hollom.pdf","date_created":"2026-10-19T07:33:58Z","success":1}],"type":"journal_article"},{"citation":{"apa":"Hollom, L., Lichev, L., Mond, A., & Portier, J. (2026). A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. Springer. https://doi.org/10.1007/s00454-025-00790-x","ieee":"L. Hollom, L. Lichev, A. Mond, and J. Portier, “A note on high-dimensional discrepancy of subtrees,” Discrete and Computational Geometry. Springer, 2026.","ama":"Hollom L, Lichev L, Mond A, Portier J. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. 2026. doi:10.1007/s00454-025-00790-x","chicago":"Hollom, Lawrence, Lyuben Lichev, Adva Mond, and Julien Portier. “A Note on High-Dimensional Discrepancy of Subtrees.” Discrete and Computational Geometry. Springer, 2026. https://doi.org/10.1007/s00454-025-00790-x.","mla":"Hollom, Lawrence, et al. “A Note on High-Dimensional Discrepancy of Subtrees.” Discrete and Computational Geometry, Springer, 2026, doi:10.1007/s00454-025-00790-x.","short":"L. Hollom, L. Lichev, A. Mond, J. Portier, Discrete and Computational Geometry (2026).","ista":"Hollom L, Lichev L, Mond A, Portier J. 2026. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry."},"doi":"10.1007/s00454-025-00790-x","author":[{"first_name":"Lawrence","full_name":"Hollom, Lawrence","last_name":"Hollom"},{"first_name":"Lyuben","full_name":"Lichev, Lyuben","last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977"},{"first_name":"Adva","full_name":"Mond, Adva","last_name":"Mond"},{"first_name":"Julien","full_name":"Portier, Julien","last_name":"Portier"}],"publisher":"Springer","mathsc":["05C05","05C35","11K38"],"department":[{"_id":"MaKw"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.04170"}],"abstract":[{"lang":"eng","text":"For a tree T and a function f:E(T)→Sd, the imbalance of a subtree Tâ€Č⊆T is given by |∑e∈E(Tâ€Č)f(e)|. The d-dimensional discrepancy of the tree T is the minimum, over all functions f as above, of the maximum imbalance of a subtree of T. We prove tight asymptotic bounds for the discrepancy of a tree T, confirming a conjecture of Krishna, Michaeli, Sarantis, Wang and Wang. We also settle a related conjecture on oriented discrepancy of subtrees by the same authors."}],"article_processing_charge":"No","date_updated":"2026-10-19T08:20:42Z","publication_status":"epub_ahead","month":"10","project":[{"name":"THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS","grant_number":"E624","_id":"e19fef4c-1f3d-11f0-ac04-b8b1af6886d8"}],"supplementarymaterial":"no","external_id":{"arxiv":["2412.04170"]},"quality_controlled":"1","OA_place":"repository","status":"public","OA_type":"green","date_created":"2026-10-18T22:01:53Z","das_tickbox":"1","language":[{"iso":"eng"}],"dataavailabilitystatement":"Data sharing not applicable to this article as no datasets were generated or analysed during the current study.","acknowledgement":"The authors would like to thank both BĂ©la BollobĂĄs and the anonymous reviewer for their careful readings of the manuscript and for their valuable comments. The first author was funded by Trinity College, Cambridge. The second author was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/ESP624. The third author was supported by UK Research and Innovation grant MR/W007320/2. The fourth author was funded by EPSRC (Engineering and Physical Sciences Research Council) and by the Cambridge Commonwealth, European and International Trust.","type":"journal_article","keyword":["Trees","High-dimensional discrepancy","Oriented discrepancy"],"article_type":"original","year":"2026","arxiv":1,"_id":"23158","oa_version":"Preprint","date_published":"2026-10-09T00:00:00Z","fulldoi":"https://doi.org/10.1007/s00454-025-00790-x","oa":1,"scopus_import":"1","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","researchdata_availability":"no","publication":"Discrete and Computational Geometry","title":"A note on high-dimensional discrepancy of subtrees","day":"09"},{"date_updated":"2025-09-30T10:28:07Z","publication_status":"epub_ahead","month":"01","external_id":{"isi":["001416788600001"],"arxiv":["2403.04474"]},"quality_controlled":"1","OA_place":"publisher","status":"public","date_created":"2025-02-10T08:39:46Z","OA_type":"hybrid","ddc":["500"],"citation":{"ista":"Glock S, Kim J, Lichev L, Pikhurko O, Sun S. 2025. On the (k + 2, k)-problem of Brown, ErdƑs, and SĂłs for k = 5,6,7. Canadian Journal of Mathematics., 1–43.","short":"S. Glock, J. Kim, L. Lichev, O. Pikhurko, S. Sun, Canadian Journal of Mathematics (2025) 1–43.","mla":"Glock, Stefan, et al. “On the (k + 2, k)-Problem of Brown, ErdƑs, and SĂłs for k = 5,6,7.” Canadian Journal of Mathematics, Cambridge University Press, 2025, pp. 1–43, doi:10.4153/s0008414x25000021.","apa":"Glock, S., Kim, J., Lichev, L., Pikhurko, O., & Sun, S. (2025). On the (k + 2, k)-problem of Brown, ErdƑs, and SĂłs for k = 5,6,7. Canadian Journal of Mathematics. Cambridge University Press. https://doi.org/10.4153/s0008414x25000021","ieee":"S. Glock, J. Kim, L. Lichev, O. Pikhurko, and S. Sun, “On the (k + 2, k)-problem of Brown, ErdƑs, and SĂłs for k = 5,6,7,” Canadian Journal of Mathematics. Cambridge University Press, pp. 1–43, 2025.","ama":"Glock S, Kim J, Lichev L, Pikhurko O, Sun S. On the (k + 2, k)-problem of Brown, ErdƑs, and SĂłs for k = 5,6,7. Canadian Journal of Mathematics. 2025:1-43. doi:10.4153/s0008414x25000021","chicago":"Glock, Stefan, Jaehoon Kim, Lyuben Lichev, Oleg Pikhurko, and Shumin Sun. “On the (k + 2, k)-Problem of Brown, ErdƑs, and SĂłs for k = 5,6,7.” Canadian Journal of Mathematics. Cambridge University Press, 2025. https://doi.org/10.4153/s0008414x25000021."},"doi":"10.4153/s0008414x25000021","author":[{"last_name":"Glock","first_name":"Stefan","full_name":"Glock, Stefan"},{"full_name":"Kim, Jaehoon","first_name":"Jaehoon","last_name":"Kim"},{"id":"9aa8388e-d003-11ee-8458-c4c1d7447977","last_name":"Lichev","full_name":"Lichev, Lyuben","first_name":"Lyuben"},{"last_name":"Pikhurko","first_name":"Oleg","full_name":"Pikhurko, Oleg"},{"first_name":"Shumin","full_name":"Sun, Shumin","last_name":"Sun"}],"publisher":"Cambridge University Press","has_accepted_license":"1","department":[{"_id":"MaKw"}],"abstract":[{"text":"Let f(r)(n;s,k) denote the maximum number of edges in an n-vertex r-uniform hypergraph containing no subgraph with k edges and at most s vertices. Brown, ErdƑs and SĂłs [New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan 1971), pp. 53--63, Academic Press 1973] conjectured that the limit limn→∞n−2f(3)(n;k+2,k) exists for all k. The value of the limit was previously determined for k=2 in the original paper of Brown, ErdƑs and SĂłs, for k=3 by Glock [Bull. Lond. Math. Soc. 51 (2019) 230--236] and for k=4 by Glock, Joos, Kim, KĂŒhn, Lichev and Pikhurko [arXiv:2209.14177, accepted by Proc. Amer. Math. Soc.] while Delcourt and Postle [arXiv:2210.01105, accepted by Proc. Amer. Math. Soc.] proved the conjecture (without determining the limiting value).\r\nIn this paper, we determine the value of the limit in the Brown-ErdƑs-SĂłs Problem for k∈{5,6,7}. More generally, we obtain the value of limn→∞n−2f(r)(n;rk−2k+2,k) for all r≄3 and k∈{5,6,7}. In addition, by combining these new values with recent results of Bennett, Cushman and Dudek [arXiv:2309.00182] we obtain new asymptotic values for several generalised Ramsey numbers.","lang":"eng"}],"main_file_link":[{"url":"https://doi.org/10.4153/s0008414x25000021","open_access":"1"}],"article_processing_charge":"No","fulldoi":"https://doi.org/10.4153/s0008414x25000021","date_published":"2025-01-06T00:00:00Z","oa":1,"isi":1,"scopus_import":"1","publication_identifier":{"issn":["0008-414X"],"eissn":["1496-4279"]},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"page":"1-43","publication":"Canadian Journal of Mathematics","title":"On the (k + 2, k)-problem of Brown, ErdƑs, and SĂłs for k = 5,6,7","day":"06","language":[{"iso":"eng"}],"type":"journal_article","article_type":"original","_id":"19017","oa_version":"Published Version","year":"2025","arxiv":1},{"publisher":"Elsevier","department":[{"_id":"MaKw"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2204.07376"}],"article_processing_charge":"No","abstract":[{"lang":"eng","text":"The online semi-random graph process is a one-player game which starts with the empty graph on n vertices. At every round, a player (called Builder) is presented with a vertex v chosen uniformly at random and independently from previous rounds, and constructs an edge of their choice that is incident to v. Inspired by recent advances on the semi-random graph process, we define a family of generalized online semi-random models.\r\nWe analyse a particular instance that shares similar features with the original semi-random graph process and determine the hitting times of the classical graph properties minimum degree k,k-connectivity, containment of a perfect matching, a Hamiltonian cycle and an \r\nH-factor for a fixed graph H possessing an additional tree-like property. Along the way, we derive a few consequences of the famous Aldous-Broder algorithm that may be of independent interest."}],"citation":{"mla":"Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European Journal of Combinatorics, vol. 126, 104120, Elsevier, 2025, doi:10.1016/j.ejc.2025.104120.","chicago":"Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104120.","ama":"Burova S, Lichev L. The semi-random tree process. European Journal of Combinatorics. 2025;126. doi:10.1016/j.ejc.2025.104120","apa":"Burova, S., & Lichev, L. (2025). The semi-random tree process. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104120","ieee":"S. Burova and L. Lichev, “The semi-random tree process,” European Journal of Combinatorics, vol. 126. Elsevier, 2025.","short":"S. Burova, L. Lichev, European Journal of Combinatorics 126 (2025).","ista":"Burova S, Lichev L. 2025. The semi-random tree process. European Journal of Combinatorics. 126, 104120."},"intvolume":" 126","doi":"10.1016/j.ejc.2025.104120","author":[{"first_name":"Sofiya","full_name":"Burova, Sofiya","last_name":"Burova"},{"full_name":"Lichev, Lyuben","first_name":"Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","last_name":"Lichev"}],"external_id":{"arxiv":["2204.07376 "],"isi":["001420659400001"]},"quality_controlled":"1","OA_place":"repository","status":"public","date_created":"2025-02-10T09:00:53Z","OA_type":"green","date_updated":"2025-09-30T10:28:42Z","publication_status":"published","month":"05","article_type":"original","oa_version":"Preprint","_id":"19018","year":"2025","arxiv":1,"language":[{"iso":"eng"}],"acknowledgement":"We are grateful to Dieter Mitsche for related discussions and to several anonymous referees for multiple useful comments.","volume":126,"type":"journal_article","publication":"European Journal of Combinatorics","title":"The semi-random tree process","article_number":"104120","day":"01","fulldoi":"https://doi.org/10.1016/j.ejc.2025.104120","date_published":"2025-05-01T00:00:00Z","oa":1,"isi":1,"publication_identifier":{"issn":["0195-6698"]},"scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"month":"06","date_updated":"2025-06-23T12:01:36Z","publication_status":"published","status":"public","OA_place":"publisher","OA_type":"gold","date_created":"2025-06-22T22:02:07Z","external_id":{"arxiv":["2211.16086 "]},"quality_controlled":"1","doi":"10.5802/ahl.228","intvolume":" 8","author":[{"id":"9aa8388e-d003-11ee-8458-c4c1d7447977","last_name":"Lichev","first_name":"Lyuben","full_name":"Lichev, Lyuben"},{"last_name":"Schapira","full_name":"Schapira, Bruno","first_name":"Bruno"}],"ddc":["510"],"citation":{"chicago":"Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the ErdƑs–RĂ©nyi Random Graph.” Annales Henri Lebesgue. École normale supĂ©rieure de Rennes, 2025. https://doi.org/10.5802/ahl.228.","apa":"Lichev, L., & Schapira, B. (2025). Color-avoiding percolation on the ErdƑs–RĂ©nyi random graph. Annales Henri Lebesgue. École normale supĂ©rieure de Rennes. https://doi.org/10.5802/ahl.228","ieee":"L. Lichev and B. Schapira, “Color-avoiding percolation on the ErdƑs–RĂ©nyi random graph,” Annales Henri Lebesgue, vol. 8. École normale supĂ©rieure de Rennes, pp. 35–65, 2025.","ama":"Lichev L, Schapira B. Color-avoiding percolation on the ErdƑs–RĂ©nyi random graph. Annales Henri Lebesgue. 2025;8:35-65. doi:10.5802/ahl.228","mla":"Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the ErdƑs–RĂ©nyi Random Graph.” Annales Henri Lebesgue, vol. 8, École normale supĂ©rieure de Rennes, 2025, pp. 35–65, doi:10.5802/ahl.228.","ista":"Lichev L, Schapira B. 2025. Color-avoiding percolation on the ErdƑs–RĂ©nyi random graph. Annales Henri Lebesgue. 8, 35–65.","short":"L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65."},"file_date_updated":"2025-06-23T11:59:22Z","department":[{"_id":"MaKw"}],"article_processing_charge":"Yes","abstract":[{"lang":"eng","text":"We consider a recently introduced model of color-avoiding percolation (abbreviated CA-percolation) defined as follows. Every edge in a graph G is colored in some of k>=2 colors. Two vertices u and v in G are said to be CA-connected if u and v may be connected using any subset of k-1 colors. CA-connectivity defines an equivalence relation on the vertex set of G whose classes are called CA-components.\r\nWe study the component structure of a randomly colored ErdƑs–RĂ©nyi random graph of constant average degree. We distinguish three regimes for the size of the largest component: a supercritical regime, a so-called intermediate regime, and a subcritical regime, in which the largest CA-component has respectively linear, logarithmic, and bounded size. Interestingly, in the subcritical regime, the bound is deterministic and given by the number of colors."}],"has_accepted_license":"1","publisher":"École normale supĂ©rieure de Rennes","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","publication_identifier":{"eissn":["2644-9463"]},"page":"35-65","corr_author":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"date_published":"2025-06-01T00:00:00Z","fulldoi":"https://doi.org/10.5802/ahl.228","oa":1,"title":"Color-avoiding percolation on the ErdƑs–RĂ©nyi random graph","day":"01","publication":"Annales Henri Lebesgue","volume":8,"DOAJ_listed":"1","file":[{"date_created":"2025-06-23T11:59:22Z","success":1,"creator":"dernst","file_size":746588,"content_type":"application/pdf","checksum":"cca22d171b7affa010d17f5e793b0045","access_level":"open_access","file_id":"19875","date_updated":"2025-06-23T11:59:22Z","file_name":"2025_AnnalesHenriLebesgue_Lichev.pdf","relation":"main_file"}],"type":"journal_article","language":[{"iso":"eng"}],"acknowledgement":"We thank Dieter Mitsche for enlightening discussions, BalĂĄzs RĂĄth for a number of comments\r\nand corrections on a first version of this paper, and an anonymous referee for several useful remarks.","arxiv":1,"year":"2025","oa_version":"Published Version","_id":"19859","article_type":"original"},{"doi":"10.1007/s13235-025-00636-4","intvolume":" 15","author":[{"full_name":"Attia, Luc","first_name":"Luc","last_name":"Attia"},{"last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","first_name":"Lyuben","full_name":"Lichev, Lyuben"},{"full_name":"Mitsche, Dieter","first_name":"Dieter","last_name":"Mitsche"},{"orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J"},{"full_name":"Ziliotto, Bruno","first_name":"Bruno","last_name":"Ziliotto"}],"citation":{"short":"L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic Games and Applications 15 (2025) 1517–1535.","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.” Dynamic Games and Applications, vol. 15, Springer Nature, 2025, pp. 1517–35, doi:10.1007/s13235-025-00636-4.","chicago":"Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” Dynamic Games and Applications. Springer Nature, 2025. https://doi.org/10.1007/s13235-025-00636-4.","apa":"Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., & Ziliotto, B. (2025). Random zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications. Springer Nature. https://doi.org/10.1007/s13235-025-00636-4","ieee":"L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Random zero-sum dynamic games on infinite directed graphs,” Dynamic Games and Applications, vol. 15. Springer Nature, pp. 1517–1535, 2025.","ama":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Random zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications. 2025;15:1517-1535. doi:10.1007/s13235-025-00636-4"},"ddc":["000"],"department":[{"_id":"MaKw"},{"_id":"KrCh"}],"file_date_updated":"2025-12-30T08:13:04Z","abstract":[{"lang":"eng","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."}],"article_processing_charge":"Yes (via OA deal)","publisher":"Springer Nature","has_accepted_license":"1","month":"11","ec_funded":1,"project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"date_updated":"2026-09-16T07:00:33Z","publication_status":"published","status":"public","OA_place":"publisher","OA_type":"hybrid","date_created":"2025-04-06T22:01:32Z","external_id":{"isi":["001449708900001"]},"quality_controlled":"1","volume":15,"file":[{"success":1,"date_created":"2025-12-30T08:13:04Z","relation":"main_file","file_name":"2025_DynGamesAppl_Attia.pdf","file_id":"20891","date_updated":"2025-12-30T08:13:04Z","content_type":"application/pdf","access_level":"open_access","checksum":"b3a1b7eef40c9ac2acf3fef563081694","creator":"dernst","file_size":570994}],"type":"journal_article","language":[{"iso":"eng"}],"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).","PlanS_conform":"1","year":"2025","_id":"19508","oa_version":"Published Version","article_type":"original","scopus_import":"1","publication_identifier":{"issn":["2153-0785"],"eissn":["2153-0793"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"20234"}]},"page":"1517-1535","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"date_published":"2025-11-01T00:00:00Z","fulldoi":"https://doi.org/10.1007/s13235-025-00636-4","isi":1,"oa":1,"title":"Random zero-sum dynamic games on infinite directed graphs","day":"01","publication":"Dynamic Games and Applications"},{"date_published":"2024-08-26T00:00:00Z","fulldoi":"https://doi.org/10.4171/aihpd/200","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_identifier":{"eissn":["2308-5835"],"issn":["2308-5827"]},"scopus_import":"1","researchdata_availability":"unclear","publication":"Annales de l’Institut Henri PoincarĂ© D, Combinatorics, Physics and their Interactions","title":"Local dimer dynamics in higher dimensions","day":"26","language":[{"iso":"eng"}],"DOAJ_listed":"1","type":"journal_article","article_type":"original","arxiv":1,"year":"2024","oa_version":"Preprint","_id":"18951","date_updated":"2026-10-16T10:14:21Z","publication_status":"epub_ahead","month":"08","external_id":{"arxiv":["2304.10930"]},"supplementarymaterial":"unclear","quality_controlled":"1","status":"public","OA_place":"repository","OA_type":"gold","das_tickbox":"1","date_created":"2025-01-29T10:57:09Z","citation":{"apa":"Hartarsky, I., Lichev, L., & Toninelli, F. L. (2024). Local dimer dynamics in higher dimensions. Annales de l’Institut Henri PoincarĂ© D, Combinatorics, Physics and Their Interactions. EMS Press. https://doi.org/10.4171/aihpd/200","ama":"Hartarsky I, Lichev L, Toninelli FL. Local dimer dynamics in higher dimensions. Annales de l’Institut Henri PoincarĂ© D, Combinatorics, Physics and their Interactions. 2024. doi:10.4171/aihpd/200","ieee":"I. Hartarsky, L. Lichev, and F. L. Toninelli, “Local dimer dynamics in higher dimensions,” Annales de l’Institut Henri PoincarĂ© D, Combinatorics, Physics and their Interactions. EMS Press, 2024.","chicago":"Hartarsky, Ivailo, Lyuben Lichev, and Fabio Lucio Toninelli. “Local Dimer Dynamics in Higher Dimensions.” Annales de l’Institut Henri PoincarĂ© D, Combinatorics, Physics and Their Interactions. EMS Press, 2024. https://doi.org/10.4171/aihpd/200.","mla":"Hartarsky, Ivailo, et al. “Local Dimer Dynamics in Higher Dimensions.” Annales de l’Institut Henri PoincarĂ© D, Combinatorics, Physics and Their Interactions, EMS Press, 2024, doi:10.4171/aihpd/200.","short":"I. Hartarsky, L. Lichev, F.L. Toninelli, Annales de l’Institut Henri PoincarĂ© D, Combinatorics, Physics and Their Interactions (2024).","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."},"doi":"10.4171/aihpd/200","author":[{"last_name":"Hartarsky","first_name":"Ivailo","full_name":"Hartarsky, Ivailo"},{"last_name":"Lichev","id":"9aa8388e-d003-11ee-8458-c4c1d7447977","first_name":"Lyuben","full_name":"Lichev, Lyuben"},{"first_name":"Fabio Lucio","full_name":"Toninelli, Fabio Lucio","last_name":"Toninelli"}],"publisher":"EMS Press","mathsc":["05B50","05C70","82C20"],"department":[{"_id":"MaKw"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2304.10930"}],"abstract":[{"lang":"eng","text":"We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes [n] \r\nd . These consist of successively switching the dimers along alternating cycles of prescribed (small) lengths. We study the connectivity properties of the dimer configuration space equipped with these transitions. Answering a question of Freire, Klivans, Milet, and Saldanha, we show that in three dimensions any configuration admits an alternating cycle of length at most 6. We further establish that any configuration on [n] d features order n d−2 alternating cycles of length at most 4d−2. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension d is ergodic when switching alternating cycles of length at most 4d−4. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped boxes in the triangular lattice are ergodic for switching alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon and RĂ©mila, which also uses 8-cycles. None of our proofs make reference to height functions."}],"article_processing_charge":"Yes"}]