Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Algorithmic solution of extremal digraph problems
HTML articles powered by AMS MathViewer

by W. G. Brown, P. Erdős and M. Simonovits PDF
Trans. Amer. Math. Soc. 292 (1985), 421-449 Request permission

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
  • Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
  • Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
  • W. G. Brown, P. Erdős, and M. Simonovits, Extremal problems for directed graphs, J. Combinatorial Theory Ser. B 15 (1973), 77–93. MR 387106, DOI 10.1016/0095-8956(73)90034-8
  • —, Multigraph extremal problems, Colloques Internationaux C.N.R.S. 260: Problèmes combinatoires et théorie des graphes, Proc. Colloq., Orsay, 1976 (Editions C.N.R.S., Paris, 1978). ISBN 2-222-02070-0, 63-66. —, Multigraph extremal problems, preprint, 1975.
  • W. G. Brown, P. Erdős, and M. Simonovits, Inverse extremal digraph problems, Finite and infinite sets, Vol. I, II (Eger, 1981) Colloq. Math. Soc. János Bolyai, vol. 37, North-Holland, Amsterdam, 1984, pp. 119–156. MR 818232
  • W. G. Brown and M. Simonovits, Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures, Discrete Math. 48 (1984), no. 2-3, 147–162. MR 737261, DOI 10.1016/0012-365X(84)90178-X
  • W. G. Brown and F. Harary, Extremal digraphs, Combinatorial theory and its applications, I (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 135–198. MR 0299528
  • P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966), 51–57. MR 205876
  • P. Erdős, Some recent results on extremal problems in graph theory. Results, Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 1967, pp. 117–123 (English); pp. 124–130 (French). MR 0227049
  • P. Erdős, On some new inequalities concerning extremal properties of graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 77–81. MR 0232703
  • Roland Häggkvist and Carsten Thomassen, On pancyclic digraphs, J. Combinatorial Theory Ser. B 20 (1976), no. 1, 20–40. MR 389650, DOI 10.1016/0095-8956(76)90063-0
  • Gyula Katona, Tibor Nemetz, and Miklós Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok 15 (1964), 228–238 (Hungarian, with English and Russian summaries). MR 172263
  • T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canadian J. Math. 17 (1965), 533–540. MR 175813, DOI 10.4153/CJM-1965-053-6
  • K. B. Reid, Two applications of Turán’s theorem to asymmetric digraphs, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 351–353. MR 0270978
  • M. Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 279–319. MR 0233735
  • M. Simonovits, Extremal graph theory, Selected topics in graph theory, 2, Academic Press, London, 1983, pp. 161–200. MR 797252
  • P. Turán, Egy gráfelméleti szélsöérték feladatról, Mat. Fiz. Lapok 48 (1941), 436-452. MR 8, 284j.
  • P. Turán, On the theory of graphs, Colloq. Math. 3 (1954), 19–30. MR 62416, DOI 10.4064/cm-3-1-19-30
  • A. A. Zykov, On some properties of linear complexes, Mat. Sbornik N.S. 24(66) (1949), 163–188 (Russian). MR 0035428
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
  • © Copyright 1985 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 292 (1985), 421-449
  • MSC: Primary 05C35; Secondary 05C20
  • DOI: https://doi.org/10.1090/S0002-9947-1985-0808730-0
  • MathSciNet review: 808730