Lecture by Frédéric Havet (INRIA Sophia-Antipolis): Unavoidability and universality of digraphs
A digraph F is n-unadoidable} (resp. n-universal) if it is contained in every tournament of order n (resp. n-chromatic digraph). Well-known theorems imply that there is an nF such that F is nF-unavoidable (resp. nF-universal) if and only if F is acyclic, (resp. an oriented forest). However, determining the smallest nF for which it occurs is a challenging question. In this talk, we survey the results on unavoidability and universality and detail some recent recults obtained with various co-authors.
Time & Location
Jul 12, 2021 | 02:15 PM