Tight single-change covering designs at small orders: exact counts and unconditional non-existence

Abstract

A tight single-change covering design tsccd(v,k) is an ordered sequence of k-subsets of {1,…,v} in which each block after the first is obtained from its predecessor by removing one point and inserting another, every pair of points occurs together in some block, and the point inserted at each step has never before shared a block with any of its new block-mates. Preece asked at the Nineteenth British Combinatorial Conference for such a design with block size greater than five, and Bean's tsccd(26,6) answers that question. We settle several small orders exactly. There are exactly 32 standardised tsccd(7,3); we have found no source that states this number, the standard survey printing six representatives and no total. There are exactly 1440 tight single-change covering designs on six labelled points with block size three, and there is no tsccd(6,4) and no tsccd(7,4) at all — with no canonical form assumed anywhere. At five further orders, (9,4), (10,4), (11,6), (12,5) and (10,6), no standardised design exists. What makes these statements about designs rather than about a program is a completeness theorem for the enumeration procedure, proved with no computation, together with a proof of the counting identity C(v, 2)=C(k, 2)+(b-1)(k-1) for all parameters, which forces the number of blocks and yields congruence obstructions ruling out a positive proportion of orders with no search at all. We also record a verification, inside the proof kernel, of Bean's design and of every statistic published about it. All statements are machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   a23fad9834853de6945698c0f2861aca10ff0a698325124a94aaf98d514d75d2