
For a given family L \mathcal {L} of digraphs, we study the "extremal" digraphs on n n vertices containing no member of L \mathcal {L} , and having the maximum number of arcs, ex ( n , L ) \operatorname {ex} (n,\mathcal {L}) . We resolve conjectures concerning the set { lim n → ∞ ( ex ( n , L ) / n 2 ) } \{ {\lim _{n \to \infty }}(\operatorname {ex} (n,\mathcal {L})/{n^2})\} as L \mathcal {L} ranges over all possible families, and describe a "finite" algorithm that can determine, for any L \mathcal {L} , all matrices A A for which a sequence { A ( n ) } \{ A(n)\} of "matrix digraphs" is asymptotically extremal ( A ( n ) A(n) contains no member of L \mathcal {L} and has ex ( n , L ) + o ( n 2 ) \operatorname {ex} (n,\mathcal {L}) + o({n^2}) arcs as n → ∞ n \to \infty .) Résumé. Pour une famille donnée, L \mathcal {L} , de digraphes, on étudie les digraphes "extrémaux" à n n sommets qui ne contiennent aucun membre de L \mathcal {L} , et qui possèdent le nombre maximal d’arêtes, ex ( n , L ) \operatorname {ex} (n,\mathcal {L}) . On résolue des conjectures qui concernent l’ensemble { lim n → ∞ ( ex ( n , L ) / n 2 ) } \{ {\lim _{n \to \infty }}(\operatorname {ex} (n,\mathcal {L})/{n^2})\} où L \mathcal {L} soit une famille quelconque, et on présente un algorithme "fini" qui peut déterminer, pour chaque L \mathcal {L} , toute matrice A A pour laquelle une suite { A ( n ) } \{ A(n)\} de "digraphes matriciels" est extrémale asymptotiquement ( A ( n ) A(n) ne contient aucun membre de L \mathcal {L} et possède ex ( n , L ) + o ( n 2 ) \operatorname {ex} (n,\mathcal {L}) + o({n^2}) arêtes lorsque n → ∞ n \to \infty .)
Extremal problems in graph theory, Directed graphs (digraphs), tournaments, digraphs
Extremal problems in graph theory, Directed graphs (digraphs), tournaments, digraphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 21 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
