2
$\begingroup$

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?

Thanks.

$\endgroup$
6
  • $\begingroup$ Sorry, the problem wasn't explained correctly. I've edited my question. $\endgroup$
    – Masood
    Jun 16, 2015 at 20:21
  • $\begingroup$ And yes, S is finite and all the matrices are $n \times n$ $\endgroup$
    – Masood
    Jun 16, 2015 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$ Jun 17, 2015 at 5:53
  • $\begingroup$ In fact, I'm looking for constant $\alpha$, independent of $|S|$ or $n$. $\endgroup$
    – Masood
    Jun 17, 2015 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, 2015 at 14:01

1 Answer 1

1
$\begingroup$

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

$\endgroup$
5
  • $\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, 2015 at 11:18
  • $\begingroup$ @Masood I have to think about this bound. Yes, you can contact me, my e-mail is [email protected] $\endgroup$ Jun 20, 2015 at 8:31
  • $\begingroup$ @Masood It seems that I can obtain a lower bound for $\alpha(n)$. To be continued... $\endgroup$ Jun 22, 2015 at 8:59
  • $\begingroup$ @Masood I posted a related question at MSE. $\endgroup$ Jun 22, 2015 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, 2015 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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