To get some feel for the size of a particular computation, I would like to know the *approximate number* of (pairwise-nonisomorphic) cubic bipartite graphs on $40$ vertices whose bipartite adjacency matrix has determinant $\pm 3$.

Just to fix some basic facts and clarify the terminology:

- A graph is
*cubic*if every vertex has three neighbours - A graph is
*bipartite*if the vertices can be partitioned into two sets $B$ (for black) and $W$ (for white) such that every edge connects a black vertex to a white one; this partition is unique if the graph is connected. - The
*bipartite adjacency matrix*of a graph (with respect to a partition) is the matrix $A$ with rows indexed by black vertices, columns by white vertices and where $A_{bw} = 1$ if and only if $b$ is adjacent to $w$

This seems to involve two steps: finding out how many cubic bipartite graphs there are and then finding out what proportion of those have a bipartite adjacency matrix with the right determinant.

I can get some handle on the first step by looking at the tables produced by Canfield and McKay (hi Brendan!) at http://users.cecs.anu.edu.au/~bdm/data/semiregular.html who tell me that there are

$$Bv[20,3,20,3] = 77705104689340239554388061645133412621507133440000$$

semi-regular binary matrices with $20$ rows and $20$ columns where each row- and column-sum is equal to $3$.

Seeing I am only concerned with isomorphism classes, not total numbers, I can divide this enormous number by $2 \cdot (20!)^2$ to get an approximate number of about $6.56 \times 10^{12}$ for the number of isomorphism classes. (The number $2 \cdot (20!)^2$ is the number of distinct labelled graphs in the isomorphism class of a $40$-vertex cubic bipartite graph with trivial automorphism group and, up to a first approximation, all graphs have trivial group.)

Now for the second step - what proportion of these cubic graphs have a bipartite adjacency matrix with determinant of absolute value $3$? The determinant of any square regular binary matrix of degree $k$ (i.e. all row sums $k$, hence all column sums $k$) is a multiple of $k$ and so $\pm3$ are the smallest possible determinants of any non-singular matrix in this class.

I've done some experiments where, for each fixed number of vertices, I created a few million random cubic bipartite graphs of that size and then looked at what percentage have determinant $0$, $\pm 3$, $\pm 6$ and so on. I did this for graphs a bit smaller than, and a bigger than, the target size really just to see what happens.

The next table shows the number of vertices (expressed as a sum - so that $15+15$ means that each part of the bipartition has $15$ vertices for a total of $30$). The three numbers following are the percentage of graphs with determinant $0$, $\pm 3$ and $\pm 6$, with the numbers trailing off (not monotonically) as the determinant increases in absolute value. Here $d$ means $|\det A|$.

```
verts d = 0 d = 3 d = 6
15+15 61.41 00.00 00.00
16+16 35.67 14.07 16.94
17+17 33.22 13.80 15.41
18+18 52.97 00.00 00.00
19+19 30.79 10.44 14.11
20+20 28.91 09.89 12.92
21+21 45.35 00.00 00.00
22+22 26.39 07.67 11.30
23+23 24.87 07.11 10.22
24+24 38.46 00.00 00.00
25+25 22.44 05.58 08.78
```

So this suggests that around $10\%$ of the cubic bipartite graphs on $40$ vertices will have the right determinant, leaving me with something like $7 \times 10^{11}$ graphs, probably a bit more.

My question is really whether I can do better than this? Are there known counting results and/or determinant results that I can use to improve my two estimates?

**Added in response to Brendan**

If the matrices have order $3k \times 3k$, then the determinant must be a multiple of $9$, hence none of $\pm 3$, $\pm 6$.

To see, suppose that $A$ is such a matrix. Use elementary row operations to add rows $2$, $3$, $\ldots$, $3k$ to row 1. The top row is now all-$3$s, but the determinant is unchanged. Repeat the process with columns. Now we have a matrix where the $(1,1)$-entry is $9k$ and all the other entries in the first row and column are equal to $3$.

Consider now each transversal of the matrix, and the contribution to the determinant made by the product of the entries picked out by the transversal. If the transversal uses the $(1,1)$-entry then it automatically contributes some multiple of $9$, while if it doesn't then it must use the $(i,1)$ and $(1,j)$ entries for some $i$, $j \ne 1$ and as each of those values is equal to $3$, contribution is also a multiple of $9$.

1more comment