A note on complete subdivisions in digraphs of large outdegree

✍ Scribed by Daniela Kühn; Deryk Osthus; Andrew Young

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 109 KB
• Volume: 57
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20255

✦ Synopsis

Abstract

Mader conjectured that for all $\ell$ there is an integer $\delta^+(\ell)$ such that every digraph of minimum outdegree at least $\delta^+(\ell)$ contains a subdivision of a transitive tournament of order $\ell$. In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let $\vec G$ be a digraph of order n whose minimum outdegree is at least d. Then $\vec G$ contains a subdivision of a complete digraph of order $\lfloor d^{2}/(8n^{3/2}) \rfloor$. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008