The Library
The exact minimum number of triangles in graphs with given order and size
Tools
Tools
Tools
Liu, Hong, Pikhurko, Oleg and Staden, Katherine (2020) The exact minimum number of triangles in graphs with given order and size. Forum of Mathematics, Pi, 8 . e8. doi:10.1017/fmp.2020.7 ISSN 2050-5086.
|
PDF
WRAP-exact-minimum-number-triangles-graphs-with-given-order-size-Liu-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (2705Kb) | Preview |
|
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-exact-minimum-number-triangles-graphs-Staden-2020.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (1357Kb) |
Official URL: https://doi.org/10.1017/fmp.2020.7
Abstract
What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turán, the first non-trivial case of this problem was solved by Rademacher in 1941, and 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.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Triangles | ||||
| Journal or Publication Title: | Forum of Mathematics, Pi | ||||
| Publisher: | Cambridge University Press | ||||
| ISSN: | 2050-5086 | ||||
| Official Date: | 20 April 2020 | ||||
| Dates: |
|
||||
| Volume: | 8 | ||||
| Article Number: | e8 | ||||
| DOI: | 10.1017/fmp.2020.7 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||
| Date of first compliant deposit: | 19 March 2020 | ||||
| Date of first compliant Open Access: | 23 March 2020 | ||||
| Related URLs: | |||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
