0
$\begingroup$

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 $n/c$ (assuming $c$ is a divisor of $n$).

Given a constant $\beta \in (0,1)$, we call a row vector $r\,$ "$z$-orthogonal" if the number of $M$'s row vectors $r'$ such that $\,r' r^{\top} \le z\,n\,$ is greater or equal to $n-n^{\beta}$.

Question: When $n$ approaches infinity, what is the maximum number $N$ of $z$-orthogonal row vectors of $M$, in the case $z$ is strictly smaller than $1/c^2$?

Note: If $z \ge 1/c^2$ is very easy to show how to construct $M$ such that $N=n$.

In the case $z < 1/c^2$, it seems to me that $N=(c-1)n^{\beta}$, but I am not completely sure and I do not know how to prove it.

---

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

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ Relation of this to your earlier question mathoverflow.net/questions/287695/… ? $\endgroup$
    – Gerry Myerson
    Commented Dec 7, 2017 at 21:00
  • 1
    $\begingroup$ What's wrong with putting all ones to the left half for $n/2$ rows and to the right half for the remaining $n/2$ rows achieving $z=0$ and $N=n$ (if you agree to consider $n/2$ as $\omega(1)$? What you, probably, really wanted to ask was the question if we can find many sets $E_j$ on $[0,1]$ of measure $1/c$ with $|E_k\cap E_m|\le a<c^{-2}$ for $k\ne m$. Then, indeed, there is a bound $C(a,c)$ for the size of any such family (just apply Cauchy-Schwarz to the sum of the characteristic functions of $E_j$). $\endgroup$
    – fedja
    Commented Dec 7, 2017 at 21:52
  • $\begingroup$ Gerry, the relation of this to my earlier question is a bit complicated. Basically I trying to simplify the "real" question underlying mathoverflow.net/questions/287695/…. When I will understand how to proceed in order to solve the problem I am addressing, I will delete the meaningless questions. $\endgroup$
    – Penelope Benenati
    Commented Dec 7, 2017 at 23:01
  • 1
    $\begingroup$ It is, indeed $C(z,c)n^\beta$ now and, if you bothered to follow the hint and solve the little puzzle I told you, you should certainly know how to get such bound by now (if the number of $z$-orthogonal vectors is too large compared to $n^\beta$, then you can use the greedy algorithm to choose more than $C(z,c)$ pairwise $z$-orthogonal vectors and that is impossible). However $c-1$ is certainly too optimistic for the constant. It should depend on $z$ too and blow up as $z\to c^{-2}$. Really, think of that old teaser for students a bit and you'll know everything one can know here :-) $\endgroup$
    – fedja
    Commented Dec 8, 2017 at 0:35
  • 1
    $\begingroup$ If there are answers posted to your "meaningless questions", Penelope, I hope you won't delete them. $\endgroup$
    – Gerry Myerson
    Commented Dec 8, 2017 at 11:24

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .