A counterexample to sparse removal

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

Authors: Craig Timmons, J. Verstraëte 

Publication date: 19 November 2014

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On a problem of K. Zarankiewicz
• On Certain Sets of Integers
• 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
• Compactness results in extremal graph theory
• New asymptotics for bipartite Turán numbers
• Title not available (Why is that?)
• Dependent random choice
• Graph removal lemmas
• On hypergraphs of girth five
• 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 that?)
• 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)