2009/04/09 by J. Robert Johnson, Johnson, J. Robert, John Talbot +1
Computer Science · Mathematics · #05C35 #05D05 #Advanced Mathematical Modeling in Engineering #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.0904.1479
openalex publication_date 2009/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let Qn 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)\not⊆ 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. 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.