Modular statistics for subgraph counts in sparse random graphs

zbMATH Open1307.05201arXiv1402.2264MaRDI QIDQ2256135FDOQ2256135

Authors: B. DeMarco, Amanda Redlich, J. Kahn 

Publication date: 19 February 2015

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

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

Full work available at URL: https://arxiv.org/abs/1402.2264

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

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

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)

Cites Work

• Title not available (Why is that?)
• The strange logic of random graphs
• Zero-One Laws for Sparse Random Graphs
• 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

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)