Replica symmetry in upper tails of mean-field hypergraphs. (English) Zbl 1434.60050
Summary: Given a sequence of \(s\)-uniform hypergraphs \(\{H_n\}_{n\geq 1}\), denote by \(T_p( H_n)\) the number of edges in the random induced hypergraph obtained by including every vertex in \(H_n\) independently with probability \(p \in(0, 1)\). Recent advances in the large deviations of low complexity non-linear functions of independent Bernoulli variables can be used to show that tail probabilities of \(T_p(H_n)\) are precisely approximated by the so-called ‘mean-field’ variational problem, under certain assumptions on the sequence \(\{H_n\}_{n\geq 1}\). In this paper, we study properties of this variational problem for the upper tail of \(T_p(H_n)\), assuming that the mean-field approximation holds. In particular, we show that the variational problem has a universal replica symmetric phase (where it is uniquely minimized by a constant function), for any sequence of regular s-uniform hypergraphs, which depends only on \(s\). We also analyze the associated variational problem for the related problem of estimating subgraph frequencies in a converging sequence of dense graphs. Here, the variational problems themselves have a limit which can be expressed in terms of the limiting graphon, which gives the exact Bahadur slope of the corresponding estimate.
MSC:
| 60C05 | Combinatorial probability |
| 05C65 | Hypergraphs |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60F10 | Large deviations |
References:
| [1] | Augeri, F., Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdős-Rényi graphs, Ann. Probab. (2020), in press · Zbl 1456.60063 |
| [2] | Austin, T., The structure of low-complexity Gibbs measures on product spaces, Ann. Probab., 47, 6, 4002-4023 (2019) · Zbl 1444.60006 |
| [3] | Bahadur, R. R., Rates of convergence of estimates and test statistics, Ann. Math. Stat., 38, 2, 303-324 (1967) · Zbl 0201.52106 |
| [4] | Basak, A.; Mukherjee, S., Universality of the mean-field for the Potts model, Probab. Theory Relat. Fields, 168, 3-4, 557-600 (2017) · Zbl 1369.60066 |
| [5] | Bhamidi, S.; Bresler, G.; Sly, A., Mixing time of exponential random graphs, Ann. Appl. Probab., 21, 6, 2146-2170 (2011) · Zbl 1238.60011 |
| [6] | Bhamidi, S.; Chakraborty, S.; Cranmer, S.; Desmarais, B., Weighted exponential random graph models: scope and large network limits, J. Stat. Phys., 173, 3-4, 704-735 (2018) · Zbl 1403.60014 |
| [7] | Bhattacharya, B. B.; Ganguly, S.; Lubetzky, E.; Zhao, Y., Upper tails and independence polynomials in random graphs, Adv. Math., 319, 313-347 (2017) · Zbl 1370.05099 |
| [8] | Bhattacharya, B. B.; Ganguly, S.; Shao, X.; Zhao, Y., Upper tails for arithmetic progressions in a random set, Int. Math. Res. Not., 2020, 1, 167-213 (2020) · Zbl 1478.11012 |
| [9] | Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K., Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math., 219, 6, 1801-1851 (2008) · Zbl 1213.05161 |
| [10] | Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K., Convergent sequences of dense graphs II. Multiway cuts and statistical physics, Ann. Math. (2), 176, 1, 151-219 (2012) · Zbl 1247.05124 |
| [11] | Briët, J.; Gopi, S., Gaussian width bounds with applications to arithmetic progressions in random settings, Int. Math. Res. Not. (2020), in press · Zbl 1470.11014 |
| [12] | Chatterjee, S., Large Deviations for Random Graphs: École d’Été de Probabilités de Saint-Flour XLV-2015, vol. 2197 (2017), Springer · Zbl 1375.60009 |
| [13] | Chatterjee, S.; Dembo, A., Nonlinear large deviations, Adv. Math., 299, 396-450 (2016) · Zbl 1356.60045 |
| [14] | Chatterjee, S.; Diaconis, P., Estimating and understanding exponential random graph models, Ann. Stat., 41, 5, 2428-2461 (2013) · Zbl 1293.62046 |
| [15] | Chatterjee, S.; Varadhan, S. R.S., The large deviation principle for the Erdős-Rényi random graph, Eur. J. Comb., 32, 7, 1000-1017 (2011) · Zbl 1230.05259 |
| [16] | Cook, N.; Dembo, A., Large deviations of subgraph counts for sparse Erdős-Rényi graphs (2018) · Zbl 1473.60058 |
| [17] | Dembo, A.; Lubetzky, E., A large deviation principle for the Erdős-Rényi uniform random graph, Electron. Commun. Probab., 23 (2018) · Zbl 1398.05179 |
| [18] | Eldan, R., Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations, Geom. Funct. Anal., 28, 1548-1596 (2018) · Zbl 1428.60045 |
| [19] | Janson, S.; Ruciński, A., Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs, Ark. Mat., 49, 1, 79-96 (2011) · Zbl 1223.05201 |
| [20] | Kenyon, R.; Radin, C.; Ren, K.; Sadun, L., Multipodal structure and phase transitions in large constrained graphs, J. Stat. Phys., 168, 2, 233-258 (2017) · Zbl 1376.82029 |
| [21] | Klusowski, J. M.; Wu, Y., Counting motifs with graph sampling, (Proceedings of the 31st Conference on Learning Theory, vol. 75 (2018)), 1966-2011 |
| [22] | Lovász, L., Very large graphs, (Current Developments in Mathematics, 2008 (2009), Int. Press: Int. Press Somerville, MA), 67-128 · Zbl 1179.05100 |
| [23] | Lubetzky, E.; Zhao, Y., On replica symmetry of large deviations in random graphs, Random Struct. Algorithms, 47, 1, 109-146 (2015) · Zbl 1348.05195 |
| [24] | Lubetzky, E.; Zhao, Y., On the variational problem for upper tails in sparse random graphs, Random Struct. Algorithms, 50, 3, 420-436 (2017) · Zbl 1364.05063 |
| [25] | Radin, C.; Ren, K.; Sadun, L., A symmetry breaking transition in the edge/triangle network model, Ann. Inst. Henri Poincaré D, 5, 2, 251-286 (2018) · Zbl 1390.05218 |
| [26] | Radin, C.; Yin, M., Phase transitions in exponential random graphs, Ann. Appl. Probab., 23, 6, 2458-2471 (2013) · Zbl 1278.05225 |
| [27] | Warnke, L., Upper tails for arithmetic progressions in random subsets, Isr. J. Math., 221, 317-365 (2017) · Zbl 1407.05238 |
| [28] | Yan, J., Nonlinear large deviations: beyond the hypercube, Ann. Appl. Probab. (2018), in press |
| [29] | Yin, M.; Rinaldo, A.; Fadnavis, S., Asymptotic quantization of exponential random graphs, Ann. Appl. Probab., 26, 6, 3251-3285 (2016) · Zbl 1356.05138 |
| [30] | Zhao, Y., On the lower tail variational problem for random graphs, Comb. Probab. Comput., 26, 2, 301-320 (2017) · Zbl 1371.05274 |
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.
