Hill-climbing to Pasch valleys

✍ Scribed by Danny Heap; Peter Danziger; Eric Mendelsohn

• Book ID: 102308208
• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 159 KB
• Volume: 15
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20142

✦ Synopsis

Abstract

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