On stability of the Erdὅs–Rademacher problem

József Balogh, Felix Christian Clemen

Research output: Contribution to journalArticlepeer-review

Abstract

Mantel's theorem states that every n-vertex graph with [n2/4] + t edges, where t > 0, contains a triangle. The problem of determining the minimum number of triangles in such a graph is usually referred to as the Erdos-Rademacher problem. Lovasz and Simonovits proved that there are at least t [n/2] triangles in each of those graphs. Katona and Xiao considered the same problem under the additional condition that there are no s — 1 vertices covering all triangles. They settled the case t = 1 and s = 2. Solving their conjecture, we determine the minimum number of triangles for every fixed pair of s and t,when n is sufficiently large. Additionally, solving another conjecture of Katona and Xiao, we extend the theory for considering cliques instead of triangles.

Original languageEnglish (US)
Pages (from-to)1-11
Number of pages11
JournalIllinois Journal of Mathematics
Volume67
Issue number1
DOIs
StatePublished - Apr 2023

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'On stability of the Erdὅs–Rademacher problem'. Together they form a unique fingerprint.

Cite this