Modular statistics for subgraph counts in sparse random graphs. (English) Zbl 1307.05201
Summary: Answering a question of P. G. Kolaitis and S. Kopparty [J. ACM 60, No. 5, Paper No. 8, 34 p. (2013; Zbl 1280.03040)], we show that, for given integer \(q>1\) and pairwise nonisomorphic connected graphs \(G_1,\dots, G_k\), if \(p=p(n) \) is such that \(\Pr(G_{n,p}\supseteq G_i)\to 1\) \(\forall i\), then, with \(\xi_i\) the number of copies of \(G_i\) in \(G_{n,p}\), \((\xi_1,\dots, \xi_k)\) is asymptotically uniformly distributed on \(\mathbb Z_q^k\).
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C42 | Density (toughness, etc.) |
| 03C13 | Model theory of finite structures |
Citations:
Zbl 1280.03040References:
| [1] | L. Babai, N. Nisan and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, in Proc. 21st ACM Symposium on the Theory of Computing, 1989. · Zbl 0769.68040 |
| [2] | S. Janson, T. Luczak and A. Ruci´nski, Random Graphs, Wiley-Interscience, 2000. · Zbl 0968.05003 |
| [3] | S. Kopparty, personal communication. |
| [4] | P. G. Kolaitis and S. Kopparty, Random graphs and the parity quantifier, J. ACM, vol. 60 (5) Article 37, 2013. · Zbl 1280.03040 |
| [5] | S. Shelah and J. Spencer, Zero-one laws for sparse random graphs, J. Amer. Math. Soc. 1 (1988), 97-115. · Zbl 0647.05051 |
| [6] | J. Spencer, The Strange Logic of Random Graphs, Springer, 2001 · Zbl 0976.05001 |
| [7] | M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes ´Etudes Sci. Publ. Math. 81 (1995), 73-205. · Zbl 0864.60013 |
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.
