A Tight Single-Change Covering Design with Block Size 6

Jul 16, 2026

Upload by Skyler

A tight single-change covering design with parameters v = 26 and k = 6 is presented, addressing Nineteenth British Combinatorial Conference Problem 1 on whether such designs exist for block size greater than 5. The work constructs the explicit design and reports its size: 63 blocks and 68 transfers. A satisfiability search is described in detail, including negative results for the smallest admissible order v = 21. Constraint programming methods are used throughout.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages9

Reading Time23 min

Introduction

Tightness and counting test

Standardisation and historical background

Main theorem

A satisfiability formulation

CP-SAT constraint model

arXiv :2607 . 10978v1 [math .CO] 13 Jul 2026 A tight single-change covering design with block size 6⋆ Richard Bean Cyber Research Centre, University of Queensland, 4072, Australia Abstract We give a tight single-change covering design with v = 26 and k = 6 . This answers Problem 1 of the Nineteenth British Combinatorial Conference, which asked whether such a design exists with block size greater than 5. We also describe the satisfiability search that found the design, including negative search results at the smallest admissible order v = 21 . Keywords: single-change covering design, tight single-change covering design, persistent pair, satisfiability, constraint programming 2020 MSC: 05B40, 05B30, 68R07 1. Introduction Following Wallis, Yucas and Zhang [3] and Preece et al. [6], a tight singlechange covering design, denoted tsccd(v, k), is an ordered sequence of ksubsets of S = {1 , 2 ,..., v}, with v > k, such that (i) any two elements of S occur together in at least one block (covering); (ii) each block after the first is obtained from the previous block by removing one element and inserting another (single change); and (iii) the element inserted to form any block after the first has not previously occurred in a block with any of the other elements of that block (tightness) . As is customary, we display a design as an array whose columns are the blocks, with unchanged elements kept in the same row and printed as dots; the tsccd(26 , 6) constructed here is shown in Table 1 . Each insertion of an element, including its first appearance, is a transfer. ⋆ Dedicated to the memory of Donald A. Preece (1939–2014), who posed this problem. Email address: [r.bean1@uq.edu.au](r.bean1@uq.edu.au) (Richard Bean) Tightness gives a useful counting test. When an element is inserted, it is paired with the k − 1 elements already present, none of which it has met before. Thus the first block creates 􀀀 k2􀀁 pairs, each later block creates exactly k − 1 new pairs, and no pair is created twice. Since all pairs must be covered, every pair occurs in exactly one run of consecutive blocks. If the design has b blocks, then 􀀒 v2􀀓 = 􀀒 k2􀀓 + (b − 1)(k − 1) , so b = 􀀀~~ ~~v~~2~~􀀁k~~ ~~−~~ ~~􀀀1k~~2~~􀀁 + 1 . (1) Counting the k elements of the first block as transfers, the total number of transfers is T = b + k − 1. Let ti be the number of elements transferred exactly i times, so Pi ti = v and Pi iti = T. An element transferred only once occurs in a single run of v − k + 1 consecutive blocks; no run can be longer. We call such an element an anchor. A pair occurring together in v − k consecutive blocks is a persistent pair [4, 6]; there are at most ⌊k/2⌋ persistent pairs [6] . A tsccd(v, k) is standardised [6, 9] if its first block is {1 , 2 ,..., k}, the other elements are first introduced in the order k + 1, k + 2 , , v, and the elements of the first block are first removed in the order k, k − 1 , , 1. Every design can be standardised by relabelling, so standardisation removes the action of the symmetric group on the labels. We use standardised designs throughout. The problem goes back to Nelder’s work on the economical formation of correlation matrices [1] and to the successive-block schemes of Gower and Preece [2] . Single-change covering designs were introduced in [3]; tight designs were studied in detail in [6], with a narrative account in [7] . The cases k = 2 (trivial), k = 3 [6], and k = 4 [8, 6] are well understood. For k = 5 , Phillips [9] found the smallest example, a tsccd(20 , 5) . Preece then asked whether any tight single-change covering design exists with k > 5; this became Problem 1 of the Nineteenth British Combinatorial Conference [10] . For k = 6, (1) requires 5 | 􀀀 v2􀀁 − 15, and Zhang’s bound [5] v (v − 1) ≥(6v − 7k)(k − 1) becomes (v − 10)(v − 21) ≥ 0; together these admit v = 21 , 25 , 26 , 30 , 31 , 35 , 36 , . . . , the smallest being v = 21, with b = 40 . Our result is the following. T

FAQs

What design is constructed in this document?

It constructs a tight single-change covering design tsccd(26, 6) with v = 26 and block size k = 6.

Why is the result important?

It answers Problem 1 of the Nineteenth British Combinatorial Conference, which asked whether tight single-change covering designs exist for block size greater than 5.

How was the design found?

The design was obtained using a satisfiability search formulated as a constraint programming model, implemented with Google OR-Tools CP-SAT.

Jul 16, 2026

Upload by Skyler