Hypergraphs with few Berge paths of fixed length between vertices

2018/07/26 by Zhiyang He, He, Zhiyang, Michael Tait +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1807.10177

openalex publication_date 2018/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

Cited by

• Induced rational exponents and bipartite subgraphs in K_{s, s}-free graphs
• General lemmas for Berge-Turán hypergraph problems

Related

• On 3-uniform hypergraphs without a cycle of a given length
• Stability of extremal connected hypergraphs avoiding Berge-paths
• Avoiding long Berge cycles II, exact bounds for all n
• On the maximum size of connected hypergraphs without a path of given\n length
• On 2-connected hypergraphs with no long cycles