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.
Hypergraphs with few Berge paths of fixed length between vertices
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this paper we study the maximum number of hyperedges which may be in an $r$-uniform hypergraph under the restriction that no pair of vertices has more than $t$ Berge paths of length $k$ between them. When $r=t=2$, this is the even-cycle problem asking for $\mathrm{ex}(n, C_{2k})$. We extend results of F\"uredi and Simonovits and of Conlon, who studied the problem when $r=2$. In particular, we show that for fixed $k$ and $r$, there is a constant $t$ such that the maximum number of edges can be determined in order of magnitude.
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.