3
$\begingroup$

Given $n\in\Bbb N$, $\alpha>0$, $\beta\in\big[\frac12,1\big]$ denote $\mathcal R_{n,\alpha,\beta}$ as collection of all $2^n\times 2^{n^\alpha}$ $0/1$ matrices with every row summing to strictly greater than $\beta2^{n^\alpha}$.

Denote $f(\mathcal R_{n,\alpha,\beta})$ as worst case minimum number of columns among matrices in $\mathcal R_{n,\alpha,\beta}$ that is needed so that in any such matrix there is always a collection $\tau\leq f(\mathcal R_{n,\alpha,\beta})$ of columns which when considered as a submatrix has every row with strictly greater than $\frac\tau2$ entries $1$.

(Clearly such a submatrix exists for every matrix in $\mathcal R_{n,\alpha,\beta}$ as every $2^n\times 2^{n^\alpha}$ matrix in $\mathcal R_{n,\alpha,\beta}$ has this property).

$1.$ Does ${f\Big(\mathcal R_{n,\alpha,\frac34}\Big)}=O(n^{\alpha\gamma})$ hold at some fixed $\gamma\geq0$?

$2.$ Does ${f\Big(\mathcal R_{n,\alpha,\frac12+\frac1{g(n)}}\Big)}=O(n^{\alpha\gamma''})$ hold at some fixed $\gamma''\geq0$ for every $g:\Bbb R\rightarrow\Bbb R$ with $x<y\implies g(x)\leq g(y)$ with $g(n)\leq2^{n^\zeta}$ where $\zeta\in[1,\alpha]$ holds or does any such $\gamma''$ depend on $g$ OR for any such growing $g$ does ${f\Big(\mathcal R_{n,\alpha,\frac12+\frac1{g(n)}}\Big)}=\omega(n^{\alpha\delta'})$ hold at any fixed $\delta'>0$ hold?

Clearly if $g(n)>2^{n^\alpha}$ the scenario reduces to case of $\frac12$ more or less morally since number of columns scales much more fast than probability of getting a balance of more $1$s.

Are there any references and any good tools to study this problem?


Without $\tau$ criterion even if $\beta=\frac12$ just ${n^\alpha} + 1$ columns suffice (we can use greedy method by picking a column which has most number of $1$s and removing this column and collection of rows which are $1$ at this column and reapply greedy method. It is clear that if $\alpha\geq1$ there should be a column with at least $\frac12$ number of $1$s).

$\endgroup$

1 Answer 1

1
$\begingroup$

If you relax the power-of-two condition, you can contrive examples for the $\beta = 1/2$ and $\alpha = 1$ case that require all columns to be used. Choose a large prime $p$. Let $A$ be the $p \times p$ matrix where $A_{ij} = 1$ if $i-j \in \{0, 1, \dots, (p-1)/2\} + \mathbb{Z}p$ and $A_{ij} = 0$ otherwise. If you choose $k<p$ columns of the $p$ available, then you have chosen a submatrix with a total of $k(p+1)/2$ ones. There is a row with at most $\lfloor k(p+1)/(2p)\rfloor$ ones. Note that $p+1$ is even and $k(p+1) = k \pmod{p}$, so $k(p+1) = k+p \pmod{2p}$. There is therefore a row with $$\left\lfloor \frac{k(p+1)}{2p}\right\rfloor = \frac{k(p+1)-(k+p)}{2p} = \frac{k-1}{2} < \frac{k}{2}$$ ones.

When $\beta = 3/4$, standard tools show that only a small number of columns are necessary. Consider i.i.d. randomly selecting each column with probability $p$. The expected number of ones in the $i$th row is $p \beta 2^{n^\alpha}$. The Chernoff bound states that we achieve fewer than $p \frac{9}{16} 2^{n^\alpha}$ ones in the $i$th row with probability at most $\exp(-p \beta 2^{n^\alpha}/32)$.

One can choose $p$ to be a constant multiple of $n 2^{-n^\alpha}$ and find that this failure probability is bounded above by $2^{-1 - n^\alpha} \leq 2^{-1-n}$. There are $2^n$ rows; by the union bound, (at least one row has too few ones) with probability at most $\frac12$ with this choice of $p$. We choose, in expectation, $C n 2^{-n^\alpha} \beta 2^{n^\alpha} = C \beta n$ columns. By Markov's inequality, we choose more than $3 C \beta n$ columns with probability at most $1/3$; with probability at least $1/6$ we choose at most $3 C \beta n$ columns and each row has more than half of its entries 1.

$\endgroup$
8
  • $\begingroup$ I am not sure what you mean by "we can [...] find." Are you looking for a construction? The proof gives an experiment that produces the set of columns you're looking for with probability at least $1/6$. $\endgroup$
    – tmyklebu
    Mar 19, 2016 at 23:59
  • $\begingroup$ yes I see that. Even if you repeat it $n$ times we are only guaranteed with probability $1-(5/6)^n$. It is not a definite statement that there is always such a set of columns in any such matrix. There could be some matrix which does not have these set of columns. $\endgroup$
    – user76479
    Mar 20, 2016 at 0:03
  • $\begingroup$ I do not understand your objection. If such a matrix existed, you could run this experiment on that matrix. The experiment would succeed (i.e. produce a set of columns of size less than $3C\beta n$ that makes every row happy) with probability zero. This proof shows that the experiment succeeds with probability at least $1/6$ no matter which matrix from $\mathcal{R}(n, \alpha, \frac34)$ you choose. $1/6$ is larger than zero. $\endgroup$
    – tmyklebu
    Mar 20, 2016 at 0:09
  • $\begingroup$ ah i see since for every matrix probability is +ve every matrix has such a subset (infact many of them). Interesting. Seems like similar approach should work for $2.$ right? $\endgroup$
    – user76479
    Mar 20, 2016 at 0:11
  • $\begingroup$ For 2, I'm not at all sure how fast $g$ can grow. Certainly you can use the Chernoff tools to analyse a specific $g$, but I'm not sure whether this analysis is tight enough. (It's not even clear to me what happens if you require each row to have at least $\lceil 2^{\alpha n-1}\rceil + 1$ ones.) $\endgroup$
    – tmyklebu
    Mar 20, 2016 at 0:14

Your Answer

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