1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you very much, I am going to download the program. Do you think it is feasible computing for $w = 52$ and $h = 13$? $\endgroup$
    – BillyJoe
    Aug 13 at 12:43
  • 1
    $\begingroup$ I doubt you can compute such large instances with this approach. With genbg you'll run into hard limits on the graph size (64 vertices using the large-graph version genbgL), and even if that is fixed, it would be extremely slow. For $h\le 10$ and $w \le 8$ I computed it in about 20 seconds, I'll add the results in my answer for reference. For large parameter values you'd need a different approach. $\endgroup$ Aug 13 at 12:52
  • 1
    $\begingroup$ The count for $w=52$ and $h=13$ is about $1.3\times 10^{113}$, so you won't be computing it by exhaustive generation. However, proving a sharp estimate is not hard. If you choose the rows at random independently, it has the other properties and a trivial automorphism group with probability close to 1 (needs proving) so divide by $52!\,13!$ for equivalence classes. An exact number needs Polya's theorem or similar and would be work. $\endgroup$ Aug 13 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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