Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653367 | European Journal of Combinatorics | 2015 | 10 Pages |
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
Craig Timmons, Jacques Verstraëte,