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.

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

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .