Premium
Graph Decomposition and Parity
Author(s) -
DeMarco Bobby,
Redlich Amanda
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21907
Subject(s) - mathematics , combinatorics , modulo , discrete mathematics , graph , random graph , voltage graph , parity (physics) , modular decomposition , line graph , pathwidth , physics , particle physics
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 recursive proof of the simplest form exists for a uniform asymptotic distribution for arbitrary graphs.