EXTREMAL THEORY OF LOCALLY SPARSE MULTIGRAPHS

摘要

An (n, s, q)-graph is an n-vertex multigraph where every set of s vertices spans at most q edges. In this paper, we determine the maximum product of the edge multiplicities in (n, s, q)-graphs if the congruence class of q modulo (s 2) is in a certain interval of length about 3s/2. The smallest case that falls outside this range is (s, q) = (4,15), and here the answer is a(n2+o(n2)), where a is transcendental assuming Schanuel's conjecture. This could indicate the difficulty of solving the problem in full generality. Many of our results can be seen as extending work by Bondy and Tuza [J. Graph Theory, 25 (1997), pp. 267-275] and Furedi and Kundgen [J. Graph Theory, 40 (2002), pp. 195-225] about sums of edge multiplicities to the product setting. We also prove a variety of other extremal results for (n, s, q) -graphs, including product-stability theorems. These results are of additional interest because they can be used to enumerate (n, s, q) -graphs. Our work therefore extends many classical enumerative results in extremal graph theory beginning with the Erdos Kleitman Rothschild theorem [Asymptotic enumeration of K-n-free graphs, in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei 17, Accad. Naz. Lincei, Rome, 1976, pp. 19-27] to multigraphs.