کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653367 1632775 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A counterexample to sparse removal
ترجمه فارسی عنوان
مثال نمونه برای حذف ضعیف
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 44, Part A, February 2015, Pages 77–86
نویسندگان
, ,