A note on the uniformity threshold for Berge hypergraphs

2021/10/30 by Dániel Gerbner, Gerbner, Dániel
Computer Science · Mathematics · #05C65 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2111.00356

openalex publication_date 2021/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A Berge copy of a graph is a hypergraph obtained by enlarging the edges arbitrarily. Grósz, Methuku and Tompkins in 2020 showed that for any graph F, there is an integer r₀=r₀(F), such that for any r≥ r₀, any r-uniform hypergraph without a Berge copy of F has o(n²) hyperedges. The smallest such r₀ is called the uniformity threshold of F and is denoted by th(F). They showed that th(F)≤ R(F,F'), where R denotes the off-diagonal Ramsey number and F' is any graph obtained form F by deleting an edge. We improve this bound to th(F)≤ R(K_χ(F),F'), and use the new bound to determine th(F) exactly for several classes of graphs.

Related

• Uniformity thresholds for the asymptotic size of extremal Berge-F-free\n hypergraphs
• On Berge-Ramsey problems
• On the weight of Berge-F-free hypergraphs
• Linearity of Saturation for Berge Hypergraphs
• On saturation of Berge hypergraphs