Vertex Turan problems for the oriented hypercube


Abstract in English

In this short note we consider the oriented vertex Turan problem in the hypercube: for a fixed oriented graph $overrightarrow{F}$, determine the maximum size $ex_v(overrightarrow{F}, overrightarrow{Q_n})$ of a subset $U$ of the vertices of the oriented hypercube $overrightarrow{Q_n}$ such that the induced subgraph $overrightarrow{Q_n}[U]$ does not contain any copy of $overrightarrow{F}$. We obtain the exact value of $ex_v(overrightarrow{P_k}, overrightarrow{Q_n})$ for the directed path $overrightarrow{P_k}$, the exact value of $ex_v(overrightarrow{V_2}, overrightarrow{Q_n})$ for the directed cherry $overrightarrow{V_2}$ and the asymptotic value of $ex_v(overrightarrow{T}, overrightarrow{Q_n})$ for any directed tree $overrightarrow{T}$.

Download