Spanning trees in pseudorandom graphs via sorting networks

Joseph Hyde, Natasha Morrison, Alp Müyesser +1

We show that $(n,d,\lambda )$-graphs with $\lambda =O(d/{\log }^{3}n)$ are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due t…