Algorithmic solution of extremal digraph problems
HTML articles powered by AMS MathViewer
- by W. G. Brown, P. Erdős and M. Simonovits
- Trans. Amer. Math. Soc. 292 (1985), 421-449
- DOI: https://doi.org/10.1090/S0002-9947-1985-0808730-0
- PDF | 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-III (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
Bibliographic 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