Hill-climbing to Pasch valleys

Exhaustive enumeration of Steiner Triple Systems is not feasible, due to the combinatorial explosion of instances. The next-best hope is to quickly find a sample that is representative of isomorphism classes. Stinson's Hill-Climbing algorithm [20] is widely used to produce random Steiner Triple Systems, and certainly finds a sample of systems quickly, but the sample is not uniformly distributed with respect to the isomorphism classes of STS with upsilon <= 19, and, in particular, we find that isomorphism classes with a large number of Pasch configurations are under-represented. No analysis of the non-uniformity of the distribution with respect to isomorphism classes or the intractability of obtaining a representative sample for upsilon > 19 is known. We also exhibit a modification to hill-climbing that makes the sample if finds closer to the uniform distribution over isomorphism classes in return for a modest increase in running time. (c) 2007 Wiley Periodicals, Inc.