[Nauty-list] genrang -r8 problem

Brendan McKay bdm at cs.anu.edu.au
Thu Aug 30 11:12:07 EST 2007


Yes, that is all correct with a caveat on the last part. This Markov
chain was one of the first that Jerrum and Sinclair analysed when
they introduced the Markov chain technique to combinatorics. However
their bounds are theoretical and don't easily translate into a
concrete statement of how long the chain needs to be run in order to
achieve a specified degree of uniformity.

The basic algorithm used now can be extended to higher degrees
using a sequence of switchings that correct the non-simpleness.
Nick Wormald and I published such an algorithm and Nick + Angelika
Steger published one which is however only asymptotically uniform.
I don't have implementations for either. I don't know of any finite
algorithm that works efficiently for really high degree (say, degree
close to n/2).  See
 http://www14.informatik.tu-muenchen.de/personen/steger/pub/dregular.ps.gz
for references.

Brendan.


* Gordon Royle <gordon at csse.uwa.edu.au> [070830 10:01]:
> 
> On 29/08/2007, at 9:02 PM, Brendan McKay wrote:
> 
> >It will terminate after a few days. The algorithm used for order n
> >and degree r takes time proportional to n*exp(r^2/4) for fixed r and
> >large n. For small n and large r, the time is worse.
> >
> >You can generate the complement instead if it has lower degree.
> >Otherwise you don't have an option except to implement a better
> >algorithm.
> >
> >Brendan.
> 
> If I recall correctly, the existing algorithm works by finding a  
> random perfect matching in graph with n groups of r vertices and then  
> squishing each group down to a single vertex thus creating a  
> multigraph with loops. So the limiting factor is the proportion of  
> these multigraphs with loops that happen to be simple - is that right?
> 
> Presumably it would be feasible to do a Markov chain type algorithm  
> based on doing "Ryser switches" on pairs of edges (using the fact  
> that any two graphs of the same degree sequence are related by a  
> sequence of such switches)... but presumably determining the mixing  
> time of such a Markov chain is impossibly difficult and hence we  
> would never know how long to run it before taking a sample...
> 
> Comments?
> --
> Associate Professor Gordon Royle
> Department of Computer Science & Software Engineering
> University of Western Australia
> http://people.csse.uwa.edu.au/gordon
> 
> 
> 




More information about the Nauty mailing list