On the maximum induced density of directed stars and related problems

Hao Huang

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

Let κ ≥ 3 be an integer. We prove that the maximum induced density of the κ-vertex directed star in a directed graph is asymptotically attained by an iterated blow-up construction. This confirms a conjecture of Falgas-Ravry and Vaughan, who proved this for κ = 3, 4, 5. This question provides the first explicitly known instance of a density problem for which one can prove extremality of an iterated blow-up construction. We also study the inducibility of complete bipartite digraphs and discuss other related problems.

Original languageEnglish (US)
Pages (from-to)92-98
Number of pages7
JournalSIAM Journal on Discrete Mathematics
Volume28
Issue number1
DOIs
StatePublished - 2014

Keywords

  • Directed star
  • Inducibility
  • Iterated blow-up

Fingerprint Dive into the research topics of 'On the maximum induced density of directed stars and related problems'. Together they form a unique fingerprint.

  • Cite this