Title of article :
Some Turلn type results on the hypercube
Author/Authors :
Offner، نويسنده , , David، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
8
From page :
2905
To page :
2912
Abstract :
For graphs H , G a classical problem in extremal graph theory asks what proportion of the edges of H a subgraph may contain without containing a copy of G . We prove some new results in the case where H 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 G is a member of this set and when G 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 G is the cube of dimension 3.
Keywords :
Hypercube , Fibonacci cube , Supersaturation , Turلn type problem , Robustness
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1598773
Link To Document :
بازگشت