2023/10/12 by Jie Ma, Ma, Jie, Long‐Tu Yuan +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.08081
openalex publication_date 2023/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The supersaturation problem for a given graph F asks for the minimum number hF(n,q) of copies of F in an n-vertex graph with ex(n,F)+q edges. Subsequent works by Rademacher, Erdős, and Lovász and Simonovits determine the optimal range of q (which is linear in n) for cliques F such that hF(n,q) equals the minimum number tF(n,q) of copies of F obtained from a maximum F-free n-vertex graph by adding q new edges. A breakthrough result of Mubayi extends this line of research from cliques to color-critical graphs F, and this was further strengthened by Pikhurko and Yilma who established the equality hF(n,q)=tF(n,q) for 1≤ q≤ εF n and sufficiently large n. In this paper, we present several results on the supersaturation problem that extend beyond the existing framework. Firstly, we explicitly construct infinitely many graphs F with restricted properties for which hF(n,q)