For 3-uniform hypergraphs, the maximum number of edges in an n-vertex hypergraph with no Berge theta made of 217 internally disjoint length-3 paths is Omega(n^{4/3}), matching the upper bound up to a constant.
Graphs with few paths of prescribed length between any two vertices
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We use a variant of Bukh's random algebraic method to show that for every natural number $k \geq 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.
fields
math.CO 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
3-uniform hypergraphs with few Berge paths of length three between any two vertices
For 3-uniform hypergraphs, the maximum number of edges in an n-vertex hypergraph with no Berge theta made of 217 internally disjoint length-3 paths is Omega(n^{4/3}), matching the upper bound up to a constant.