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 F⊆d{0,1} we say that S⊆n{0,1} is F-free if every embedding satisfies i(F)?S. We consider the question of how large S⊆n{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 等数据库收录! |
|