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

Question

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.

Answer 1

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