کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653367 | 1632775 | 2015 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A counterexample to sparse removal
ترجمه فارسی عنوان
مثال نمونه برای حذف ضعیف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
Journal: European Journal of Combinatorics - Volume 44, Part A, February 2015, Pages 77–86
نویسندگان
Craig Timmons, Jacques Verstraëte,