On tight cycles in hypergraphs

2017/11/20 by Hao Huang, Jie Ma, Huang, Hao +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1711.07442

openalex publication_date 2017/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A tight k-uniform ℓ-cycle, denoted by TC_ℓ^k, is a k-uniform hypergraph whose vertex set is v₀, ⋯, v_ℓ-1, and the edges are all the k-tuples \v_i, v_i+1, ⋯, v_i+k-1\, with subscripts modulo ℓ. Motivated by a classic result in graph theory that every n-vertex cycle-free graph has at most n-1 edges, Sós and, independently, Verstraëte asked whether for every integer k, a k-uniform n-vertex hypergraph without any tight k-uniform cycles has at most \binomn-1k-1 edges. In this paper, we answer this question in negative.

Citations

• On a Packing and Covering Problem
• On extremal problems of graphs and generalized graphs

Related

• The extremal number of tight cycles
• Hypergraphs with no tight cycles
• The codegree Turán density of tight cycles minus one edge
• Tight cycles and regular slices in dense hypergraphs
• The Turán Density of 4-Uniform Tight Cycles