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 ν ≤ 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 ν > 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. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 405–419, 2007