Number of couples of columns "connecting" top to bottom of a matrix

Question

This question is on the same topic of this one, but simpler, and I have also included some numerical tests here.

Consider a $h \times (n-1-h)$ matrix $A$ with all entries $a_{ij}$, $1 \le i \le h$, $1 \le j \le n-1-h$, equal to $0$ or $1$. We know that each row has $\lfloor (n+1) / 2 \rfloor - 1$ entries equal to $1$ and $n-\lfloor (n+1) / 2 \rfloor-h$ entries equal to $0$. All rows are different. Let $c(A)$ be the number of couples of columns with indexes $1 \le j_1 \lt j_2 \le n-1-h$ such that $a_{ij_1} = 1 \lor a_{ij_2} = 1$, $1 \le i \le h$. It's like there is a path of ones from the top to the bottom of the matrix along the $2$ columns of a couple. Let $\mathcal{A}(h,n)$ be the set of all those matrices for given $h,n$.

Let $$f(n) = \min_{1 \le h \le \lfloor n/2 \rfloor - 1, A \in \mathcal{A}(h,n)}{c(A)}.$$

I have computed the minimum for some values of $n$ based on 700000 random cases for each $h$ and $n$ to get an estimate $f_e(n)$ for $f(n)$. $f_e(n) \ge f(n)$. For $2 \le k \le 23$, $f_e(2k+1)$ is equal to: $3,6,10,15,21,28,36,45,55,61,68,74,80,84,89,94,95,96,103,109,106,105$ while $f_e(2k+2)$ is equal to: $3,6,10,15,21,28,36,45,55,53,58,62,68,71,74,79,82,80,86,90,91,89$.

For $k \le 10$, $f_e(2k+1) = f_e(2k+2)$, while for $k \gt 10$ it seems that $f_e(2k+1) > f_e(2k+2)$.

The minimum is located at $h = \lfloor n/2 \rfloor - 1$ for $k \le 10$, while for $k \gt 10$ it seems to move to $h \approx n/4$.

Now, for $2 \le k \le 10$ we can note that:

$$f_e(2k+1) = f_e(2k+2) = \binom{k+1}{2}$$

What happens for $k \gt 10$? Is it just a problem/error in the numerical random tests that the computed values does not follow the last equation? Is it actually

$$f(n) = \binom{\lceil n/2 \rceil}{2}?$$

If so, any hint for proving it? If not, is it possible to get a good lower bound for $f(n)$?

Answer 1

We can view (unordered) pairs of zeros in each row as covering the pairs of columns (and thus eliminating them from being counted by $c$). Since we want to minimize $c$, the more pairs are covered the better. Thus, we naturally arrive at partial $(n-1-h,\lfloor n/2\rfloor - h,2)$-covering designs, where number of blocks is fixed at $h$ and the goal is to cover as many $2$-element subsets of $[n-1-h]$ as possible. I was not able to find direct results on this variation of the problem right away, but I suspect it must have been studied.

---

The above considerations imply the lower bound: $$f(n) \geq \min_{1\leq h\leq \lfloor n/2\rfloor-1} \binom{n-1-h}2 - h\binom{\lfloor n/2\rfloor - h}2.$$ For $n=4,5,\dots,23$, the values of this bound are $$1, 3, 3, 6, 6, 10, 10, 15, 15, 21, 21, 28, 28, 36, 36, 45, 41, 55, 45, 60.$$

---

Below I present an ILP formulation for computing $\min_{A\in\cal{A}(h,n)} c(A)$ for a given $h$ and $n$: $$\begin{cases} \sum_{1\leq i<j\leq n-1-h} t_{i,j} \quad\longrightarrow\quad \min\\ \sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];\\ a_{k,i} + a_{k,j} \leq 2 d_{k,i,j}\qquad \text{for }1\leq i<j\leq n-1-h,\ k\in[h];\\ \sum_{k=1}^h d_{k,i,j} \leq h - 1 + t_{i,j}\quad \text{for }1\leq i<j\leq n-1-h \end{cases}$$ where $a_{k,i}$, $d_{k,i,j}$, and $t_{i,j}$ are binary variables, $a_{k,i}$ represent elements of $A$, optimal value $t_{i,j}$ equals 1 iff the column pair $(i,j)$ is not covered, and thus $\min_{A\in\cal{A}(h,n)} c(A)$ is given by the objective value $\sum_{1\leq i<j\leq n-1-h} t_{i,j}$.

I confirm that your estimated values $f_e(2k+1)$ give the true values of $f(2k+1)$ for $k\leq 10$, and in fact they can be achieved on a matrix with $h=k-1$ and all zeroes forming a single column, which explains the equality $f(2k+1)=\binom{k+1}2$ here.