A combinatorial design is equivalent to a stable set in a suitably chosen Johnson graph, whose vertices correspond to all k-sets that could be blocks of the design. In order to find maximum stable sets of a graph G, two ideals are associated with G, one constructed from the Motzkin-Strauss formula and one reported by Lova ?sz in connection with the stability polytope. These ideals are shown to coincide and form the stability ideal of G. Graph stability ideals belong to a class of 0-1 ideals. These ideals are shown to be radical, and therefore have a strong structure. Stability ideals of Johnson graphs provide an algebraic char- acterization that can be used to generate Steiner triple systems. Two different ideals for the generation of Steiner triple systems, and a third for Kirkman triple systems, are developed. The last of these combines stability and colorings
展开▼
