Paths in pseudorandom graphs and applications

Let G = (V, E) be an (n, d, lambda)-graph. In this paper, we give an asymptotically tight condition on the size of U subset of V such that the number of paths of length k in U is close to the expected number for arbitrary integer k >= 1. More precisely, we will show that if lambda n/d = o(vertical bar U vertical bar), then the number of paths of length k in U is (1 + o(1))vertical bar U vertical bar(k+1) (d/n)(k) . As applications, we obtain improvements and generalizations of recent results on Erdos-Falconer distance problems due to Bennett, Chapman, Covert, Hart, Iosevich, Pakianathan (2016).