2020/03/29 by József Balogh, Felix Christian Clemen, Balogh, József +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2003.12917
Mantel's theorem states that every n-vertex graph with \lfloor (n2)/(4) \rfloor +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 Erdős-Rademacher problem. Lovász and Simonovits proved that there are at least t\lfloor n/2 \rfloor 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.