Let $M \in \{0, 1\}^{n\times n}$.
Given a *constant* integer $c \ge 2$, let the number of $1$s in each row be equal to $\frac{n}{c}$ (assuming $c$ is a divisor of $n$). Let $\mathcal{M}_c$ be the set of such matrices.

Given a *constant* $\beta \in (0,1)$ and a matrix $M \in \mathcal{M}_c$, we say that "a row vector $r$ of $M$ is $\beta$-*covered*" if the number of row vectors $r'$ of $M$ such that $\,r' r^{\top} \ge \frac{n}{c^2}\,$ is greater than $n^{\beta}$.

**Question**: When $n$ approaches infinity, what is the **minimum** number $N$ of $\beta$-covered rows of a matrix in $\mathcal{M}_c$? -- (My conjecture is $N=n-\Theta(n^{\beta})$).

## ---

PS: My previous questions 0-1 matrix combinatorial problem and A combinatorial 0-1 matrix problem arose from this problem.

strictlysmaller than $n/4$. Could you please describe it? I now designed a method to create, when $n=c^m$, $\sum_{i=1}^{m} c^{(c^i)}$ vectors with $n/c$ ones such that the pairwise overlap is exactly $n/c^2$ (perhaps this method listsallvectors satisfying these properties "with the equality"). However I cannot see how to construct a list of vectors when the pairwise overlap isstrictly smallerthan $n/c^2$. $\endgroup$ – Penelope Benenati Dec 10 '17 at 13:17mypost without the at construct, so you, most likely, haven't been notified yet. Ping! $\endgroup$ – fedja Dec 10 '17 at 20:57