Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  569.05023
Autor:  Brown, William G.; Erdös, Paul; Simonovits, M.
Title:  Inverse extremal digraph problems. (In English)
Source:  Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. I, Colloq. Math. Soc. János Bolyai 37, 119-156 (1984).
Review:  [For the entire collection see Zbl 559.00001.]
Authors' abstract: "The authors continue their study of extremal problems of Turán type for directed graphs with multiple edges, now permitting any finite non-negative integer multiplicity. Having proved earlier (for the case of multiplicity at most 1) that there exists, for any family of "sample" digraphs, a matrix which represents the structure of an "asymptotically extremal sequence" of digraphs (containing none of the sample digraphs, and having a total number of arcs asymptotic to the maximum), they address themselves to the inverse problem: is every matrix so realized for some finite family of sample digraphs? They prove that this is indeed true for "dense" matrices - having certain integer entries, and such that an associated quadratic form attains its maximum for the standard simplex uniquely at an interior point."
Reviewer:  G.Chaty
Classif.:  * 05C20 Directed graphs (digraphs)
                   05C35 Extremal problems (graph theory)
                   05C50 Graphs and matrices
Keywords:  extremal digraphs; Turán problem
Citations:  Zbl 559.00001

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page