Abstract | In this paper we examine spectral properties of random intersection graphs when the number
of vertices is equal to the number of labels. We call this class symmetric random intersection graphs.
We examine symmetric random intersection graphs when the probability that a vertex selects a label
is close to the connectivity threshold ¿c. In particular, we examine the size of the second eigenvalue of
the transition matrix corresponding to the Markov Chain that describes a random walk on an instance
of the symmetric random intersection graph Gn,n,p. We show that with high probability the second
eigenvalue is upper bounded by some constant ³ < 1. |