TY - JOUR

T1 - On stability of the Erdὅs–Rademacher problem

AU - Balogh, József

AU - Clemen, Felix Christian

N1 - Publisher Copyright:
© 2023 by the University of Illinois Urbana-Champaign.

PY - 2023/4

Y1 - 2023/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85159653903&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85159653903&partnerID=8YFLogxK

U2 - 10.1215/00192082-10429321

DO - 10.1215/00192082-10429321

M3 - Article

AN - SCOPUS:85159653903

SN - 0019-2082

VL - 67

SP - 1

EP - 11

JO - Illinois Journal of Mathematics

JF - Illinois Journal of Mathematics

IS - 1

ER -