I've come up with the following question in my research: Let $S$ be a finite set of $n \times n$ matrices with elements 0 or 1. denote $n_i$ as the total number of 1's in the $i$th row of all matrices in $S$. We want to select one column of each matrix, such that for the $i$th row, at least $\lfloor \frac{\alpha n_i}{n} \rfloor $ of the ones in that row are selected. Is there any $\alpha>0$ that we can guarantee the existence of such selection? In particular, what is the maximum $\alpha$ that we can guarantee? Is there a previous well known result about this problem?


  • $\begingroup$ Sorry, the problem wasn't explained correctly. I've edited my question. $\endgroup$ – Masood Jun 16 '15 at 20:21
  • $\begingroup$ And yes, S is finite and all the matrices are $n \times n$ $\endgroup$ – Masood Jun 16 '15 at 20:22
  • $\begingroup$ It seems that the question is about $\alpha_0$, which equals the maximal $\alpha$ that we can guarantee and $1/|S|\le \alpha_0\le 1 $, because if $0<\alpha<1/|S|$ then the condition is trivially satisfied because $\lfloor \frac{\alpha n_i}{n} \rfloor=0$. $\endgroup$ – Alex Ravsky Jun 17 '15 at 5:53
  • $\begingroup$ In fact, I'm looking for constant $\alpha$, independent of $|S|$ or $n$. $\endgroup$ – Masood Jun 17 '15 at 7:43
  • 1
    $\begingroup$ $\alpha$ is strictly less than one. As an example, consider these two $4 \times 4$ matrices: $$ 1 1 0 0 \mbox{ -- } 0 1 0 1 $$ $$ 1 1 0 0 \mbox{ -- } 1 0 1 0 $$ $$ 0 0 1 1 \mbox{ -- } 1 0 1 0 $$ $$ 0 0 1 1 \mbox{ -- } 0 1 0 1 $$ For any selection of columns, at least one row has no selected "1". $\endgroup$ – Masood Jun 18 '15 at 14:01

Naturally generalizing your example we can show that $\alpha=0$. Consider the following construction. For any natural number $k$ put $n=2^k$ and consider matrices $A_1,\dots, A_k$, where each $A_j$ consists of $n/2$ copies of columns $a_j^T=(a_{ij})$, where $a_{ij}=1$, if $\lfloor i/2^{j-1} \rfloor$ is odd and $a_{ij}=0$, otherwise and $n/2$ copies of columns $(1,1,\dots, 1)^T- a_j^T $. Then $n_i=kn/2$ for each $i$, but for any selection of columns at least one row has no selected “1”. So $0=\lfloor \alpha n_i/n\rfloor=\lfloor \alpha k/2\rfloor$. That is $\alpha<2/k$.

  • $\begingroup$ Thanks, your construction shows that no constant $\alpha>0$ can be guaranteed. Do you think $\alpha = \Omega(\frac{1}{\log n})$? Can I contact you by email, if necessary? $\endgroup$ – Masood Jun 19 '15 at 11:18
  • $\begingroup$ @Masood I have to think about this bound. Yes, you can contact me, my e-mail is oravsky@mail.ru $\endgroup$ – Alex Ravsky Jun 20 '15 at 8:31
  • $\begingroup$ @Masood It seems that I can obtain a lower bound for $\alpha(n)$. To be continued... $\endgroup$ – Alex Ravsky Jun 22 '15 at 8:59
  • $\begingroup$ @Masood I posted a related question at MSE. $\endgroup$ – Alex Ravsky Jun 22 '15 at 18:47
  • 1
    $\begingroup$ Thanks, I'll track it as well. Maybe searching for generalized form of probability bounds like chernoff helps. $\endgroup$ – Masood Jun 23 '15 at 20:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.