Paperlane

no. 2 · Monday 26 October 2026

Links of minimum degree and exact covering numbers

Alfonso Gippini Requeijo

math.CO · via cs.DM · 11 pp

Abstract

The covering number $C(v,k,t)$ is the least number of $k$-subsets, called blocks, of a $v$-set such that every $t$-subset lies in one of them. We reduce the question whether a covering with $L$ blocks exists to the classification of links. If every point of such a covering lies in at least $r$ blocks and $(r+1)v>kL$, some point lies in exactly $r$ blocks, and its link, the blocks through it with the point removed, is a $(v-1,k-1,t-1)$-covering with $r$ blocks. It then suffices to list these links up to isomorphism, to prove the list complete, and to show that no link in the list extends to a covering with $L$ blocks. Completeness is certified by one unsatisfiable formula that excludes the listed classes, so the program that lists the links need not be trusted. In general the last two steps are decided by propositional satisfiability (SAT) solving, with every formula written by two separately implemented encoders and every refutation checked by a formally verified proof checker. For links with four blocks and $t=3$ we give the classification by hand, under a condition on the parameters. As an application we determine twenty-five covering numbers with $t\in\{3,4,5\}$ in which the published lower bound was one less than the size of a known covering, among them $C(39,24,3)=9$.

comments
11 pages, 1 figure, 1 table. Code, class lists, logs, DRAT proofs and a long version: https://doi.org/10.5281/zenodo.23434567
fields
Combinatorics
pdf ↗ page arXiv:2610.31696 ↗