prob044: Steiner triple systems

proposed by Francisco Azevedo
fa@di.fct.unl.pt

References

A backtrack-free Prolog construction method is available at http://perso.wanadoo.fr/colin.barker/lpa/sts.htm

based on
Ian Anderson, Iiro Honkala: A Short Course in Combinatorial Designs  (1997) 41 pp.

A complete description with references can be found at:

Eric W. Weisstein. "Steiner Triple System." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/SteinerTripleSystem.html

Other References:

  1. L. Babai, Almost all Steiner triple systems are asymmetric, in Topics in Steiner systems (ed. C. C. Lindner and A. Rosa), Ann. Discrete Math. 7, Elsevier, Amsterdam, 1979, pp. 37-39.

  2. J. Doyen and R. M. Wilson, Embeddings of Steiner triple systems, Discrete Math. 5 (1973), 229-239.
  3. M. Hall, Jr., Automorphisms of Steiner triple systems, IBM J. Research Develop. 4 (1960), 460-472.
  4. P. Kaski and P. R. J. Östergård, The Steiner triple systems of order 19, Math. Comp. 73 (2004), 2075-2092.
  5. Petteri Kaski, Patric R. J. Östergård, Svetlana Topalova, and Rosen Zlatarski. Steiner triple systems of order 19 and
    21 with subsystems of order 7. Discrete Mathematics, to appear.
  6. D. K. Ray-Chaudhuri and R. M. Wilson, Solution of Kirkman's schoolgirl problem, Combinatorics, Proc. Symp. Pure Math. 19, 187-203 (1971).
  7. R. M. Wilson, Non-isomorphic Steiner triple systems, Math. Z. 135 (1974), 303-313.

[Lueneburg 1989] H. Lueneburg, Tools and Fundamental Constructions of Combinatorial Mathematics, Wissenschaftverlag, 1989.

[Lindner and Rosa 1980] C. C. Lindner and A. Rosa, Topics on Steiner Systems, Annals of Discrete Mathematics, Vol. 7, North Holland, 1980.

N. Beldiceanu, An Example of Introduction of Global Constraints in CHIP: Application to Block Theory Problems, Technical Report TR-LP-49, ECRC, Munich, Germany, 1990.

Some (Set) Constraint Programming Approaches:

C. Gervet, Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language, Constraints International Journal, Vol. 1, Number 3, Kluwer Academic Publishers, pages 191-244, March 1997.

Francisco Azevedo, Constraint Solving over Multi-valued Logics - Application to Digital Circuits, vol 91 of Frontiers of Artificial Intelligence and Applications, ISBN: 1 58603 304 2, IOS Press, xviii + 204 pages, 2003.

V. Lagoon and P.J. Stuckey Set domain propagation using ROBDDs In M. Wallace, editor, Proceedings of the Ninth International Conference on Principles and Practices of Constraint Programming, LNCS, pages 347-361. Springer-Verlag, 2004.