5
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Presumably you mean $r_ir^T$? $\endgroup$ – Greg Martin Dec 4 '17 at 10:11
  • $\begingroup$ Of course, sorry, I correct. Thanks. $\endgroup$ – Penelope Benenati Dec 4 '17 at 10:13
  • 2
    $\begingroup$ 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. $\endgroup$ – Greg Martin Dec 4 '17 at 10:17
  • $\begingroup$ 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. $\endgroup$ – Penelope Benenati Dec 4 '17 at 20:07
  • 3
    $\begingroup$ (I suggest editing those comments into the question) $\endgroup$ – Greg Martin Dec 4 '17 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.