MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 Replaced k by k+1 in the size of the block, since the block starts at size 2 if you start at an off-diagonal entry.

Also in the "a little too involved for a comment" class: A matrix that's this sparse is usually going to be a block diagonal matrix with very small blocks.

Let $k$ be any fixed constant, and suppose that your matrix contains no $k+1 \times k+1$ principal submatrix with at least $k$ nonzero entries. Then your matrix has a block decomposition with all blocks having size at most $k$ k+1$ (If you start with a given diagonal nonzero entry and "grow" it by adding entries in the same row/column as an entry already added, you'll stop by the time you've reached $k-1$ added entries, and each addition increases the size of your block by at most $1$). In this case we can upper bound the probably a submatrix of this size exists by $$\binom{n}{k+1} \binom{(k+1)^2}{k} p^{k} \leq C_k n^{k+1-k \beta}$$ Which goes to $0$ for any $\beta$ in your range if $k$ sufficiently large.

This means you'll usually see singular vectors with very small support, and that the $\sigma_2$ should be much larger than $\sqrt{np}$ (maybe equal to $\sigma_1$ in most cases?) You might be able to get something more explicit by enumerating all the possible structures of blocks and the expected number of occurrences of each.

show/hide this revision's text 1

Also in the "a little too involved for a comment" class: A matrix that's this sparse is usually going to be a block diagonal matrix with very small blocks.

Let $k$ be any fixed constant, and suppose that your matrix contains no $k+1 \times k+1$ principal submatrix with at least $k$ nonzero entries. Then your matrix has a block decomposition with all blocks having size at most $k$ (If you start with a given diagonal entry and "grow" it by adding entries in the same row/column as an entry already added, you'll stop by the time you've reached $k-1$ added entries, and each addition increases the size of your block by at most $1$). In this case we can upper bound the probably a submatrix of this size exists by $$\binom{n}{k+1} \binom{(k+1)^2}{k} p^{k} \leq C_k n^{k+1-k \beta}$$ Which goes to $0$ for any $\beta$ in your range if $k$ sufficiently large.

This means you'll usually see singular vectors with very small support, and that the $\sigma_2$ should be much larger than $\sqrt{np}$ (maybe equal to $\sigma_1$ in most cases?) You might be able to get something more explicit by enumerating all the possible structures of blocks and the expected number of occurrences of each.