An extremal combinatorics problem involving column summation

Question

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

Answer 1

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.