2016/08/31 by Mubayi, Dhruv, Terry, Caroline
#05A16 #05C30 #05C35 #05D99 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1608.08948
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\choose 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 an2+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-Tuza and Füredi-Kündgen 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 and to prove logical 0-1 laws for (n,s,q)-graphs. Our work therefore extends many classical enumerative results in extremal graph theory beginning with the Erdős-Kleitman-Rothschild theorem to multigraphs.