Graphs with few paths of prescribed length between any two vertices
arXiv:1411.0856 · doi:10.1112/blms.12295
Abstract
We use a variant of Bukh's random algebraic method to show that for every natural number there exists a natural number such that, for every , there is a graph with vertices and edges with at most paths of length 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.
arXiv comment8 pages
References in corpus (1)
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