Graphs with few paths of prescribed length between any two vertices

We use a variant of Bukh’s random algebraic method to show that for every natural number $k\ge 2$ there exists a natural number $\mathrm{\ell }$ such that, for every $n$, there is a graph with $n$ vertices and ${\mathrm{\Omega }}_k(n^{1+1\mathrm{/}k})$ edges with at most $\mathrm{\ell }$ 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.