A central challenge in network design is ensuring resilience: how can we guarantee multiple, independent, communication pathways between nodes, even when some connections fail in a network? In 1989, Zehavi and Itai formulated a graph-theoretic conjecture that captures the essence of this problem. They proposed that any \(k\)-vertex-connected graph contains \(k\) independent spanning trees rooted at any given root \(r\), which means that for every vertex \(v\) in the graph, the unique \(r-v\) paths within these \(k\) spanning trees are entirely disjoint, apart from their endpoints \(r\) and \(v\). Despite decades of effort, this conjecture has only been proven for \(k \le 4\) and for specific graph families using their underlying topological structure, leaving the general case as an open problem in graph theory with substantial consequences in the field of distributed algorithms.

Abstract. We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong [Formula: see text]-regular expander graph [Formula: see text] with [Formula: see text] vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths [Formula: see text] in [Formula: see text] and fulfills any series of two types of requests: (1) Given two vertices [Formula: see text] and [Formula: see text] such that each appears as an endpoint in [Formula: see text] paths in [Formula: see text] and, additionally, [Formula: see text], the algorithm finds a path of length at most [Formula: see text] connecting [Formula: see text] and [Formula: see text] which is edge-disjoint from all other paths in [Formula: see text], and adds it to [Formula: see text]. (2) Remove a given path [Formula: see text] from [Formula: see text]. Importantly, each request is processed before seeing the next one. The upper bound on the length of found paths and the constraints are the best possible up to a constant factor. This establishes the first online algorithm for finding edge-disjoint paths in expanders which also allows removals, significantly strengthening a long list of previous results on the topic. We obtain the same result in the case [Formula: see text] is directed.

It is a classical result that a random permutation of n elements has, on average, about log n cycles. We generalise this fact to all directed d-regular graphs on n vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt {\log d} )$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1 + {\mathcal{O}}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong d-regular expander graph G with n vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths P in G and fulfills any series of two types of requests:

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. This proves to be a powerful tool for embedding graphs of large girth into expander graphs. As an application of this method, we settle two problems: For a graph H, we denote by Hq the graph obtained from H by subdividing its edges with q–1 vertices each. We show that the k-size-Ramsey number Ŗk(Hq) satisfies Ŗk(Hq) = O(qn) for every bounded degree graph H on n vertices and for q = Ω(log n), which is optimal up to a constant factor. This settles a conjecture of Pak (2002). We give a deterministic, polynomial time algorithm for finding vertex-disjoint paths between given pairs of vertices in a strong expander graph. More precisely, let G be an (n, d, λ)-graph with λ = O(d1 – ∊), and let be any collection of at most disjoint pairs of vertices in G for some small constant c, such that in the neighborhood of every vertex in G there are at most d/4 vertices from . Then there exists a polynomial time algorithm which finds vertex-disjoint paths between every pair in , and each path is of the same length . Both the number of pairs and the length of the paths are optimal up to a constant factor; the result answers the offline version of a question of Alon and Capalbo (2007).

Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence number of $G(n,p)$ by Erdös and Bollobás and by Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/n\le p \le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2\log_q(np)$, where $q= \frac{1}{1-p}$.