Graph decomposition and parity

DOI10.1002/JGT.21907MaRDI QIDQ3188670zbMATH OpenOpenAlexFDO

Authors B. DeMarco, Amanda Redlich

Publication date 12 August 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

asymptotic distributiontwo-component graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Motivated by a recent extension of the zero-one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph $G(n,p)$. We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo $q$. We determine the asymptotic distribution of all fixed two-component graphs in $G(n,p)$ for all $q$, and we give infinite families of many-component graphs with a uniform asymptotic distribution for all $q$. We also prove a negative result, that no simple proof of uniform asymptotic distribution for arbitrary graphs exists.

Recommendations

• Random graphs and the parity quantifier
• Random graphs and the parity quantifier
• Modular statistics for subgraph counts in sparse random graphs
• Zero-one \(k\)-law
• Distribution of subgraphs of random regular graphs

Cites work

• Random graphs and the parity quantifier
• Triangles in random graphs

Cited in

(9)

• The largest parity demigenus of a simple graph
• Anti-concentration for subgraph counts in random graphs
• Decomposing a graph into two subgraphs with prescribed parities of vertex degrees
• Uniform distribution for a class of k-paradoxical oriented graphs
• scientific article; zbMATH DE number 3889564 (Why is no real title available?)
• scientific article; zbMATH DE number 25257 (Why is no real title available?)
• Random graphs and the parity quantifier
• Random graphs and the parity quantifier
• Local limit theorems for subgraph counts

This page was built for publication: Graph decomposition and parity

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