Some Turán type results on the hypercube |
| |
Authors: | David Offner |
| |
Institution: | Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, United States |
| |
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 |
本文献已被 ScienceDirect 等数据库收录! |
|