Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T00:47:20.269Z Has data issue: false hasContentIssue false

THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE

Part of:Graph theory

Published online by Cambridge University Press:  20 April 2020

HONG LIU
Affiliation:
Mathematics Institute and DIMAP, University of Warwick, CoventryCV4 7AL, UK; h.liu.9@warwick.ac.uk, o.pikhurko@warwick.ac.uk
OLEG PIKHURKO
Affiliation:
Mathematics Institute and DIMAP, University of Warwick, CoventryCV4 7AL, UK; h.liu.9@warwick.ac.uk, o.pikhurko@warwick.ac.uk
KATHERINE STADEN
Affiliation:
Mathematical Institute, University of Oxford, OxfordOX2 6GG, UK; staden@maths.ox.ac.uk

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turán, Rademacher solved the first nontrivial case of this problem in 1941. The problem was revived by Erdős in 1955; it is now known as the Erdős–Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from $1$, which in this range confirms a conjecture of Lovász and Simonovits from 1975. Furthermore, we give a description of the extremal graphs.

MSC classification

Information

Type
Discrete Mathematics
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s) 2020