2021/02/07 by Jiaxi Nie, Jacques Verstraëte, Nie, Jiaxi +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2102.03720
openalex publication_date 2021/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we consider an extension of cycle-complete graph Ramsey numbers to Berge cycles in hypergraphs: for k ≥ 2, a \em non-trivial Berge k-cycle is a family of sets e1,e2,…,ek such that e1 ∩ e2, e2 ∩ e3,…,ek ∩ e1 has a system of distinct representatives and e1 ∩ e2 ∩ … ∩ ek = ∅. In the case that all the sets ei have size three, let Bk denotes the family of all non-trivial Berge k-cycles. The \em Ramsey numbers R(t,Bk) denote the minimum n such that every n-vertex 3-uniform hypergraph contains either a non-trivial Berge k-cycle or an independent set of size t. We prove R(t, B2k) ≤ t1 + (1)/(2k-1) + (4)/(√(log t)) and moreover, we show that if a conjecture of Erdős and Simonovits \citeES on girth in graphs is true, then this is tight up to a factor to(1) as t → ∞.