On subgraphs with degrees of prescribed residues in the random graph

Abstract: We show that with high probability the random graph

G_{n, 1 / 2}

has an induced subgraph of linear size, all of whose degrees are congruent to

r p m o d q

for any fixed

r

and

q g e q 2

. More generally, the same is true for any fixed distribution of degrees modulo

q

. Finally, we show that with high probability we can partition the vertices of

G_{n, 1 / 2}

into

q + 1

parts of nearly equal size, each of which induces a subgraph all of whose degrees are congruent to

r p m o d q

. Our results resolve affirmatively a conjecture of Scott, who addressed the case

q = 2

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: On subgraphs with degrees of prescribed residues in the random graph