Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur 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