--- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '23001' abstract: - lang: eng text: "A famous conjecture by Itai and Zehavi states that, for every \U0001D451\r\n-vertex-connected graph \U0001D43A\r\n and every vertex \U0001D45F\r\n in \U0001D43A\r\n, there are \U0001D451\r\n spanning trees of \U0001D43A\r\n such that, for every vertex \U0001D463\r\n in \U0001D43A ∖{\U0001D45F}\r\n, the paths between \U0001D45F\r\n and \U0001D463\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 \U0001D43A⁡(\U0001D45B,\U0001D45D)\r\n when \U0001D45B⁢\U0001D45D =\U0001D714⁡(log⁡\U0001D45B)\r\n and for random regular graphs \U0001D43A⁡(\U0001D45B,\U0001D451)\r\n when \U0001D451 =\U0001D714⁡(log⁡\U0001D45B)\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." 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." article_number: e70095 article_processing_charge: Yes (via OA deal) article_type: original arxiv: 1 author: - first_name: Lawrence full_name: Hollom, Lawrence last_name: Hollom - first_name: Lyuben full_name: Lichev, 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 - first_name: Yiting full_name: Wang, Yiting id: 1917d194-076e-11ed-97cd-837255f88785 last_name: Wang citation: 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 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 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. 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. 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. 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. short: L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Random Structures and Algorithms 69 (2026). das_tickbox: '0' date_created: 2026-09-27T22:01:52Z date_published: 2026-09-01T00:00:00Z date_updated: 2026-10-07T07:13:30Z day: '01' ddc: - '500' department: - _id: MaKw - _id: GradSch doi: 10.1002/rsa.70095 external_id: arxiv: - '2506.23970' file: - access_level: open_access checksum: 9a786460a47542f24576e947987e558a content_type: application/pdf creator: dernst date_created: 2026-10-07T07:10:43Z date_updated: 2026-10-07T07:10:43Z file_id: '23068' file_name: 2026_RandomStructAlgorithms_Hollom.pdf file_size: 457581 relation: main_file success: 1 file_date_updated: 2026-10-07T07:10:43Z fulldoi: https://doi.org/10.1002/rsa.70095 has_accepted_license: '1' intvolume: ' 69' issue: '2' language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics publication: Random Structures and Algorithms publication_identifier: eissn: - 1098-2418 issn: - 1042-9832 publication_status: published publisher: Wiley quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: yes title: Approximate Itai–Zehavi conjecture for random graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 69 year: '2026' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '23155' 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." 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." article_processing_charge: Yes (in subscription journal) article_type: original arxiv: 1 author: - first_name: Lawrence full_name: Hollom, Lawrence last_name: Hollom - first_name: Lyuben full_name: Lichev, 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 - first_name: Yiting full_name: Wang, Yiting id: 1917d194-076e-11ed-97cd-837255f88785 last_name: Wang citation: 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. 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. 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. 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. short: L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Annals of Applied Probability 36 (2026) 4716–4738. das_tickbox: '0' date_created: 2026-10-18T22:01:52Z date_published: 2026-10-01T00:00:00Z date_updated: 2026-10-19T07:39:17Z day: '01' ddc: - '500' department: - _id: MaKw - _id: GradSch doi: 10.1214/26-AAP2345 external_id: arxiv: - '2505.22875' file: - access_level: open_access checksum: 46101e61d29cf40f0a204801d15a848f content_type: application/pdf creator: dernst date_created: 2026-10-19T07:33:58Z date_updated: 2026-10-19T07:33:58Z file_id: '23165' file_name: 2026_AnnalsAppliedProbability_Hollom.pdf file_size: 320593 relation: main_file success: 1 file_date_updated: 2026-10-19T07:33:58Z fulldoi: https://doi.org/10.1214/26-AAP2345 has_accepted_license: '1' intvolume: ' 36' issue: '5' keyword: - Random regular graphs - coupling - contiguity - total variation distance - decomposition language: - iso: eng mathsc: - 05C80 month: '10' oa: 1 oa_version: Published Version page: 4716-4738 project: - _id: bd95085b-d553-11ed-ba76-e55d3349be45 grant_number: '101076777' name: Randomness and structure in combinatorics - _id: e19fef4c-1f3d-11f0-ac04-b8b1af6886d8 grant_number: E624 name: THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS publication: Annals of Applied Probability publication_identifier: eissn: - 2168-8737 issn: - 1050-5164 publication_status: published publisher: Institute of Mathematical Statistics quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Monotonicity and decompositions of random regular graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 36 year: '2026' ... --- OA_place: repository OA_type: green _id: '23158' 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. 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. article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Lawrence full_name: Hollom, Lawrence last_name: Hollom - first_name: Lyuben full_name: Lichev, 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 citation: 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 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 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. ieee: L. Hollom, L. Lichev, A. Mond, and J. Portier, “A note on high-dimensional discrepancy of subtrees,” Discrete and Computational Geometry. Springer, 2026. ista: Hollom L, Lichev L, Mond A, Portier J. 2026. A note on high-dimensional discrepancy of subtrees. Discrete and Computational Geometry. 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). das_tickbox: '1' dataavailabilitystatement: Data sharing not applicable to this article as no datasets were generated or analysed during the current study. date_created: 2026-10-18T22:01:53Z date_published: 2026-10-09T00:00:00Z date_updated: 2026-10-19T08:20:42Z day: '09' department: - _id: MaKw doi: 10.1007/s00454-025-00790-x external_id: arxiv: - '2412.04170' fulldoi: https://doi.org/10.1007/s00454-025-00790-x keyword: - Trees - High-dimensional discrepancy - Oriented discrepancy language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2412.04170 mathsc: - 05C05 - 05C35 - 11K38 month: '10' oa: 1 oa_version: Preprint project: - _id: e19fef4c-1f3d-11f0-ac04-b8b1af6886d8 grant_number: E624 name: THRESHOLDS IN SEMI-RANDOM PROCESSES AND GRAPH EMBEDDINGS publication: Discrete and Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: epub_ahead publisher: Springer quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: A note on high-dimensional discrepancy of subtrees type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2026' ... --- OA_place: publisher OA_type: hybrid _id: '19017' abstract: - lang: eng 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." article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Stefan full_name: Glock, Stefan last_name: Glock - first_name: Jaehoon full_name: Kim, Jaehoon last_name: Kim - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Oleg full_name: Pikhurko, Oleg last_name: Pikhurko - first_name: Shumin full_name: Sun, Shumin last_name: Sun citation: 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 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 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. 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. 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. 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. short: S. Glock, J. Kim, L. Lichev, O. Pikhurko, S. Sun, Canadian Journal of Mathematics (2025) 1–43. date_created: 2025-02-10T08:39:46Z date_published: 2025-01-06T00:00:00Z date_updated: 2025-09-30T10:28:07Z day: '06' ddc: - '500' department: - _id: MaKw doi: 10.4153/s0008414x25000021 external_id: arxiv: - '2403.04474' isi: - '001416788600001' fulldoi: https://doi.org/10.4153/s0008414x25000021 has_accepted_license: '1' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4153/s0008414x25000021 month: '01' oa: 1 oa_version: Published Version page: 1-43 publication: Canadian Journal of Mathematics publication_identifier: eissn: - 1496-4279 issn: - 0008-414X publication_status: epub_ahead publisher: Cambridge University Press quality_controlled: '1' scopus_import: '1' status: public title: On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7 tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 year: '2025' ... --- OA_place: repository OA_type: green _id: '19018' 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." acknowledgement: We are grateful to Dieter Mitsche for related discussions and to several anonymous referees for multiple useful comments. article_number: '104120' article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Sofiya full_name: Burova, Sofiya last_name: Burova - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev citation: 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 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. ieee: S. Burova and L. Lichev, “The semi-random tree process,” European Journal of Combinatorics, vol. 126. Elsevier, 2025. ista: Burova S, Lichev L. 2025. The semi-random tree process. European Journal of Combinatorics. 126, 104120. 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. short: S. Burova, L. Lichev, European Journal of Combinatorics 126 (2025). date_created: 2025-02-10T09:00:53Z date_published: 2025-05-01T00:00:00Z date_updated: 2025-09-30T10:28:42Z day: '01' department: - _id: MaKw doi: 10.1016/j.ejc.2025.104120 external_id: arxiv: - '2204.07376 ' isi: - '001420659400001' fulldoi: https://doi.org/10.1016/j.ejc.2025.104120 intvolume: ' 126' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2204.07376 month: '05' oa: 1 oa_version: Preprint publication: European Journal of Combinatorics publication_identifier: issn: - 0195-6698 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: The semi-random tree process type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 126 year: '2025' ... --- DOAJ_listed: '1' OA_place: publisher OA_type: gold _id: '19859' 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." 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." article_processing_charge: Yes article_type: original arxiv: 1 author: - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Bruno full_name: Schapira, Bruno last_name: Schapira citation: 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 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 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. 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. ista: Lichev L, Schapira B. 2025. Color-avoiding percolation on the Erdős–Rényi random graph. Annales Henri Lebesgue. 8, 35–65. 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. short: L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65. corr_author: '1' date_created: 2025-06-22T22:02:07Z date_published: 2025-06-01T00:00:00Z date_updated: 2025-06-23T12:01:36Z day: '01' ddc: - '510' department: - _id: MaKw doi: 10.5802/ahl.228 external_id: arxiv: - '2211.16086 ' file: - access_level: open_access checksum: cca22d171b7affa010d17f5e793b0045 content_type: application/pdf creator: dernst date_created: 2025-06-23T11:59:22Z date_updated: 2025-06-23T11:59:22Z file_id: '19875' file_name: 2025_AnnalesHenriLebesgue_Lichev.pdf file_size: 746588 relation: main_file success: 1 file_date_updated: 2025-06-23T11:59:22Z fulldoi: https://doi.org/10.5802/ahl.228 has_accepted_license: '1' intvolume: ' 8' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 35-65 publication: Annales Henri Lebesgue publication_identifier: eissn: - 2644-9463 publication_status: published publisher: École normale supérieure de Rennes quality_controlled: '1' scopus_import: '1' status: public title: Color-avoiding percolation on the Erdős–Rényi random graph tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8 year: '2025' ... --- OA_place: publisher OA_type: hybrid PlanS_conform: '1' _id: '19508' 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. 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). article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Luc full_name: Attia, Luc last_name: Attia - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Dieter full_name: Mitsche, Dieter last_name: Mitsche - first_name: Raimundo J full_name: Saona Urmeneta, Raimundo J id: BD1DF4C4-D767-11E9-B658-BC13E6697425 last_name: Saona Urmeneta orcid: 0000-0001-5103-038X - first_name: Bruno full_name: Ziliotto, Bruno last_name: Ziliotto citation: 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 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 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. 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. 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. short: L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic Games and Applications 15 (2025) 1517–1535. corr_author: '1' date_created: 2025-04-06T22:01:32Z date_published: 2025-11-01T00:00:00Z date_updated: 2026-09-16T07:00:33Z day: '01' ddc: - '000' department: - _id: MaKw - _id: KrCh doi: 10.1007/s13235-025-00636-4 ec_funded: 1 external_id: isi: - '001449708900001' file: - access_level: open_access checksum: b3a1b7eef40c9ac2acf3fef563081694 content_type: application/pdf creator: dernst date_created: 2025-12-30T08:13:04Z date_updated: 2025-12-30T08:13:04Z file_id: '20891' file_name: 2025_DynGamesAppl_Attia.pdf file_size: 570994 relation: main_file success: 1 file_date_updated: 2025-12-30T08:13:04Z fulldoi: https://doi.org/10.1007/s13235-025-00636-4 has_accepted_license: '1' intvolume: ' 15' isi: 1 language: - iso: eng month: '11' oa: 1 oa_version: Published Version page: 1517-1535 project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: Dynamic Games and Applications publication_identifier: eissn: - 2153-0793 issn: - 2153-0785 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '20234' relation: dissertation_contains status: public scopus_import: '1' status: public title: Random zero-sum dynamic games on infinite directed graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 15 year: '2025' ... --- DOAJ_listed: '1' OA_place: repository OA_type: gold _id: '18951' 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 article_type: original arxiv: 1 author: - first_name: Ivailo full_name: Hartarsky, Ivailo last_name: Hartarsky - first_name: Lyuben full_name: Lichev, Lyuben id: 9aa8388e-d003-11ee-8458-c4c1d7447977 last_name: Lichev - first_name: Fabio Lucio full_name: Toninelli, Fabio Lucio last_name: Toninelli citation: 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 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 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. 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. 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.” 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). das_tickbox: '1' date_created: 2025-01-29T10:57:09Z date_published: 2024-08-26T00:00:00Z date_updated: 2026-10-16T10:14:21Z day: '26' department: - _id: MaKw doi: 10.4171/aihpd/200 external_id: arxiv: - '2304.10930' fulldoi: https://doi.org/10.4171/aihpd/200 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2304.10930 mathsc: - 05B50 - 05C70 - 82C20 month: '08' oa: 1 oa_version: Preprint publication: Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions publication_identifier: eissn: - 2308-5835 issn: - 2308-5827 publication_status: epub_ahead publisher: EMS Press quality_controlled: '1' researchdata_availability: unclear scopus_import: '1' status: public supplementarymaterial: unclear title: Local dimer dynamics in higher dimensions type: journal_article user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 year: '2024' ...