Regular graphs with many triangles are structured. (English) Zbl 1481.05142
Summary: 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 P. Collet and J. P. Eckmann [J. Stat. Phys. 109, No. 5–6, 923–943 (2002; Zbl 1011.05028)] and considerably strengthens their observation that the triangles cannot be totally scattered in typical instances of regular graphs with many triangles.
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 P. Collet and J. P. Eckmann [J. Stat. Phys. 109, No. 5–6, 923–943 (2002; Zbl 1011.05028)] and considerably strengthens their observation that the triangles cannot be totally scattered in typical instances of regular graphs with many triangles.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C30 | Enumeration in graph theory |
| 05C75 | Structural characterization of families of graphs |
| 60C05 | Combinatorial probability |
Citations:
Zbl 1011.05028References:
| [1] | Fanny Augeri. Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erd˝os-R´enyi graphs.arXiv:1810.01558, 2018. · Zbl 1417.60005 |
| [2] | Sourav Chatterjee. The missing log in large deviations for triangle counts.Random Structures & Algorithms, 40(4):437-451, 2012. · Zbl 1246.05140 |
| [3] | Sourav Chatterjee and Amir Dembo. Nonlinear large deviations.Advances in Mathematics, 299:396-450, 2016. · Zbl 1356.60045 |
| [4] | Sourav Chatterjee and S. R. Srinivasa Varadhan. The large deviation principle for the Erd˝os-R´enyi random graph.European Journal of Combinatorics, 32(7):1000 - 1017, 2011. Homomorphisms and Limits. · Zbl 1230.05259 |
| [5] | Pierre Collet and Jean-Pierre Eckmann. The number of large graphs with a positive density of triangles.Journal of Statistical Physics, 109(5):923-943, 2002. · Zbl 1011.05028 |
| [6] | Nicholas Cook and Amir Dembo. Large deviations of subgraph counts for sparse Erd˝os-R´enyi graphs.Advances in Mathematics, 373:107289, 2020. · Zbl 1473.60058 |
| [7] | Bobby DeMarco and Jeff Kahn. Upper tails for triangles.Random Structures & Algorithms, 40(4):452-459, 2011. · Zbl 1246.05142 |
| [8] | Matan Harel, Frank Mousset, and Wojciech Samotij. Upper tails via high moments and entropic stability.arXiv:1904.08212, 2019. |
| [9] | Svante Janson, Krzysztof Oleszkiewicz, and Andrzej Ruci´nski. Upper tails for subgraph counts in random graphs.Israel Journal of Mathematics, 142(1):61-92, 2004. · Zbl 1055.05136 |
| [10] | Svante Janson and Andrzej Ruci´nski. The infamous upper tail.Random Structures & Algorithms, 20(3):317-342, 2002. · Zbl 0996.60023 |
| [11] | Svante Janson and Andrzej Ruci´nski. The deletion method for upper tail estimates. Combinatorica, 24(4):615-640, 2004. · Zbl 1074.60006 |
| [12] | Richard Kenyon, Charles Radin, Kui Ren, and Lorenzo Sadun. Bipodal structure in oversaturated random graphs.International Mathematics Research Notices, page rnw261, 2016. · Zbl 1404.05196 |
| [13] | Richard Kenyon, Charles Radin, Kui Ren, and Lorenzo Sadun. The phases of large networks with edge and triangle constraints.Journal of Physics A: Mathematical and Theoretical, 50(43):435001, 2017. · Zbl 1386.82015 |
| [14] | Jeong Han Kim, Benny Sudakov, and Van Vu. Small subgraphs of random regular graphs.Discrete Mathematics, 307(15):1961-1967, 2007. · Zbl 1118.05088 |
| [15] | Jeong Han Kim and Van H. Vu. Divide and conquer martingales and the number of triangles in a random graph.Random Structures & Algorithms, 24(2):166-174, 2004. · Zbl 1041.60042 |
| [16] | Dmitri Krioukov. Clustering implies geometry in networks.Physical review letters, 116(20):208302, 2016. |
| [17] | Eyal Lubetzky and Yufei Zhao. On replica symmetry of large deviations in random graphs.Random Structures & Algorithms, 47(1):109-146, 2015. · Zbl 1348.05195 |
| [18] | Eyal Lubetzky and Yufei Zhao. On the variational problem for upper tails in sparse random graphs.Random Structures & Algorithms, 50(3):420-436, 2017. · Zbl 1364.05063 |
| [19] | Brendan D. McKay and Nicholas C. Wormald. Asymptotic enumeration by degree sequence of graphs with degreeso(n1/2).Combinatorica, 11(4):369-382, 1991. · Zbl 0742.05047 |
| [20] | Charles Radin, Kui Ren, and Lorenzo Sadun. The asymptotics of large constrained graphs.Journal of Physics A: Mathematical and Theoretical, 47(17):175001, 2014. · Zbl 1290.05139 |
| [21] | Charles Radin and Lorenzo Sadun. Phase transitions in a complex network.Journal of Physics A: Mathematical and Theoretical, 46(30):305002, 2013. · Zbl 1314.82011 |
| [22] | Van H. Vu. A large deviation result on the number of small subgraphs of a random graph.Combinatorics, Probability and Computing, 10(1):79-94, 2001 · Zbl 0982.05092 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
