Article ID Journal Published Year Pages File Type
4649892 Discrete Mathematics 2009 8 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,