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

thresholdrandom graphszero-one law

Mathematics Subject Classification ID

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

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 $$.

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

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Concentration of measure and isoperimetric inequalities in product spaces
• 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)

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

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)