@article{23001, abstract = {A famous conjecture by Itai and Zehavi states that, for every 𝑑 -vertex-connected graph 𝐺 and every vertex 𝑟 in 𝐺 , there are 𝑑 spanning trees of 𝐺 such that, for every vertex 𝑣 in 𝐺 ∖{𝑟} , the paths between 𝑟 and 𝑣 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 𝐺⁡(𝑛,𝑝) when 𝑛⁢𝑝 =𝜔⁡(log⁡𝑛) and for random regular graphs 𝐺⁡(𝑛,𝑑) when 𝑑 =𝜔⁡(log⁡𝑛) . 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.}, author = {Hollom, Lawrence and Lichev, Lyuben and Mond, Adva and Portier, Julien and Wang, Yiting}, issn = {1098-2418}, journal = {Random Structures and Algorithms}, number = {2}, publisher = {Wiley}, title = {{Approximate Itai–Zehavi conjecture for random graphs}}, doi = {10.1002/rsa.70095}, volume = {69}, year = {2026}, } @article{23155, abstract = {In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters d1 ≤ d2, there exists a coupling of G(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. Our contributions include new tools for analysing contiguity and total variation distance between random regular graph models, a novel procedure for generating 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, McKay, Southwell and Zhukovskii.}, author = {Hollom, Lawrence and Lichev, Lyuben and Mond, Adva and Portier, Julien and Wang, Yiting}, issn = {2168-8737}, journal = {Annals of Applied Probability}, keywords = {Random regular graphs, coupling, contiguity, total variation distance, decomposition}, number = {5}, pages = {4716--4738}, publisher = {Institute of Mathematical Statistics}, title = {{Monotonicity and decompositions of random regular graphs}}, doi = {10.1214/26-AAP2345}, volume = {36}, year = {2026}, } @article{23158, abstract = {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.}, author = {Hollom, Lawrence and Lichev, Lyuben and Mond, Adva and Portier, Julien}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, keywords = {Trees, High-dimensional discrepancy, Oriented discrepancy}, publisher = {Springer}, title = {{A note on high-dimensional discrepancy of subtrees}}, doi = {10.1007/s00454-025-00790-x}, year = {2026}, } @article{19017, abstract = {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). In 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.}, author = {Glock, Stefan and Kim, Jaehoon and Lichev, Lyuben and Pikhurko, Oleg and Sun, Shumin}, issn = {1496-4279}, journal = {Canadian Journal of Mathematics}, pages = {1--43}, publisher = {Cambridge University Press}, title = {{On the (k + 2, k)-problem of Brown, Erdős, and Sós for k = 5,6,7}}, doi = {10.4153/s0008414x25000021}, year = {2025}, } @article{19018, abstract = {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. We 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 H-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.}, author = {Burova, Sofiya and Lichev, Lyuben}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{The semi-random tree process}}, doi = {10.1016/j.ejc.2025.104120}, volume = {126}, year = {2025}, } @article{19859, abstract = {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. We 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.}, author = {Lichev, Lyuben and Schapira, Bruno}, issn = {2644-9463}, journal = {Annales Henri Lebesgue}, pages = {35--65}, publisher = {École normale supérieure de Rennes}, title = {{Color-avoiding percolation on the Erdős–Rényi random graph}}, doi = {10.5802/ahl.228}, volume = {8}, year = {2025}, } @article{19508, abstract = {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.}, author = {Attia, Luc and Lichev, Lyuben and Mitsche, Dieter and Saona Urmeneta, Raimundo J and Ziliotto, Bruno}, issn = {2153-0793}, journal = {Dynamic Games and Applications}, pages = {1517--1535}, publisher = {Springer Nature}, title = {{Random zero-sum dynamic games on infinite directed graphs}}, doi = {10.1007/s13235-025-00636-4}, volume = {15}, year = {2025}, } @article{18951, abstract = {We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes [n] d . 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.}, author = {Hartarsky, Ivailo and Lichev, Lyuben and Toninelli, Fabio Lucio}, issn = {2308-5835}, journal = {Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions}, publisher = {EMS Press}, title = {{Local dimer dynamics in higher dimensions}}, doi = {10.4171/aihpd/200}, year = {2024}, }