A counterexample to sparse removal. (February 2015)

• Record Type: Journal Article
• Authors: Timmons, Craig; Verstraëte, Jacques
• Is Part Of: European journal of combinatorics. Volume 44:Part A(2015)
• Page Start: 77
• Page End: 86
• Publication Date: 2015-02
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2014.09.008
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 (2011) 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 (1978). Using Sidon sets we exhibit infinitely many bipartite graphs H for which the conjecture is false.