  We investigate certain structural properties of random interdependent
networks. We start by studying a property known as $r$-robustness, which is a
strong indicator of the ability of a network to tolerate structural
perturbations and dynamical attacks. We show that random $k$-partite graphs
exhibit a threshold for $r$-robustness, and that this threshold is the same as
the one for the graph to have minimum degree $r$. We then extend this
characterization to random interdependent networks with arbitrary intra-layer
topologies. Finally, we characterize the algebraic connectivity of such
networks, and provide an asymptotically tight rate of growth of this quantity
for a certain range of inter-layer edge formation probabilities. Our results
arise from a characterization of the isoperimetric constant of random
interdependent networks, and yield new insights into the structure and
robustness properties of such networks.
