Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0002-9947-1985-0808730-0
PII: S 0002-9947(1985)0808730-0
Article copyright: © Copyright 1985 American Mathematical Society