Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
Actually, the probability of success is goes down like $\exp(-d^2/2),$ I think, so you might want to grab a coffee (and maybe a night's sleep). I used this method for the paper of Jakobson/Miller/Rivin/Rudnick (generating largish random $d$-regular graphs), and degree six was very slow. There is a paper by Van Vu (et al?) where the algorithm is sped up a lot, but the results are useful only for $n \gg d.$ Since $12$ is not $\gg$ anything, not useful there... –  Igor Rivin Dec 12 '10 at 4:30
    
Oops, comment is on the wrong problem (one of generating a random graph) -- the probability of success = probability of generating a simple graph. So, somewhat relevant... –  Igor Rivin Dec 12 '10 at 4:44
    
After generating 700,000,000 random permutations, it found 256 simple graphs, hence giving the estimate 129554937144. I could continue further, but there seems to be little point. –  Douglas S. Stones Dec 13 '10 at 11:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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