Let $\mathcal B_n$ denote the set of $n\times n$ matrices with entries in $\{0,1\}$. It follows from the spectral radius formula that if $M\in\mathcal B_n$ is not nilpotent, then $\rho(M)$, the spectral radius of $M$, is $\ge1$.
I need a condition for $\rho(M)>1$ in terms of the proportion of 1s.
QUESTION. Is there a $c\in(0,1)$ such that for any $n\ge1$ and any $M\in\mathcal B_n$ with the number of 0s less than $cn^2$ we have $\rho(M)>1$?
If so, what's the best known value of $c$?
Perron-Frobenius theory clarifies this quickly. Observe first of all that if $M$ is irreducible in the sense that it cannot be made a block upper triangular matrix by a permutation of the standard basis vectors, then $\rho(M)>1$. This follows because the Perron-Frobenius eigenvector $x$ has positive entries, and if, say, $x_1>x_2> \ldots >x_n$, then $\lambda=1$ would force $M_{1j}=0$ for $j\ge 2$, so $M$ was reducible. A similar argument works if $x_1 = \ldots = x_m>x_{m+1} \ge \ldots$.
So $\rho(M)\le 1$ forces $M$ to be block upper triangular after a permutation of basis vectors and moreover the diagonal blocks must be zero or $1\times 1$ matrices (the argument in the preceding paragraph implicitly used that the matrix has size $n\ge 2$). Clearly such a matrix has $\ge (n^2-n)/2$ zeros, so any $c<1/2$ works. Moreover, we have also obtained an example with $(n^2-n)/2$ zeros and $\rho(M)=1$, so this is optimal.
