Publication

Paths in pseudorandom graphs and applications

Van Thang Pham
2020
Journal Articles

Résumé

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).

Source officielle

https://infoscience.epfl.ch/entities/publication/4aaff8b0-048e-4266-830a-89b7ec5b241a

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Paths in pseudorandom graphs and applications

Chattez avec Graph Search

Toroidal families and averages of L-functions, I

Using Structural Properties for Integer Programs

Computing in social networks