The circular law for sparse random combinatorial matrices

Let ${\log }^{2+\epsilon }n\le d\le n\mathrm{/}2$ for some fixed $\epsilon \in (0,1)$, and let $M_n$ be an $n\times n$ random matrix with entries in $0,1$, where each row is independently and uniformly sampled from the set of all vectors in ${0,1}^n$ containing exactly $d$ ones. We show that the empirical spectral distribution of the appropriately rescaled matrix $M_n$ converges in probability to the circular law provided that $d=o(n)$. As a crucial element of the proof, we obtain quantitative lower bounds on the smallest singular value of the shifted matrices $M_n-z{I}_n$ whenever $\mathrm{\mid }z\mathrm{\mid }\le \sqrt{d}\log \log d$ and $C\log n\le d\le n\mathrm{/}2$ for some absolute positive constant $C$.