Modular statistics for subgraph counts in sparse random graphs

MaRDI QIDQ2256135zbMATH OpenFDO

Authors B. DeMarco, Amanda Redlich, J. Kahn

Publication date 19 February 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.2264, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p37

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random graphsthresholdzero-one law

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Answering a question of Kolaitis and Kopparty, we show that, for given integer $q>1$ and pairwise nonisomorphic connected graphs $G_1\mathrm{...}{G}_k$, if $p=p(n)$ is such that $Pr(G_{n,p}supseteq{G}_i)o1$ $foralli$, then, with $x{i}_i$ the number of copies of $G_i$ in $G_{n,p}$, $(x{i}_1\mathrm{...}x{i}_k)$ is asymptotically uniformly distributed on $$.

Review text

Summary: Answering a question of \textit{P. G. Kolaitis} and \textit{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\).

Recommendations

• Subgraph counts in random graphs using incomplete U-statistics methods
• The probability of non-existence of a subgraph in a moderately sparse random graph
• Distribution of subgraphs of random regular graphs
• Subgraph distributions in dense random regular graphs
• Distributions of sparse spanning subgraphs in random graphs

Cites work

• Concentration of measure and isoperimetric inequalities in product spaces
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Random graphs and the parity quantifier
• The strange logic of random graphs
• Zero-One Laws for Sparse Random Graphs

Cited in

(7)

• Anti-concentration for subgraph counts in random graphs
• Graph decomposition and parity
• Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges
• A local central limit theorem for triangles in a random graph
• The complexity of the Approximate Multiple Pattern Matching Problem for random strings
• On the maximum \(F_5\)-free subhypergraphs of a random hypergraph
• Variance of the subgraph count for sparse Erdős-Rényi graphs

This page was built for publication: Modular statistics for subgraph counts in sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256135)