What is the number of k-regular subgraphs of $K_{12,12}$?

Question

I'm thinking about making an attempt at counting the number of Latin squares of order 12. Currently I'm in (what I call) the "sanity check" stage, where we check that the ranges that need searching through aren't too massive.

The standard method of counting Latin squares involves building up from Latin rectangles. We get an improvement if we "forget" the structure of the Latin rectangle and remember only which symbols occur in which column (in fact, this is what's makes counting Latin squares possible-ish, the idea goes back to Sade). This can be achieved by interpreting the Latin rectangle as a k-regular subgraph of $K_{n,n}$.

So, in order to perform my sanity check, I'm after the number of non-isomorphic $k$-regular subgraphs of $K_{12,12}$ where $k \in \{1,2,\ldots,6\}$ (where subgraphs include all 24 vertices). (Sloane's http://oeis.org/A008327). I'm particularly interested in the case $k=6$.

Question: What is the number of non-isomorphic $k$-regular subgraphs of $K_{12,12}$?

Actually, an estimate would be good enough for what I want. So perhaps it's more realistic to hope for an answer to this question:

Question: What is an easy way to estimate the number of non-isomorphic $k$-regular subgraphs of $K_{12,12}$?

McKay and Wanless (2005) write:

It is unlikely that [the number of Latin squares of order 12] will be computable by the same method for some time, since the number of regular bipartite graphs of order $24$ and degree $6$ is more than $10^{11}$.

Searching through $10^{11}$ graphs is not completely out-of-the-question, but if it were much more than this I would have to reconsider.

Answer 1

The "nonisomorphic" part is not relevant, if you are only looking for an estimate (the isomorphsm group of almost all graphs is trivial), so to first order you are looking for the number of $k$-regular bi-partite graphs on $n$ (in your case $n=12$) vertices. At that point, the key words are "configuration model", invented by Bollobas, and used to great effect by Nick Wormald. In any case, Bollobas' "Random Graphs" will have the estimate you want.

Answer 2

This answer is mostly a thanks to Igor Riven, and to give the details for those who may follow. So I think I got a configuration model to work...

We construct a random k-regular bipartite multi-graph by generating a random permutation $\sigma$ from {1,...,kn}. Then draw an edge from 1 to $\sigma(1),\sigma(2),\ldots,\sigma(k)$, then draw an edge from 2 to $\sigma(k+1),\sigma(k+2),\ldots,\sigma(2k)$, and so on.

The size of the set being sampled from has size approximately $(kn)!/(k!^{2n})$ -- the same graph will be drawn if we permute within the sets $\{1,\ldots,k\},\{k+1,\ldots,2k\},\ldots$, and if we permute $\{\sigma(1),\ldots,\sigma(k)\},\{\sigma(k+1),\ldots,\sigma(2k)\},\ldots$. If we ignore the possibility of obtaining the same permutation back again after performing these operations, we obtain a biased estimator for the number of k-regular bipartite multi-graphs generated.

Restricting to the types of isomorphisms considered by McKay and Wanless, we should anticipate each isomorphism class to have size $2 n!^2$ (another biased estimator), which we divide by to give the desired result.

Here's the GAP code I wrote to perform these estimates.

This function tests if the graph is a simple graph:

NoIntersectionContainsMoreThanOneElement:=function(A,B)
  local S1,S2;
  for S1 in A do for S2 in B do
    if(Size(Intersection(S1,S2))>1) then return false; fi;
  od; od;
  return true;
end;;

This function generates iter instances of the random graph described above.

EstimateNrRandomKRegularSubgraphOfKNN:=function(k,n,iter)
  local p,q,A,S1,S2,count_total,count_good;
  count_total:=0;
  count_good:=0;
  A:=List([1..n],i->List([1..k],j->k*(i-1)+j));
  for count_total in [1..iter] do
    p:=RandomPermutationList(k*n);
    q:=List([1..n],i->List([1..k],j->p[k*(i-1)+j]));
    # Print(p,"\n",q,"\n",NoIntersectionContainsMoreThanOneElement(q,A),"\n\n");
    if(NoIntersectionContainsMoreThanOneElement(q,A)) then count_good:=count_good+1; fi;
  od;
  return count_good/count_total*Factorial(k*n)/Factorial(k)^(2*n);
end;;

[RandomPermutationList() and Decimal() are non-GAP functions that I implemented myself]

Here is the test output for 5-regular subgraphs of $K_{11,11}$:

gap> k:=5;; n:=11;; iter:=1000000;; EstimateNrRandomKRegularSubgraphOfKNN(k,n,iter)/(2*Factorial(n)^2);
32487228876370918434190864363106201/424673280000000000000000000
gap> Decimal(last);
76499347.6311269652
gap> k:=5;; n:=11;; iter:=1000000;; EstimateNrRandomKRegularSubgraphOfKNN(k,n,iter)/(2*Factorial(n)^2);
4290766078011253378100680198900819/56623104000000000000000000
gap> Decimal(last);
75777655.6723427486

which is reasonably close to 78322916 (the number being estimated, as given by McKay and Wanless).

Estimating 6-regular subgraphs of $K_{12,12}$ this way looks like it's going to take much longer (although, within reason).