An n-vertex graph G is a C-expander if |N(X)| ≥ C|X| for every X ⊆ V(G) with |X| < n/2C and there is an edge between every two disjoint sets of at least n/2C vertices. We show that there is some constant C > 0 for which every C-expander is Hamiltonian. In particular, this implies the well-known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in (n,d,λ)-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs and has many applications, including to the Hamiltonicity of random Cayley graphs.

An n-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices, and it is pancyclic if it contains cycles of all lengths from 3 up to n. In 1972, Erdős conjectured that every Hamiltonian graph with independence number at most k and at least n = Ω(k^2) vertices is pancyclic. In this paper, we prove this old conjecture in a strong form by showing that if such a graph has n = (2 + o(1))k^2 vertices, it is already pancyclic, and this bound is asymptotically best possible.

We study how to route many connections through a highly connected network without conflicts. The network is modeled as a regular expander graph, which is a standard model for robust communication networks.

We design a deterministic algorithm that incrementally builds a collection of paths in the graph, with the guarantee that no two paths share an edge. The algorithm works online: requests are processed one by one, without knowing future requests in advance.

There are two types of operations. First, given two vertices that are not already heavily used, the algorithm efficiently finds a short path between them that does not interfere with any existing paths and adds it to the collection. Second, the algorithm can remove previously added paths, freeing their edges for future use. Despite this flexibility, the algorithm maintains strong guarantees on the number of paths it can handle and on the maximum length of each path.

The bounds we achieve are essentially optimal and improve upon a long line of earlier work, which either required all requests in advance or did not allow deletions. To our knowledge, this is the first online algorithm for edge-disjoint path routing in expander graphs that also supports removals. We also show that the same guarantees hold in the more delicate setting of directed graphs.

The size-Ramsey number of a graph H is the smallest number of edges a host graph G can have, such that for any red/blue coloring of G, there is a monochromatic copy of H in G. Conlon, Nenadov, and Trujić showed that if H is a graph with n vertices and maximum degree three, then the size-Ramsey number is O(n^(8/5)), improving upon the previous upper bound of n^(5/3+o(1)) by Kohayakawa, Rödl, Schacht, and Szemerédi. In this paper, we show that the size-Ramsey number is at most n^(3/2+o(1)). While previous results used binomial random graphs as host graphs, we achieve our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods.

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique and its algorithmic version, enhanced with a roll-back idea allowing a sequential retracing of previously performed embedding steps. We use this method to obtain the following results:

• We show that the size-Ramsey number of logarithmically long subdivisions of bounded degree graphs is linear in their number of vertices, settling a conjecture of Pak (2002).

• We give a deterministic, polynomial time online algorithm for finding vertex-disjoint paths of a prescribed length between given pairs of vertices in an expander graph. Our result answers a question of Alon and Capalbo (2007).

• We show that relatively weak bounds on the spectral ratio λ/d of d-regular graphs force the existence of a topological minor of Kt where t = (1 − o(1))d. We also exhibit a construction which shows that the theoretical maximum t = d + 1 cannot be attained even if λ = O(√d). This answers a question of Fountoulakis, Kühn, and Osthus (2009).

The induced size-Ramsey number of a graph is the smallest number of edges a host graph can have, such that no matter how its edges are colored with a certain number of colors, there will always be a monochromatic copy of the original graph as an induced subgraph. In 1995, Haxell, Kohayakawa, and Łuczak showed that for cycles, these numbers are linear in the size of the cycle for any constant number of colors. This result was achieved using the regularity lemma, which led to a very large, tower-type dependence on the number of colors.

In our work, we significantly improve these bounds, showing that the induced size-Ramsey number for cycles has a much smaller dependence on the number of colors. Specifically, for even-sized cycles, the number grows polynomially with the number of colors, and for odd-sized cycles, we show upper bounds very close to the known lower bounds. Additionally, we prove essentially optimal bounds for the normal (non-induced) size-Ramsey number for odd cycles, showing that they grow exponentially in the number of colors. Our approach involves a new construction of the host graph, which simplifies the problem to finding a cycle of only an approximate length in a graph with local sparsity.

In 1996, in his final paper, Erdős posed the following question together with Faudree: Is there a positive constant c such that every (n+1)-regular graph on 2n vertices contains at least c·2^(2n) distinct subsets of vertices that are cyclic, meaning each subset exactly forms the vertex set of a cycle?

We answer this question affirmatively and in a strong form. Specifically, we prove the following exact result: for all sufficiently large n, the graph that minimizes the number of such cyclic subsets is constructed by taking the complete bipartite graph with parts of size n−1 and n+1, and adding a 2-factor (a spanning collection of vertex-disjoint cycles) within the larger part.

In particular, this implies that for large n, the optimal constant c is exactly one-half.

A linear forest is a collection of vertex‑disjoint paths. The Linear Arboricity Conjecture states that any graph of maximum degree Δ can be decomposed into at most ⌈(Δ + 1)/2⌉ linear forests. We prove that Δ/2 + O(log n) linear forests suffice, where n is the number of vertices of the graph. If Δ = Ω(n^ε), this represents an exponential improvement over the previous best error term. Our approach generalizes Pósa rotations—from rotating a single path endpoint to performing simultaneous rotations on multiple endpoints within a linear forest. This technique also resolves a conjecture of Feige and Fuchs on spanning linear forests with few paths and establishes the existence of optimally short tours in connected regular graphs. 

Dirac’s classical theorem shows that dense graphs with minimum degree at least n/2 are Hamiltonian, and later work proved that regular such graphs even decompose into Hamilton cycles, resolving the Nash–Williams conjecture. In the pseudorandom setting, it was long conjectured that analogous results hold in much sparser graphs. We establish asymptotically optimal theorems on resilience and Hamilton decompositions in sparse pseudorandom graphs, substantially improving previous results.