کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649892 | 1342468 | 2009 | 8 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 309, Issue 9, 6 May 2009, Pages 2905–2912