Typical large graphs with given edge and triangle densities. (English) Zbl 1517.05086
Summary: The analysis of large simple graphs with extreme values of the densities of edges and triangles has been extended to the statistical structure of typical graphs of fixed intermediate densities, by the use of large deviations of Erdős-Rényi graphs. We prove that the typical graph exhibits sharp singularities as the constraining densities vary between different curves of extreme values, and we determine the precise nature of the singularities. The extension to graphs with fixed densities of edges and \(k\)-cycles for odd \(k>3\) is straightforward and we note the simple changes in the proof.
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C42 | Density (toughness, etc.) |
| 60F10 | Large deviations |
| 60B20 | Random matrices (probabilistic aspects) |
| 60C05 | Combinatorial probability |
Software:
FlyspeckReferences:
| [1] | Augeri, F., Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs, Ann. Prob., 48, 5, 2404-2448 (2020) · Zbl 1456.60063 · doi:10.1214/20-AOP1427 |
| [2] | Bhattacharya, BB; Ganguly, S.; Lubetzky, E.; Zhao, Y., Upper tails and independence polynomials in random graphs, Adv. Math., 319, 313-347 (2017) · Zbl 1370.05099 · doi:10.1016/j.aim.2017.08.003 |
| [3] | Borgs, C.; Chayes, J.; Lovász, L.; Sós, VT; Vesztergombi, K., Convergent graph sequences I: subgraph frequencies, metric properties, and testing, Adv. Math., 219, 1801-1851 (2008) · Zbl 1213.05161 · doi:10.1016/j.aim.2008.07.008 |
| [4] | Borgs, C.; Chayes, J.; Lovász, L., Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal., 19, 1597-1619 (2010) · Zbl 1223.05193 · doi:10.1007/s00039-010-0044-0 |
| [5] | Chatterjee, S.; Dembo, A., Nonlinear large deviations, Adv. Math., 299, 396-450 (2016) · Zbl 1356.60045 · doi:10.1016/j.aim.2016.05.017 |
| [6] | Chatterjee, S.; Diaconis, P., Estimating and understanding exponential random graph models, Ann. Statist., 41, 2428-2461 (2013) · Zbl 1293.62046 · doi:10.1214/13-AOS1155 |
| [7] | Chatterjee, S.; Varadhan, SRS, The large deviation principle for the Erdős-Rényi random graph, Eur. J. Comb., 32, 1000-1017 (2011) · Zbl 1230.05259 · doi:10.1016/j.ejc.2011.03.014 |
| [8] | Cook, N.; Dembo, A., Large deviations of subgraph counts for sparse Erdős-Rényi graphs, Adv. Math., 373, 107289 (2020) · Zbl 1473.60058 · doi:10.1016/j.aim.2020.107289 |
| [9] | Eldan, R., Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations, Geom. Funct. Anal., 28, 6, 1548-1596 (2018) · Zbl 1428.60045 · doi:10.1007/s00039-018-0461-z |
| [10] | Ellis, R., Entropy, Large Deviations, and Statistical Mechanics (2006), Berlin: Springer-Verlag, Berlin · Zbl 1102.60087 · doi:10.1007/3-540-29060-5 |
| [11] | Hales, TC, Dense Sphere Packings (2012), Cambridge: Cambridge University Press, Cambridge · Zbl 1263.52001 · doi:10.1017/CBO9781139193894 |
| [12] | Harel, M., Mousset, F., Samotij, W.: Upper tails via high moments and entropic stability, arXiv preprint arXiv:1904.08212 (2019) · Zbl 1500.60002 |
| [13] | Kenyon, R.; Radin, C.; Ren, K.; Sadun, L., Multipodal structures and phase transitions in large constrained graphs, J. Stat. Phys., 168, 233-258 (2017) · Zbl 1376.82029 · doi:10.1007/s10955-017-1804-0 |
| [14] | Kenyon, R.; Radin, C.; Ren, K.; Sadun, L., The phases of large networks with edge and triangle constraints, J. Phys. A: Math. Theor., 50, 435001 (2017) · Zbl 1386.82015 · doi:10.1088/1751-8121/aa8ce1 |
| [15] | Kenyon, R.; Radin, C.; Ren, K.; Sadun, L., Bipodal structure in oversaturated random graphs, Int. Math. Res. Notices, 2016, 1009-1044 (2018) · Zbl 1404.05196 |
| [16] | Lanford, O.E.: Entropy and equilibrium states in classical statistical mechanics. In: Lenard, A. (eds.) Statistical Mechanics and Mathematical Problems, Battelle Seattle 1971 Rencontres, vol. 20 of Springer Lecture Notes in Physics, pp. 1-113. Springer-Verlag, Berlin/Heidelberg/New York (1973) |
| [17] | Lovász, L., Large Networks and Graph Limits (2012), Providence: American Mathematical Society, Providence · Zbl 1292.05001 · doi:10.1090/coll/060 |
| [18] | Lovász, L.; Szegedy, B., Limits of dense graph sequences, J. Combin. Theory Ser. B, 98, 933-957 (2006) · Zbl 1113.05092 · doi:10.1016/j.jctb.2006.05.002 |
| [19] | Lovász, L.; Szegedy, B., Szemerédi’s lemma for the analyst, GAFA, 17, 252-270 (2007) · Zbl 1123.46020 |
| [20] | Lovász, L.; Szegedy, B., Finitely forcible graphons, J. Combin. Theory Ser. B, 101, 269-301 (2011) · Zbl 1223.05248 · doi:10.1016/j.jctb.2011.03.005 |
| [21] | Löwen, H.: Fun with hard spheres, pages 295-331 in Statistical physics and spatial statistics : the art of analyzing and modeling spatial structures and pattern formation. In: Mecke, K.R., Stoyen, D. (eds.) Lecture Notes in Physics No. 554, Springer-Verlag, Berlin, (2000) |
| [22] | Neeman, J., Radin, C., Sadun, L.: Moderate deviations in triangle count, arXiv:2101.08249 (2021) |
| [23] | Pikhurko, O.; Razborov, A., Asymptotic structure of graphs with the minimum number of triangles, Combin. Probab. Comput., 26, 138-160 (2017) · Zbl 1371.05147 · doi:10.1017/S0963548316000110 |
| [24] | Radin, C.; Sadun, L., Phase transitions in a complex network, J. Phys. A: Math. Theor., 46 (2013) · Zbl 1314.82011 · doi:10.1088/1751-8113/46/30/305002 |
| [25] | Radin, C.; Sadun, L., Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys., 158, 853-865 (2015) · Zbl 1320.05064 · doi:10.1007/s10955-014-1151-3 |
| [26] | Razborov, A., On the minimal density of triangles in graphs, Combin. Probab. Comput., 17, 603-618 (2008) · Zbl 1170.05036 · doi:10.1017/S0963548308009085 |
| [27] | Turán, P., On an extremal problem in graph theory (in Hungarian), Matematikai é s Fizikai Lapok, 48, 436-452 (1941) · JFM 67.0732.03 |
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.
