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 -