Relative Turán Numbers for Hypergraph Cycles

2020/12/21 by Sam Spiro, Jacques Verstraëte, Spiro, Sam +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2012.11061

openalex publication_date 2020/12/21 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

For an r-uniform hypergraph H and a family of r-uniform hypergraphs F, the relative Turán number ex(H,F) is the maximum number of edges in an F-free subgraph of H. In this paper we give lower bounds on ex(H,F) for certain families of hypergraph cycles F such as Berge cycles and loose cycles. In particular, if C_ℓ³ denotes the set of all 3-uniform Berge ℓ-cycles and H is a 3-uniform hypergraph with maximum degree Δ, we prove ex(H,C₄³)≥ Δ^-3/4-o(1)e(H), ex(H,C₅³)≥ Δ^-3/4-o(1)e(H), and these bounds are tight up to the o(1) term.

Citations

• Existence of spanning F-free subgraphs with large minimum degree
• The regularity method for graphs with few 4-cycles
• Triangle-free Subgraphs of Hypergraphs
• Inverse Tur'an numbers

Related

• Relative Turán Problems for Uniform Hypergraphs
• Turan numbers of complete 3-uniform Berge-hypergraphs
• Hypergraph Turán numbers of vertex disjoint cycles
• Random Turán theorem for hypergraph cycles
• A note on the Turán number for the traces of hypergraphs