Supersaturation for Subgraph Counts

Jonathan Cutler, Jd Nir, A. J. Radcliffe

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The classical extremal problem is that of computing the maximum number of edges in an F-free graph. In particular, Turán’s theorem entirely resolves the case where F= Kr+1. Later results, known as supersaturation theorems, proved that in a graph containing more edges than the extremal number, there must also be many copies of Kr+1. Alon and Shikhelman introduced a broader class of extremal problems, asking for the maximum number of copies of a graph T in an F-free graph (so that T= K2 is the classical extremal number). In this paper we determine some of these generalized extremal numbers when T and F are stars or cliques and prove some supersaturation results for them.

Original languageEnglish
Article number65
JournalGraphs and Combinatorics
Volume38
Issue number3
DOIs
StatePublished - Jun 2022

Keywords

  • Extremal graph theory
  • Generalized Turán problem
  • Supersaturation

Fingerprint

Dive into the research topics of 'Supersaturation for Subgraph Counts'. Together they form a unique fingerprint.

Cite this