Extremal Problems for Multigraphs

Abstract

In this thesis, we study the Mubayi-Terry multigraph problem, wherein one seeks to maximise the product of edge multiplicities in a locally sparse multigraph. A multigraph G is called an (s,q) graph if every set of s vertices in G spans at most q edges (counting multiplicities). The problem of determining the maximum sum of edge multiplicities in an n-vertex (s,q) graph is the multigraph analogue of a classical problem in extremal graph theory, which has been studied extensively over the years. More recently, in 2019, Mubayi and Terry introduced the product version of this problem, for which much less is known. The Mubayi-Terry problem is motivated by attempts to develop counting theorems for multigraphs.

Our primary contribution is to resolve the Mubayi-Terry multigraph problem for new infinite families of pairs (s,q). We prove the optimality of a broad class of lower-bound multigraph constructions for this problem. In so doing, we obtain an asymptotic resolution of a conjecture by Day, Falgas-Ravry and Treglown, and vastly generalise previous results on the problem. Our arguments are highly structural, a feature we then leverage to obtain stability results.