Timeline for Selecting columns of a set of boolean matrices with constraint on the ones in each row
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 19, 2015 at 11:04 | vote | accept | Masood | ||
| Jun 19, 2015 at 3:29 | answer | added | Alex Ravsky | timeline score: 1 | |
| Jun 18, 2015 at 14:01 | comment | added | Masood | $\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". | |
| Jun 18, 2015 at 3:16 | comment | added | Alex Ravsky | It's natural. Now I'm trying to check these $\alpha$'s, in particular, $\alpha=1$. | |
| Jun 17, 2015 at 7:43 | comment | added | Masood | In fact, I'm looking for constant $\alpha$, independent of $|S|$ or $n$. | |
| Jun 17, 2015 at 5:53 | comment | added | Alex Ravsky | 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$. | |
| Jun 16, 2015 at 20:22 | comment | added | Masood | And yes, S is finite and all the matrices are $n \times n$ | |
| Jun 16, 2015 at 20:21 | comment | added | Masood | Sorry, the problem wasn't explained correctly. I've edited my question. | |
| Jun 16, 2015 at 20:19 | history | edited | Masood | CC BY-SA 3.0 |
added 34 characters in body
|
| Jun 16, 2015 at 11:40 | history | edited | Masood | CC BY-SA 3.0 |
edited title
|
| Jun 16, 2015 at 11:35 | history | edited | Masood | CC BY-SA 3.0 |
edited title
|
| Jun 16, 2015 at 11:28 | history | asked | Masood | CC BY-SA 3.0 |