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


Vertex Turán problems in the hypercube
Authors:J Robert Johnson
Institution:a School of Mathematical Sciences, Queen Mary University of London, E1 4NS, UK
b Department of Mathematics, University College London, WC1E 6BT, UK
Abstract:Let Qn be the n-dimensional hypercube: the graph with vertex set n{0,1} and edges between vertices that differ in exactly one coordinate. For 1?d?n and Fd{0,1} we say that Sn{0,1} is F-free if every embedding View the MathML source satisfies i(F)?S. We consider the question of how large Sn{0,1} can be if it is F-free. In particular we generalise the main prior result in this area, for F=2{0,1}, due to E.A. Kostochka and prove a local stability result for the structure of near-extremal sets.We also show that the density required to guarantee an embedded copy of at least one of a family of forbidden configurations may be significantly lower than that required to ensure an embedded copy of any individual member of the family.Finally we show that any subset of the n-dimensional hypercube of positive density will contain exponentially many points from some embedded d-dimensional subcube if n is sufficiently large.
Keywords:Hypercube  Extremal problem  Turá  n problem
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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