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})\} $ $ \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