A generalized Turán problem and its applications

DOI10.1145/3188745.3188778MaRDI QIDQ5230336zbMATH OpenOpenAlexFDO

Authors Lior Gishboliner, Asaf Shapira

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.00831

zbMATH Keywords

generalized Turán problemgraph property testing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: The investigation of conditions guaranteeing the appearance of cycles of certain lengths is one of the most well-studied topics in graph theory. In this paper we consider a problem of this type which asks, for fixed integers $ell$ and $k$, how many copies of the $k$-cycle guarantee the appearance of an $ell$-cycle? Extending previous results of Bollob'as--GyH{o}ri--Li and Alon--Shikhelman, we fully resolve this problem by giving tight (or nearly tight) bounds for all values of $ell$ and $k$. We also present a somewhat surprising application of the above mentioned estimates to the study of the graph removal lemma. Prior to this work, all bounds for removal lemmas were either polynomial or there was a tower-type gap between the best known upper and lower bounds. We fill this gap by showing that for every super-polynomial function $f(varepsilon)$, there is a family of graphs $calF$, such that the bounds for the $calF$ removal lemma are precisely given by $f(varepsilon)$. We thus obtain the first examples of removal lemmas with tight super-polynomial bounds. A special case of this result resolves a problem of Alon and the second author, while another special case partially resolves a problem of Goldreich.

Recommendations

• Testing subgraphs in large graphs
• Testing Triangle-Freeness in General Graphs
• Testing subgraphs in directed graphs
• Testing subgraphs in directed graphs
• Every monotone graph property is testable

Cited in

(21)

• Some sharp results on the generalized Turán numbers
• On Turán-good graphs
• Maximizing five-cycles in \(K_r\)-free graphs
• Generalized rainbow Turán problems
• Generalized Turán problems for even cycles
• Hierarchy theorems for testing properties in size-oblivious query complexity
• The shifting method and generalized Turán number of matchings
• Counting copies of a fixed subgraph in F-free graphs
• Generalized Turán problems for disjoint copies of graphs
• \(C_{2k}\)-saturated graphs with no short odd cycles
• Generalized planar Turán numbers
• scientific article; zbMATH DE number 3827993 (Why is no real title available?)
• The generalized rainbow Turán problem for cycles
• Many H-copies in graphs with a forbidden tree
• On the maximum number of copies of H in graphs with given size and order
• On supersaturation and stability for generalized Turán problems
• Generalized Turán problems for even cycles
• On the maximum number of odd cycles in graphs without smaller odd cycles
• Generalized regular Turán numbers
• Generalized Turán problems for small graphs
• The number of cliques in hypergraphs with forbidden subgraphs

This page was built for publication: A generalized Turán problem and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230336)