Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649892 | Discrete Mathematics | 2009 | 8 Pages |
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.