Regular Graphs with Many Triangles are Structured
<jats:p>We compute the leading asymptotics of the logarithm of the number of $d$-regular graphs having at least a fixed positive fraction $c$ of the maximum possible number of triangles, and provide a strong structural description of almost all such graphs.
 When $d$ is constant, we...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
The Electronic Journal of Combinatorics
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145810 |
| _version_ | 1811080067462201344 |
|---|---|
| author | Van der Hoorn, Pim Lippner, Gabor Mossel, Elchanan |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Van der Hoorn, Pim Lippner, Gabor Mossel, Elchanan |
| author_sort | Van der Hoorn, Pim |
| collection | MIT |
| description | <jats:p>We compute the leading asymptotics of the logarithm of the number of $d$-regular graphs having at least a fixed positive fraction $c$ of the maximum possible number of triangles, and provide a strong structural description of almost all such graphs.
When $d$ is constant, we show that such graphs typically consist of many disjoint $(d+1)$-cliques and an almost triangle-free part. When $d$ is allowed to grow with $n$, we show that such graphs typically consist of very dense sets of size $d+o(d)$ together with an almost triangle-free part.
This confirms a conjecture of Collet and Eckmann from 2002 and considerably strengthens their observation that the triangles cannot be totally scattered in typical instances of regular graphs with many triangles.</jats:p> |
| first_indexed | 2024-09-23T11:25:15Z |
| format | Article |
| id | mit-1721.1/145810 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:25:15Z |
| publishDate | 2022 |
| publisher | The Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/1458102022-10-13T03:29:06Z Regular Graphs with Many Triangles are Structured Van der Hoorn, Pim Lippner, Gabor Mossel, Elchanan Massachusetts Institute of Technology. Department of Mathematics <jats:p>We compute the leading asymptotics of the logarithm of the number of $d$-regular graphs having at least a fixed positive fraction $c$ of the maximum possible number of triangles, and provide a strong structural description of almost all such graphs.
 When $d$ is constant, we show that such graphs typically consist of many disjoint $(d+1)$-cliques and an almost triangle-free part. When $d$ is allowed to grow with $n$, we show that such graphs typically consist of very dense sets of size $d+o(d)$ together with an almost triangle-free part.
 This confirms a conjecture of Collet and Eckmann from 2002 and considerably strengthens their observation that the triangles cannot be totally scattered in typical instances of regular graphs with many triangles.</jats:p> 2022-10-12T18:39:18Z 2022-10-12T18:39:18Z 2022 2022-10-12T18:33:48Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/145810 Van der Hoorn, Pim, Lippner, Gabor and Mossel, Elchanan. 2022. "Regular Graphs with Many Triangles are Structured." The Electronic Journal of Combinatorics, 29 (1). en 10.37236/10369 The Electronic Journal of Combinatorics Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf The Electronic Journal of Combinatorics The Electronic Journal of Combinatorics |
| spellingShingle | Van der Hoorn, Pim Lippner, Gabor Mossel, Elchanan Regular Graphs with Many Triangles are Structured |
| title | Regular Graphs with Many Triangles are Structured |
| title_full | Regular Graphs with Many Triangles are Structured |
| title_fullStr | Regular Graphs with Many Triangles are Structured |
| title_full_unstemmed | Regular Graphs with Many Triangles are Structured |
| title_short | Regular Graphs with Many Triangles are Structured |
| title_sort | regular graphs with many triangles are structured |
| url | https://hdl.handle.net/1721.1/145810 |
| work_keys_str_mv | AT vanderhoornpim regulargraphswithmanytrianglesarestructured AT lippnergabor regulargraphswithmanytrianglesarestructured AT mosselelchanan regulargraphswithmanytrianglesarestructured |