Embeddings
A Steiner Triple System S is said to be “embedded in” another Steiner Triple System T iff every triple in S is also contained in T and the order of S is less than the order of T.
For instance, this Steiner Triple System of order 3:
{{1,2,3}}
Is “embedded in” this Steiner Triple System of order 9:
{{1,2,3}, {4,5,6}, {7,8,9}, {1,4,7}, {2,5,8}, {3, 6, 9}, {1, 5, 9}, {2, 6, 7}, {3, 4, 8}, {1, 6, 8}, {2, 4, 9}, {3, 5, 7}}
In this paper it is shown that for any Steiner Triple System of order v, there exists a Steiner Triple System of order u >= 2v + 1, such that the STS of order v is embedded in the STS of order u.
A related paper addresses embeddings of “partial Steiner Triple Systems”: systems that contain AT MOST one triple containing each pair in its input set rather than EXACTLY one triple. This paper demonstrates that for some partial Steiner Triple Systems of order v there exists Steiner Triple Systems of order u < 2v + 1 that embed the partial STS.
Other Ways to Generate Steiner Triple Systems
There are a number of ways to generate Steiner Triple Systems with computers, many of which rely on exhaustive searches. Our method, while it is not exhaustive of all possible triple systems, does in the worst case require an exhaustive search for an NS1D0 sequence. This paper presents a genetic algorithm that can generate Steiner Triple Systems without performing an exhaustive search.
Another paper presents a way to specifically find orthogonal Steiner Triple Systems: a pair of systems that have no common triples, and for which if the triples {x, y, z} and {u, v, z} are in the first system, then for {x, y, a} and {u, v, b} a must not equal b.
Comentarios