Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.04293 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909811515326464 |
|---|---|
| author | Kiermaier, Michael Krčadinac, Vedran Tonchev, Vladimir D. Kruc, Renata Vlahović Wassermann, Alfred |
| author_facet | Kiermaier, Michael Krčadinac, Vedran Tonchev, Vladimir D. Kruc, Renata Vlahović Wassermann, Alfred |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04293 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Some new Steiner designs $S(2,6,91)$ Kiermaier, Michael Krčadinac, Vedran Tonchev, Vladimir D. Kruc, Renata Vlahović Wassermann, Alfred Combinatorics 05B05 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$. |
| title | Some new Steiner designs $S(2,6,91)$ |
| topic | Combinatorics 05B05 |
| url | https://arxiv.org/abs/2504.04293 |