Hypergraphs with few Berge paths of fixed length between vertices

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üredi 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.

arXiv commentA small mistake completing the proof of the main theorem has now been fixed

References in corpus (3)

• A bound on the number of edges in graphs without an even cycle
• Graphs with few paths of prescribed length between any two vertices
• Arithmetic Progressions of Cycle Lengths in Graphs