Graphs with few paths of prescribed length between any two vertices

Abstract

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 $\ell$ such that, for every $n$, there is a graph with $n$ vertices and ${\Omega }_k(n^{1+1/k})$ edges with at most $\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.

8 pages

References in corpus (1)

• Turán numbers for $K_{s,t}$-free graphs: topological obstructions and algebraic constructions

Cited by in corpus (15)

• On Turán exponents of bipartite graphs
• Some remarks on the Zarankiewicz problem
• Repeated patterns in proper colourings
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
• The extremal number of longer subdivisions
• Balanced supersaturation for some degenerate hypergraphs
• Turan numbers of bipartite subdivisions
• Hypergraphs with few Berge paths of fixed length between vertices
• Some extremal results on hypergraph Turán problems
• Balanced supersaturation and Turan numbers in random graphs
• On the Turán Number of Generalized Theta Graphs
• 3-uniform hypergraphs with few Berge paths of length three between any two vertices
• Some extremal results on complete degenerate hypergraphs
• A polynomial resultant approach to algebraic constructions of extremal graphs
• Bipartite-ness under smooth conditions