The exact minimum number of triangles in graphs with given order and size
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 attracti...
| Main Authors: | , , |
|---|---|
| Formato: | Journal article |
| Idioma: | English |
| Publicado: |
Cambridge University Press
2020
|
| _version_ | 1826277165499416576 |
|---|---|
| author | Liu, H Pikhurko, O Staden, K |
| author_facet | Liu, H Pikhurko, O Staden, K |
| author_sort | Liu, H |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T23:24:48Z |
| format | Journal article |
| id | oxford-uuid:69fe6902-bd04-4a24-a4ba-c74b8dc72129 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:24:48Z |
| publishDate | 2020 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | oxford-uuid:69fe6902-bd04-4a24-a4ba-c74b8dc721292022-03-26T18:54:36ZThe exact minimum number of triangles in graphs with given order and sizeJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:69fe6902-bd04-4a24-a4ba-c74b8dc72129EnglishSymplectic ElementsCambridge University Press2020Liu, HPikhurko, OStaden, KWhat 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. |
| spellingShingle | Liu, H Pikhurko, O Staden, K The exact minimum number of triangles in graphs with given order and size |
| title | The exact minimum number of triangles in graphs with given order and size |
| title_full | The exact minimum number of triangles in graphs with given order and size |
| title_fullStr | The exact minimum number of triangles in graphs with given order and size |
| title_full_unstemmed | The exact minimum number of triangles in graphs with given order and size |
| title_short | The exact minimum number of triangles in graphs with given order and size |
| title_sort | exact minimum number of triangles in graphs with given order and size |
| work_keys_str_mv | AT liuh theexactminimumnumberoftrianglesingraphswithgivenorderandsize AT pikhurkoo theexactminimumnumberoftrianglesingraphswithgivenorderandsize AT stadenk theexactminimumnumberoftrianglesingraphswithgivenorderandsize AT liuh exactminimumnumberoftrianglesingraphswithgivenorderandsize AT pikhurkoo exactminimumnumberoftrianglesingraphswithgivenorderandsize AT stadenk exactminimumnumberoftrianglesingraphswithgivenorderandsize |