Tue, 20 Jan 2009
14:30 -
15:30
L3
Vertex Turan problems in the hypercube
John Talbot
(UCL)
Abstract
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.