# 0-1 matrix combinatorial problem

Let $M \in \{0,1\}^{n \times n}$ and let $r_i$ be its $i$-th row. Given constant $p \in (0,1/2]$, let the number of $1$s in each row be at least $p\,n$. Given constant $c \in (0,1)$, what is the maximum number $R_{max}$ of rows $r$ such that

$$r\, r_i^{\top} \ge c\,n$$

holds for less than $n^{1/3}$ row indices $i$? Do we have $R_{max}=\Theta(n^{1/3})$ for any constant $c>0$ and $p \in (0,1/2]$ when $n$ approaches infinity? Thank you!

Think about having the first $n^{1/3}−1$ rows with all of their $1$s in the first $pn$ columns, the second $n^{1/3}−1$ rows with all their $1$s in the second $pn$ columns, and so on. This construction allows me to see that, for any constant $c>0$ and $p \in (0,1/2]$, we have $$R_{max} \ge (1/p−1)(n^{1/3}−1)$$ It is not clear to me whether there exists a matrix construction showing that $$R_{max}=\omega\left((1/p−1)(n^{1/3}−1)\right)$$ for some constant $c>0$ when $n$ approaches infinity.

Perhaps, the most central question is: Do we have $$R_{max}=\Theta\left((1/p-1)(n^{1/3}-1)\right)=\Theta(n^{1/3})$$ for any constant $c>0$ and $p \in (0,1/2]$ when $n$ approaches infinity?

## ---

Update: I just posted now the "real" (complete) question from which this (sub)problem arose: Combinatorial 0-1 vector problem.

• Presumably you mean $r_ir^T$? Dec 4, 2017 at 10:11
• Of course, sorry, I correct. Thanks. Dec 4, 2017 at 10:13
• What relative sizes of $p$ and $c$ are you interested in? What do simple constructions yield (like having the first $pn$ rows have all of their $1$s in the first $pn$ columns, the second $pn$ rows having all their $1$s in the second $pn$ columns, etc.), and do you think there are better constructions? I'm guessing you've done some work on this problem already, and it will enable actual helpful responses if you don't make readers reconstruct what you already know. Dec 4, 2017 at 10:17
• Think about having the first $n^{1/3}-1$ rows with all of their $1$s in the first $pn$ columns, the second $n^{1/3}-1$ rows with all their $1$s in the second $pn$ columns, and so on. This construction allows me to see that, for any constant $c>0$, we have $R_{max} \ge \left(\frac{1}{p}-1\right)\,(n^{1/3}-1)$. It is not clear to me whether there exists a matrix construction showing that $R_{max} = \omega\left(\left(\frac{1}{p}-1\right)\,(n^{1/3}-1)\right)$ for some constant $c>0$, when $n$ approaches infinity. Dec 4, 2017 at 20:07
• (I suggest editing those comments into the question) Dec 4, 2017 at 22:59