Vertex Turán problems for the oriented hypercube

Abstract

In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph F→\vec F, determine the maximum cardinality exv(F→,Q→n)e{x_v}\left( {\vec F,{{\vec Q}_n}} \right) of a subset U of the vertices of the oriented hypercube Q→n{\vec Q_n} such that the induced subgraph Q→n[U]{\vec Q_n}\left[ U \right] does not contain any copy of F→\vec F. We obtain the exact value of exv(Pk,→ Qn→)e{x_v}\left( {\overrightarrow {{P_k},} \,\overrightarrow {{Q_n}} } \right) for the directed path Pk→\overrightarrow {{P_k}}, the exact value of exv(V2→, Qn→)e{x_v}\left( {\overrightarrow {{V_2}} ,\,\overrightarrow {{Q_n}} } \right) for the directed cherry V2→\overrightarrow {{V_2}} and the asymptotic value of exv(T→,Qn→)e{x_v}\left( {\overrightarrow T ,\overrightarrow {{Q_n}} } \right) for any directed tree T→\vec T.

Keywords

• vertex turán
• hypercube
• extremal set theory
• 05d05