This question is on the same topic of [this one](https://mathoverflow.net/q/434157/136218), 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)$?



Number of couples of columns "connecting" top to bottom of a matrix
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](https://www.dmgordon.org/cover/), 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.


