Algorithmic solution of extremal digraph problems

Abstract:

For a given family $\mathcal {L}$ of digraphs, we study the "extremal" digraphs on $n$ vertices containing no member of $\mathcal {L}$, and having the maximum number of arcs, $\operatorname {ex} (n,\mathcal {L})$. We resolve conjectures concerning the set $\{ {\lim _{n \to \infty }}(\operatorname {ex} (n,\mathcal {L})/{n^2})\}$ as $\mathcal {L}$ ranges over all possible families, and describe a "finite" algorithm that can determine, for any $\mathcal {L}$, all matrices $A$ for which a sequence $\{ A(n)\}$ of "matrix digraphs" is asymptotically extremal ($A(n)$ contains no member of $\mathcal {L}$ and has $\operatorname {ex} (n,\mathcal {L}) + o({n^2})$ arcs as $n \to \infty$.) Résumé. Pour une famille donnée, $\mathcal {L}$, de digraphes, on étudie les digraphes "extrémaux" à $n$ sommets qui ne contiennent aucun membre de $\mathcal {L}$, et qui possèdent le nombre maximal d’arêtes, $\operatorname {ex} (n,\mathcal {L})$. On résolue des conjectures qui concernent l’ensemble $\{ {\lim _{n \to \infty }}(\operatorname {ex} (n,\mathcal {L})/{n^2})\}$ où $\mathcal {L}$ soit une famille quelconque, et on présente un algorithme "fini" qui peut déterminer, pour chaque $\mathcal {L}$, toute matrice $A$ pour laquelle une suite $\{ A(n)\}$ de "digraphes matriciels" est extrémale asymptotiquement ($A(n)$ ne contient aucun membre de $\mathcal {L}$ et possède $\operatorname {ex} (n,\mathcal {L}) + o({n^2})$ arêtes lorsque $n \to \infty$.)