Vertex Turلn problems in the hypercube

Let Q n be the n-dimensional hypercube: the graph with vertex set { 0 , 1 } n and edges between vertices that differ in exactly one coordinate. For 1 ⩽ d ⩽ n and F ⊆ { 0 , 1 } d we say that S ⊆ { 0 , 1 } n is F-free if every embedding i : { 0 , 1 } d → { 0 , 1 } n satisfies i ( F ) ⊈ S . We consider the question of how large S ⊆ { 0 , 1 } n can be if it is F-free. In particular we generalise the main prior result in this area, for F = { 0 , 1 } 2 , due to E.A. Kostochka and prove a local stability result for the structure of near-extremal sets. o 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. y 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.