A critical probability for biclique partition of G_n,p

Abstract: The biclique partition number of a graph

G = (V, E)

, denoted

b p (G)

, is the minimum number of pairwise edge disjoint complete bipartite subgraphs of

G

so that each edge of

G

belongs to exactly one of them. It is easy to see that

b p (G) l e q n - a l p h a (G)

, where

a l p h a (G)

is the maximum size of an independent set of

G

. ErdH{o}s conjectured in the 80's that for almost every graph

G

equality holds; i.e., if

G = G_{n, 1 / 2}

then

b p (G) = n - a l p h a (G)

with high probability. Alon showed that this is false. We show that the conjecture of ErdH{o}s is true if we instead take

G = G_{n, p}

, where

p

is constant and less than a certain threshold value

p_{0} a p p r o x 0.312

. This verifies a conjecture of Chung and Peng for these values of

p

. We also show that, if

p_{0} < p < 1 / 2

, then

b p (G_{n, p}) = n - (1 + T h e t a (1)) a l p h a (G_{n, p})

with high probability.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: A critical probability for biclique partition of \(G_{n,p}\)