CaltechAUTHORS
  A Caltech Library Service

Graphs with few paths of prescribed length between any two vertices

Conlon, David (2019) Graphs with few paths of prescribed length between any two vertices. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170853333

[img] PDF - Submitted Version
See Usage Policy.

125Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-170853333

Abstract

We use a variant of Bukh's random algebraic method to show that for every natural number k ≥ 2 there exists a natural number ℓ such that, for every n, there is a graph with n vertices and Ω_(k)(n^(1 + 1/k)) edges with at most ℓ paths of length k between any two vertices. A result of Faudree and Simonovits shows that the bound on the number of edges is tight up to the implied constant.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1411.0856arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:Research supported by a Royal Society University Research Fellowship. I would like to thank Boris Bukh, Gal Kronenberg, Rudi Mrazović and Lisa Sauermann for a number of valuable comments on an earlier draft of this paper. I would also like to thank the anonymous referee for their considered review.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
Record Number:CaltechAUTHORS:20190819-170853333
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-170853333
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98021
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 19:54
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page