Abstract | We investigate important combinatorial and algorithmic properties of $G_n, m, p$ random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are ``rapidly mixing" (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is $\Theta(n \logn)$). All results are proved for $p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical $G_n, p$ random graphs. |