Supersaturation for Hypergraph-Weighted Independent Sets

Abstract

Many extremal problems can be viewed as finding large independent sets in an auxiliary hypergraph. We propose a generalization of this by looking for ``large'' independent sets $I$ in a hypergraph $\mathcal{F}$ where ``large'' is measured by how many edges $I$ induces in another hypergraph $\mathcal{H}$ on the same vertex set as $\mathcal{F}$. We prove general supersaturation results for such extremal problems motivated by the breakthrough work of Ferber, McKinley and Samotij on counting $F$-free graphs. As applications, we prove new supersaturation bounds for generalized Turán problems, as well as supersaturation bounds for a new set of extremal problems inspired by work of Fox and Pohoata on finding subsets $A\subset \mathbb{N}$ which maximize the number of solutions to a given system of equations while avoiding solutions to another system.

22 pages, comments welcome!