Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Algorithmic solution of extremal digraph problems

Authors: W. G. Brown, P. Erdős and M. Simonovits
Journal: Trans. Amer. Math. Soc. 292 (1985), 421-449
MSC: Primary 05C35; Secondary 05C20
MathSciNet review: 808730
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C35, 05C20

Retrieve articles in all journals with MSC: 05C35, 05C20

Additional Information

Article copyright: © Copyright 1985 American Mathematical Society