2014/04/20 by Clayton Collier-Cartaino, Collier-Cartaino, Clayton, Nathan Graber +3 · 1 citation
Computer Science · Mathematics · #05 combinatorics #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1404.5015
openalex publication_date 2014/04/20 · openalex created_date 2016/11/30 · openalex updated_date 2026/07/28
An r-uniform hypergraph is called an r-graph. A hypergraph is linear if every two edges intersect in at most one vertex. Given a linear r-graph H and a positive integer n, the linear Turán number exL(n,H) is the maximum number of edges in a linear r-graph G that does not contain H as a subgraph. For each ℓ≥ 3, let Cr_ℓ denote the r-uniform linear cycle of length ℓ, which is an r-graph with edges e1,…, e_ℓ such that ∀ i∈ [ℓ-1], |ei∩ ei+1|=1, |e_ℓ∩ e1|=1 and ei∩ ej=∅ for all other pairs \i,j\, i≠ j. For all r≥ 3 and ℓ≥ 3, we show that there exist positive constants cm,r and c'm,r, depending only m and r, such that exL(n,Cr2m)≤ cm,r n1+(1)/(m) and exL(n,Cr2m+1)≤ c'm,r n1+(1)/(m). This answers a question of Kostochka, Mubayi, and Verstraëte. For even cycles, our result extends the result of Bondy and Simonovits on the Turán numbers of even cycles to linear hypergraphs. Using our results on linear Turán numbers we also obtain bounds on the cycle-complete hypergraph Ramsey numbers. We show that there are positive constants am,r and bm,r, depending only on m and r, such that R(Cr2m, Krt)≤ am,r ((t)/(ln t))^(m)/(m-1) and R(Cr2m+1, Krt)≤ bm,r t^(m)/(m-1).