2017/12/03 by Lior Gishboliner, Asaf Shapira, A. Shapira +2 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Function (biology) #Graph #Graph theory and applications #Lemma (botany) #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Polynomial #Tower #Type (biology) #Upper and lower bounds #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1712.00831
arxiv created 2017/12/03 · openalex publication_date 2017/12/03 · arxiv updated 2017/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The investigation of conditions guaranteeing the appearance of cycles of\ncertain lengths is one of the most well-studied topics in graph theory. In this\npaper we consider a problem of this type which asks, for fixed integers\n\ℓ and k, how many copies of the k-cycle guarantee the appearance of\nan \ℓ-cycle? Extending previous results of Bollob 'as--Gy Hori--Li and\nAlon--Shikhelman, we fully resolve this problem by giving tight (or nearly\ntight) bounds for all values of \ℓ and k.\n We also present a somewhat surprising application of the above mentioned\nestimates to the study of the graph removal lemma. Prior to this work, all\nbounds for removal lemmas were either polynomial or there was a tower-type gap\nbetween the best known upper and lower bounds. We fill this gap by showing that\nfor every super-polynomial function f(\ε), there is a family of\ngraphs cal F, such that the bounds for the cal F removal lemma are\nprecisely given by f(\ε). We thus obtain the first examples of\nremoval lemmas with tight super-polynomial bounds. A special case of this\nresult resolves a problem of Alon and the second author, while another special\ncase partially resolves a problem of Goldreich.\n