首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号