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
DOI: https://doi.org/10.1090/S0002-9947-1985-0808730-0
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] A. Aho, J. E. Hopcroft and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1974. ISBN 0-201-00029-6. MR 54 #1706. MR 0413592 (54:1706)
  • [2] B. Bollobás, Extremal graph theory, Academic Press, London, 1978. ISBN 0-12-111750-2. MR 80a #05120. MR 506522 (80a:05120)
  • [3] W. G. Brown, P. Erdös, and M. Simonovits, Extremal problems for directed graphs, J. Combin. Theory Ser. B 15 (1973), 77-93. MR 52 #7952. MR 0387106 (52:7952)
  • [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] -, Inverse extremal digraph problems, Colloq. Math. Soc. János Bolyai 37, Finite and Infinite Sets, Eger (Hungary), 1981, Akad. Kiadó, Budapest, 1985, pp. 119-156. MR 818232 (87f:05087)
  • [7] W. G. Brown and M. Simonovits, Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures, Discrete Math. 48 (1984), 147-162. MR 737261 (85b:05103)
  • [8] W. G. Brown and F. Harary, Extremal digraphs, Combinatorial Theory and its Applications, Colloq. Math. Soc. János Bolyai 4 (1970), I135-198. MR 45 #8576. MR 0299528 (45:8576)
  • [9] P. Erdös and M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966), 51-57. MR 34 #5702. MR 0205876 (34:5702)
  • [10] P. Erdös, Some recent results on extremal problems in graph theory (Results), Theory of Graphs: (International Symposium, Rome, 1966), Gordon & Breach, New York and Dunod, Paris, 1967, pp. 118-123. MR 37 #2634. MR 0227049 (37:2634)
  • [11] -, On some new inequalities concerning extremal properties of graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York and Akad. Kiadó, Budapest, 1968, pp. 77-81. MR 38 #1026. MR 0232703 (38:1026)
  • [12] R. Häggkvist and C. Thomassen, On pancyclic digraphs, J. Combin. Theory Ser. B 20 (1976), 20-40. MR 52 #10481. MR 0389650 (52:10481)
  • [13] Gy. Katona, T. Nemetz and M. Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok 15 (1964), 228-238. MR 30#2483. MR 0172263 (30:2483)
  • [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 31 #89. MR 0175813 (31:89)
  • [15] K. B. Reid, Two applications of Turán's theorem to asymmetric digraphs, Combinatorial Structures and their Applications, Proc. Calgary Internat. Conference (Calgary, Alberta, 1969), Gordon & Breach, New York, 1970, pp. 351-353. MR 42 #5861. MR 0270978 (42:5861)
  • [16] M. Simonovits, A method for solving problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq. Tihany, 1966), Academic Press, New York and Akad. Kiadó, Budapest, 1968, pp. 279-319. MR 38 #2056. MR 0233735 (38:2056)
  • [17] -, Extremal graph theory, Selected Topics in Graph Theory 2 (L. W. Beineke and R. J. Wilson, eds.), Academic Press, London, 1983, pp. 161-200, ISBN 0-12-086202-2. MR 797252 (86i:05089)
  • [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] -, On the theory of graphs, Colloq. Math.3 (1954), 19-30. MR 15, 976b. MR 0062416 (15:976b)
  • [20] A. Zykov, On some properties of linear complexes, Mat. Sb. 24 (1949), 163-188; Amer. Math. Soc. Transl. (1) 79 (1959). MR 11, 733h. MR 0035428 (11:733h)

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: https://doi.org/10.1090/S0002-9947-1985-0808730-0
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society