Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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).
Rachid Guerraoui, Anne-Marie Kermarrec, Kévin Clément Huguenin, Andrei Giurgiu