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?)

  • [1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR 0413592
  • [2] 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
  • [3] W. G. Brown, P. Erdős, and M. Simonovits, Extremal problems for directed graphs, J. Combinatorial Theory Ser. B 15 (1973), 77–93. MR 0387106
  • [4] -, 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.
  • [5] -, Multigraph extremal problems, preprint, 1975.
  • [6] 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
  • [7] 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, 10.1016/0012-365X(84)90178-X
  • [8] 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
  • [9] P. Erdős and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar 1 (1966), 51–57. MR 0205876
  • [10] 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
  • [11] 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
  • [12] Roland Häggkvist and Carsten Thomassen, On pancyclic digraphs, J. Combinatorial Theory Ser. B 20 (1976), no. 1, 20–40. MR 0389650
  • [13] 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 Russian and English summaries). MR 0172263
  • [14] T. S. Motzkin and E. G. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965), 533–540. MR 0175813
  • [15] 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
  • [16] 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
  • [17] M. Simonovits, Extremal graph theory, Selected topics in graph theory, 2, Academic Press, London, 1983, pp. 161–200. MR 797252
  • [18] P. Turán, Egy gráfelméleti szélsöérték feladatról, Mat. Fiz. Lapok 48 (1941), 436-452. MR 8, 284j.
  • [19] P. Turán, On the theory of graphs, Colloquium Math. 3 (1954), 19–30. MR 0062416
  • [20] 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

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