A counterexample to sparse removal

DOI10.1016/J.EJC.2014.09.008zbMATH Open1302.05089OpenAlexW2089062285WikidataQ124840434 ScholiaQ124840434MaRDI QIDQ472399FDOQ472399

Authors Craig Timmons, J. Verstraëte 

Publication date 19 November 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

bipartite graphsSidon sets

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Abstract: The Tur'{a}n number of a graph $H$, denoted $mboxex(n,H)$, is the maximum number of edges in an $n$-vertex graph with no subgraph isomorphic to $H$. Solymosi conjectured that if $H$ is any graph and $mboxex(n,H)=O(n^{alpha})$ where $alpha>1$, then any $n$-vertex graph with the property that each edge lies in exactly one copy of $H$ has $o(n^{alpha})$ edges. This can be viewed as conjecturing a possible extension of the removal lemma to sparse graphs, and is well-known to be true when $H$ is a non-bipartite graph, in particular when $H$ is a triangle, due to Ruzsa and Szemer'{e}di. Using Sidon sets we exhibit infinitely many bipartite graphs $H$ for which the conjecture is false.

Recommendations

• Disproof of a Conjecture of Erdős and Simonovits on the Turán Number of Graphs with Minimum Degree 3
• Graph removal lemmas
• Turán numbers of bipartite graphs plus an odd cycle
• Turán number of bipartite graphs with no \(K_{t,t}\)
• On the Turán number for the hexagon

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• Compactness results in extremal graph theory
• Dependent random choice
• Graph removal lemmas
• New asymptotics for bipartite Turán numbers
• On Certain Sets of Integers
• On a problem of K. Zarankiewicz
• On hypergraphs of girth five
• Solving a linear equation in a set of integers I
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions

Cited in

(9)

• Counting hypergraphs with large girth
• Sparse hypergraphs with applications to coding theory
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Title not available (Why is no real title available?)
• Relative Turán numbers for hypergraph cycles
• Generalized Turán problems for complete bipartite graphs
• Planar polynomials and an extremal problem of Fischer and Matoušek
• On \(r\)-uniform linear hypergraphs with no Berge-\(K_{2,t}\)
• Improved lower bounds for multiplicative square-free sequences

This page was built for publication: A counterexample to sparse removal

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