Counting the equivalence classes of some binary matrices

Question

Consider an $h \times w$ binary matrix (a matrix with all entries $a_{ij}$, $1 \le i \le h$, $1 \le j \le w$, equal to $0$ or $1$) with $w$ even and $h \ge 3$. We know that each row has $\frac{w+2}{2}$ entries equal to $1$ and $\frac{w-2}{2}$ entries equal to $0$. All rows are different. For each $j$, $1 \le j \le w$ there exists at least one $k$, $1 \le k \le h$ such that $a_{kj} = 0$. One matrix is equivalent to another when equal up to a permutation of columns and/or rows.

I would like to find a function $c(h,w)$ to count how many possible equivalence classes of matrices are there, if possible for generic values of $h$ and $w$, or at least for some values of $h$. If an exact count is not possible, an upper bound can do.

For example, I can get $c(3,6)=1$ and any matrix satisfying the requirements is equivalent to:

$$ \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ \end{pmatrix} $$

However, I have difficulties in going further.

Any hint? Thank you.

Answer 1

Equivalently, you are counting unlabelled bicolored graphs that have $h$ red vertices ("rows") and $w$ blue vertices ("columns"); such that red vertices have degree exactly $w/2+1$, and blue vertices have degree at most $h-1$ (each column has at least one zero). And finally, each red vertex has different neighborhood (all rows are different). Your matrices are the biadjacency matrices of such graphs. "Unlabelled" says you can freely permute rows and columns.

A computational solution for generating (and then counting) such bicolored graphs is genbg from Nauty. The degree conditions are easy to specify. We have to make the red vertices to be the second color class, then "genbg -z" enforces them to have different neighborhoods. (It does not have a corresponding option for the first color class.) The conditions listed above lead to the following shell script:

#/bin/bash
h=$1
w=$2
let bluemaxdeg=$h-1
let reddeg=$w/2+1
./genbg -z $w $h -d0:${reddeg} -D${bluemaxdeg}:${reddeg}

For example, if that script is named "somebinary",

$ ./somebinary 3 6
>A ./genbg n=6+3 e=12:12 d=0:4 D=2:4 z
H??FeW{
>Z 1 graphs generated in 0.00 sec

Extracting the biadjacency matrix in SageMath (from red vertices to blue vertices, so the matrix is oriented as in the problem):

sage: G=Graph("H??FeW{")
sage: A=G.adjacency_matrix()
sage: A[:6, 6:]
[1 1 1 1 0 0]
[1 1 0 0 1 1]
[0 0 1 1 1 1]

Here are the counts for small parameter values. That's a couple of hours of computation.

$$ \begin{array}{r|rrrr} & w=4 & 6 & 8 & 10\\ \hline h=3 & 0 & 1 & 1 & 3 \\ 4 & 1 & 3 & 14 & 55 \\ 5 & 0 & 9 & 115 & 1265 \\ 6 & 0 & 15 & 904 & 33425 \\ 7 & 0 & 20 & 6052 & 885810 \\ 8 & 0 & 22 & 36311 & 21936149 \\ 9 & 0 & 20 & 191568 & 492515184 \\ 10 & 0 & 14 & 896697 \\ 11 & 0 & 9 & 3738372 \\ 12 & 0 & 5 & 13989546 \\ 13 & 0 & 2 & 47256369 \\ 14 & 0 & 1 & 144910788 \\ 15 & 0 & 1 \\ 16 & 0 & 0 \\ \end{array} $$

You'll notice that with $w=6$ the rows have two zeros, so there can be at most $\binom{6}{2}=15$ different rows and the counts are zero for $h>15$.

The columns don't seem to match anything in OEIS. (Okay, the $w=4$ column is A185014.)