Article ID Journal Published Year Pages File Type
4653367 European Journal of Combinatorics 2015 10 Pages PDF
Abstract

The Turán number   of a graph HH, denoted ex(n,H)ex(n,H), is the maximum number of edges in an nn-vertex graph with no subgraph isomorphic to HH. Solymosi (2011) conjectured that if HH is any graph and ex(n,H)=O(nα)ex(n,H)=O(nα) where α>1α>1, then any nn-vertex graph with the property that each edge lies in exactly one copy of HH has o(nα)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 HH is a non-bipartite graph, in particular when HH is a triangle, due to Ruzsa and Szemerédi (1978). Using Sidon sets we exhibit infinitely many bipartite graphs HH for which the conjecture is false.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,