Vertex Turán problems in the hypercube

Details Vertex Turán problems in the hypercube Vertex Turán problems in the hypercube

2009-04-09

arxiv.org/abs/0904.1479v2

Mathematics

Combinatorics

15 pages 2 figures. Revised version to appear in Journal of Combinatorial Theory, Series A

Scientific paper

Let $\mathcal{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\leq d\leq n$ and $F\subseteq \{0,1\}^d$ we say that $S\subseteq \{0,1\}^n$ is \emph{$F$-free} if every embedding $i:\{0,1\}^d\to \{0,1\}^n$ satisfies $i(F)\not\subseteq S$. We consider the question of how large $S\subseteq \{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.

Affiliated with

Also associated with

No associations

Rating

Vertex Turán problems in the hypercube does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Vertex Turán problems in the hypercube, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex Turán problems in the hypercube will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-408431