Boundedness of optimal matrices in extremal multigraph and digraph problems

DOI10.1007/BF01202793MaRDI QIDQ2367447zbMATH OpenOpenAlexFDO

Publication date 16 August 1993

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01202793

asymptotically extremal dense matrices finite algorithm multigraphs multiplicity Ramsey numbers standard simplex

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Ramsey theory (05D10)

Review text

In a series of papers \textit{P. Erdős}, \textit{M. Simonovits} and the reviewer [J. Comb. Theory, Ser. B 15, 77-93 (1973; Zbl 0253.05124); Inverse extremal digraph problems, Finite and infinite sets, 6th Hung. Combin. Colloq., Eger/Hung. 1981, Vol. I, Colloq. Math. Soc. János Bolyai 37, 119-156 (1984; Zbl 0569.05023); Algorithm solution of extremal digraph problems, Trans. Am. Math. Soc. 292, 421-449 (1985; Zbl 0607.05040)] have considered Turán-type problems for multigraphs without loops. Certain of the ``asymptotically extremal sequences considered in those papers consist of multigraphs whose adjacencies can be represented by ``dense matrices: \(n\times n\) matrices with nonnegative entries not exceeding some integers \(q\) -- the multiplicity of the multigraphs under consideration -- whose associated quadratic form attains its maximum only in the interior of the standard simplex in \(\mathbb{R}^ n\). These matrices generalize the matrices associated with complete (ordinary) graphs in the ``new proof of Turán's theorem for ordinary graphs by \textit{T. S. Motzkin} and \textit{E. G. Straus} [Can. J. Math. 17, 533-540 (1965; Zbl 0129.399)]. In Theorem 2 the author determines a characterization of dense matrices. One question considered in the first paper of the series cited, and ultimately resolved for \(q=2\) in the third, concerned the existence of a finite algorithm to determine all dense matrices \(A\) whose associated sequences of multigraphs are ``asymptotically extremal for a given finite family \({\mathcal L}=\{L_ 1,L_ 2,\dots,L_ r\}\) of ``prohibited submultigraphs. To that end the three authors cited conjectured in the first paper cited that the numbers of rows and columns in such a matrix \(A\) would never exceed the product \(v(L_ 1)\cdot v(L_ 2)\cdot v(L_ r)\). The three authors subsequently proved (unpublished) that the product failed to be an upper bound, and succeeded in proving the existence of an algorithm without requiring an upper bound. In Theorem 3 the author proves, for \(q=2\), the existence of an upper bound related to certain Ramsey numbers. This yields a new proof of many of the results of the third paper cited. The main results of that paper applied only to the case \(q=2\), and depended on a lemma which, it was there suggested ``may be true for all \(q\). The author proves in Theorem 4 that the lemma does not generalize to cases \(q>2\). Extensions to oriented multigraphs are considered in \S4.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Boundedness of optimal matrices in extremal multigraph and digraph problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2367447)