Vertex Turán problems for the oriented hypercube

2018/07/18 by Gerbner, Dániel, Methuku, Abhishek, Nagy, Dániel T. +2
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1807.06866

Abstract

In this short note we consider the oriented vertex Turán problem in the hypercube: for a fixed oriented graph \overrightarrowF, determine the maximum size ex_v(\overrightarrowF, \overrightarrowQ_n) of a subset U of the vertices of the oriented hypercube \overrightarrowQ_n such that the induced subgraph \overrightarrowQ_n[U] does not contain any copy of \overrightarrowF. We obtain the exact value of ex_v(\overrightarrowP_k, \overrightarrowQ_n) for the directed path \overrightarrowP_k, the exact value of ex_v(\overrightarrowV₂, \overrightarrowQ_n) for the directed cherry \overrightarrowV₂ and the asymptotic value of ex_v(\overrightarrowT, \overrightarrowQ_n) for any directed tree \overrightarrowT.

Related

• Vertex Turán problems in the hypercube
• Generalized Turán densities in the hypercube
• On the Turán number of the hypercube
• Generalized Turán problem for directed cycles
• An extremal theorem in the hypercube