Skip to content

CSM

Seminar

A Markov chain for certain triple systems

Cameron, PJ (London)
Tuesday 25 March 2008, 14:35-15:05

Seminar Room 1, Newton Institute

Abstract

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.

Related Links

Presentation

[pdf ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧