# Selecting columns of a set of boolean matrices with constraint on the ones in each row

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.

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

## 1 Answer

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

• 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? – Masood Jun 19 '15 at 11:18
• @Masood I have to think about this bound. Yes, you can contact me, my e-mail is oravsky@mail.ru – Alex Ravsky Jun 20 '15 at 8:31
• @Masood It seems that I can obtain a lower bound for $\alpha(n)$. To be continued... – Alex Ravsky Jun 22 '15 at 8:59
• @Masood I posted a related question at MSE. – Alex Ravsky Jun 22 '15 at 18:47
• Thanks, I'll track it as well. Maybe searching for generalized form of probability bounds like chernoff helps. – Masood Jun 23 '15 at 20:54