Abstract

How pseudorandom does a graph need to be before it contains a certain spanning subgraph? This problem is not very well understood, especially in comparison to its purely random analogue. For example, the best possible condition that forces an (n,d,\lambda)-graph to contain a Hamilton cycle is not known, where an (n,d,\lambda)-graph is an n-vertex, d-regular graph such that the second largest eigenvalue (in absolute value) of the adjacency matrix is bounded above by \lambda. The smaller \lambda is, the more control we have over the edge distribution, and the easier it becomes to embed spanning subgraphs. Alon, Krivelevich, and Sudakov asked in 2007 if the mild condition ”\lambda=o(d)” is sufficient to guarantee that an (n,d,\lambda)-graph contains all bounded degree spanning trees. Improving significantly on previous results, we show that the condition ”\lambda Contrary to other results in the area, our proof does not rely on any absorption technique. Instead, we take a new approach based on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Komlós and Szemerédi. Using this construction, we show that the classical vertex-disjoint paths problem can be solved for a set of vertices fixed in advance, which might be of independent interest.

Joint work with Joseph Hyde, Natasha Morrison, and Matías Pavez-Signé.