Extremal problems for multigraphs

Abstract

An $(n,s,q)$-graph is an $n$-vertex multigraph in which every $s$-set of vertices spans at most $q$ edges. Turán-type questions on the maximum of the sum of the edge multiplicities in such multigraphs have been studied since the 1990s. More recently, Mubayi and Terry [An extremal problem with a transcendental solution, Combinatorics Probability and Computing 2019] posed the problem of determining the maximum of the product of the edge multiplicities in $(n,s,q)$-graphs. We give a general lower bound construction for this problem for many pairs $(s,q)$, which we conjecture is asymptotically best possible. We prove various general cases of our conjecture, and in particular we settle a conjecture of Mubayi and Terry on the $(s,q)=(4,6a+3)$ case of the problem (for $a\ge 2$); this in turn answers a question of Alon. We also determine the asymptotic behaviour of the problem for `sparse' multigraphs (i.e. when $q\le 2\left(\genfrac{}{}{0ex}{}{s}{2}\right)$). Finally we introduce some tools that are likely to be useful for attacking the problem in general.

arXiv comment35 pages, 2 figures, author accepted manuscript, to appear in JCTB