Return to Question

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?

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.

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$? 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?

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?

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$? 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]$?

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$? 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?