The construction of antipodal triple systems by simulated annealing Original Research Article

An antipodal triple system of order v is a triple (V,B,f), where | V | = v, B is a set of cyclically oriented 3-subsets of V, and f: V → V is an involution with one fixed point such that: 1. (i) (V,B∪ f(B)) is a Mendelsohn triple system. 2. (ii) B ∩ f(B) = 0. 3. (iii) f is an isomorphism between the Steiner triple system (STS) (V,B′) and the STS (V, f(B′)), where B′ is the same as B without orientation. 4. (iv) f preserves orientation. An STS (V,B) is hemispheric if there exists a cyclic orientation B∗ of its block set B and an involution f such that (V,B∗, f) is an antipodal system. We use simulated annealing on a carefully chosen feasibility space to show that any STS(v) (V,B), where 7 ⩽ v ⩽ 15, is hemispheric, and conjecture that this is true for any STS(v) v > 3. We were unable to find a way of applying the alternative computational techniques of hill climbing and backtracking to this problem.