Vertex Turan problems in the hypercube

Vertex Turan problems in the hypercube

Tue, 20/01/2009
14:30 		John Talbot (UCL) Combinatorial Theory Seminar Add to calendar L3
Vertex Turan problems in the hypercube
Let $ Q_n=\{0,1\}^n $ be the $ n $-dimensional hypercube. For $ 1\leq d \leq n $ and $ F\subseteq Q_d $ we consider the question of how large $ S\subseteq Q _n $ can be if every embedding $ i:Q_d\to Q_n $ satisfies $ i(F)\not\subseteq S $. We determine the asymptotic behaviour of the largest $ F $-free subsets of $ Q_n $ for a variety of $ F $, in particular we generalise the sole non-trivial prior result in this area: $ F=Q_2 $ due to E.A. Kostochka. Many natural questions remain open. This is joint work with Robert Johnson.