Department of
Applied
Mathematics

Subdivision of digraphs with large minimum out-degree

Phablo Moura

UNICAMP

Abstract

Given a digraph D, a subdivision of D is a digraph obtained by replacing every arc uv in D by a directed path P(u,v) from u to v in such a way that every internal vertex of P(u,v) (if any) is a newly created vertex.

In 1985, Mader conjectured the existence of a function f such that every digraph with minimum out-degree at least f(k) contains a subdivision of the transitive tournament of order k. This conjecture is still completely open, as the existence of f(5) remains unknown. In this talk, we give some new evidences to this conjecture. More precisely, if D is an oriented path, or an in-arborescence (i.e. a tree with all edges oriented towards the root), then every digraph with minimum out-degree large enough contains a subdivision of D. Additionally, we present an overview of the main conjectures and results related to subdivisions of digraphs.

(This is a joint work with Pierre Aboulker, Nathann Cohen, Frédéric Havet, William Lochet and Stéphan Thomassé.)