2013/12/10 by Craig Timmons, Timmons, Craig, Jacques Verstraete +1
Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C35
paper · pdf · doi:10.48550/arxiv.1312.2994
arxiv created 2013/12/10 · arxiv updated 2013/12/12
The Turán number of a graph H, denoted ex(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 ex(n,H) = O(nα) where α> 1, then any n-vertex graph with the property that each edge lies in exactly one copy of H has o(nα) 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édi. Using Sidon sets we exhibit infinitely many bipartite graphs H for which the conjecture is false.