Boundedness of optimal matrices in extremal multigraph and digraph problems (Q2367447)

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.