Counting partitions of Gn,1/2 {G}_{n,1/2} with degree congruence conditions

Abstract: For

G = G_{n, 1 / 2}

, the ErdH{o}s--Renyi random graph, let

X_{n}

be the random variable representing the number of distinct partitions of

V (G)

into sets

A_{1}, l d o t s, A_{q}

so that the degree of each vertex in

G [A_{i}]

is divisible by

q

for all

i i n [q]

. We prove that if

q g e q 3

is odd then

X_{n} x r i g h t a r r o w d m a t h r m P o (1 / q!)

, and if

q g e q 4

is even then

X_{n} x r i g h t a r r o w d m a t h r m P o (2^{q} / q!)

. More generally, we show that the distribution is still asymptotically Poisson when we require all degrees in

G [A_{i}]

to be congruent to

x_{i}

modulo

q

for each

i i n [q]

, where the residues

x_{i}

may be chosen freely. For

q = 2

, the distribution is not asymptotically Poisson, but it can be determined explicitly.

Cites Work

This page was built for publication: Counting partitions of Gn,1/2$$ {G}_{n,1/2} $$ with degree congruence conditions