0
$\begingroup$

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)$?

$\endgroup$
2
  • 1
    $\begingroup$ Is $c(h,n)$ a minimum over matrices? You don't say that. $\endgroup$ Nov 12, 2022 at 6:29
  • 1
    $\begingroup$ @Brendan McKay yes, sorry, I have updated the question. $\endgroup$ Nov 12, 2022 at 6:47

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Great answer, thank you. I will wait some time before accepting, should a better bound come up, because your bound computed at $h=\lfloor n/4 \rfloor$ is negative for $n \ge 40$. $\endgroup$ Nov 12, 2022 at 18:50
  • 1
    $\begingroup$ Yes, it's not that useful for large $n$. Still, for $n=23$ it can be used to show that your upper bound 61 is in fact $f(23)$. If the expression under $\min$ in my bound is attained at some matrix from $\cal{A}(h,n)$, then there is a 2-design with $b:=h$, $k:=\lfloor n/2\rfloor - h$, and $\lambda:=1$. A necessary condition is that $8h\binom{\lfloor n/2\rfloor - h}2+1$ is a square, which fails for $n=23$ and $h=6$ corresponding to the lower bound 60. Hence, $f(23)=61$. $\endgroup$ Nov 12, 2022 at 21:53
  • $\begingroup$ Do you think it might be worthwhile to try to refine your expression under $\min$ using some "inclusion-exclusion"? $\endgroup$ Nov 14, 2022 at 13:31
  • $\begingroup$ I do not see how inclusion-exclusion can help here. $\endgroup$ Nov 14, 2022 at 14:49
  • 1
    $\begingroup$ You may try to look at the concept of "partially balanced incomplete block design". Maybe even the simplest case of two associate classes with $\lambda_1 = 0$ and $\lambda_2 = 1$ (eg. check this paper), ie. when every pair of columns is either not covered or covered exactly once, can be fruitful here. $\endgroup$ Nov 15, 2022 at 15:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.