Scholarlink

<p>The Kramer–Mesner method for constructing designs with a prescribed automorphism group&#xa0;<i>G</i> has proven effective many times. In the special case of Steiner designs, the task reduces to solving an exact cover problem, with the advantage that fast backtracking solvers like Donald Knuth’s <i>dancing links</i> and <i>dancing cells</i> can be used. We find ways to encode the inherent symmetry of the problem space, induced by the action of the normalizer of <i>G</i>, into a single instance of the exact cover problem. This eliminates redundant computations of certain isomorphic search branches, while preventing the overhead caused by repeatedly restarting the solver. Our improved approach is applied to the parameters <i>S</i>(2,&#xa0;6,&#xa0;91). Previously, only four such Steiner designs were known, all of which had been constructed as cyclic designs over four decades ago. We find 23 new designs, each with full automorphism group of order 84.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Some new Steiner designs S(2, 6, 91)

  • 期刊论文

  • 发表日期：

    2025年9月9日

查看全文
  • Michael Kiermaier,
  • Vedran Krčadinac,
  • Vladimir D. Tonchev,
  • Renata Vlahović Kruc,
  • Alfred Wassermann

摘要

The Kramer–Mesner method for constructing designs with a prescribed automorphism group G has proven effective many times. In the special case of Steiner designs, the task reduces to solving an exact cover problem, with the advantage that fast backtracking solvers like Donald Knuth’s dancing links and dancing cells can be used. We find ways to encode the inherent symmetry of the problem space, induced by the action of the normalizer of G, into a single instance of the exact cover problem. This eliminates redundant computations of certain isomorphic search branches, while preventing the overhead caused by repeatedly restarting the solver. Our improved approach is applied to the parameters S(2, 6, 91). Previously, only four such Steiner designs were known, all of which had been constructed as cyclic designs over four decades ago. We find 23 new designs, each with full automorphism group of order 84.