Vertex Turán problems for the oriented hypercube

Dániel Gerbner, Abhishek Methuku, Dániel T. Nagy, Balázs Patkós, Máté Vizer

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish (US)
Pages (from-to)356-366
Number of pages11
JournalActa Universitatis Sapientiae, Mathematica
Volume13
Issue number2
DOIs
StatePublished - Dec 1 2021
Externally publishedYes

Keywords

  • Extremal set theory
  • Hypercube
  • Vertex Turán

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Vertex Turán problems for the oriented hypercube'. Together they form a unique fingerprint.

Cite this