A Markov chain for certain triple systems
Seminar Room 1, Newton Institute
In 1996, M. T. Jacobson and P. Matthews constructed a Markov chain whose limiting distribution is uniform on Latin squares. This has been a useful tool for exploring the properties of random Latin squares. However, very little is known about the rate of convergence of the Markov chain; more information about this would greatly enhance its value.
A feature of the Jacobson-Matthews Markov chain is that it enlarges the search space by adding "improper" Latin squares which have one "fault"; when we move from an improper Latin square we must fix that fault but may create another one.
The method has been extended to other classes of combinatorial structures (Steiner triple systems and 1-factorizations of complete graphs), and to more general versions of these (corresponding to the generalization from Steiner triple systems to BIBDs with an arbitrary value of lambda. Unfortunately, except in the case of orthogonal arrays (the generalization of Latin squares), the connectedness of the Markov chain is conjectured, but not known to hold. If the conjecture is true, then the limiting distribution in each of these cases will be uniform.
- http://www.maths.qmul.ac.uk/~pjc/preprints/gendesdm.pdf - Preprint of paper on the generalisation
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.