The edges of the random graph (with the edge probability
p=1/2) can be covered using
O(n
2lnln
n/(ln
n)
2) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1–
)
n
2/(2lg
n)
2.
AMS subject classification code (1991) 05 C 80
Research supported in part by ONR Grant N00014-85K0570 and by NSA/MSP Grant MDA904-90-H-4011.