Algorithmic solution of extremal digraph problems

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$.)