کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649892 1342468 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Some Turán type results on the hypercube
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Some Turán type results on the hypercube
چکیده انگلیسی

For graphs H,GH,G a classical problem in extremal graph theory asks what proportion of the edges of HH a subgraph may contain without containing a copy of GG. We prove some new results in the case where HH is a hypercube. We use a supersaturation technique of Erdős and Simonivits to give a characterization of a set of graphs such that asymptotically the answer is the same when GG is a member of this set and when GG is a hypercube of some fixed dimension. We apply these results to a specific set of subgraphs of the hypercube called Fibonacci cubes. Additionally, we use a coloring argument to prove new asymptotic bounds on this problem for a different set of graphs. Finally we prove a new asymptotic bound for the case where GG is the cube of dimension 3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 9, 6 May 2009, Pages 2905–2912
نویسندگان
,