Unified approach to the generalized Turán problem and supersaturation

Abstract

In this paper we introduce a unifying approach to the generalized Turán problem and supersaturation results in graph theory. The supersaturation-extremal function $satex(n,F:m,G)$ is the least number of copies of a subgraph $G$ an $n$-vertex graph can have, which contains at least $m$ copies of $F$ as a subgraph. We present a survey, discuss previously known results and obtain several new ones focusing mainly on proof methods, extremal structure and phase transition phenomena. Finally we point out some relation with extremal questions concerning hypergraphs, particularly Berge-type results.

arXiv comment16 pages