2026/07/26 by Charlie Krug
Mathematics · #math.CO
A t-(v,k,λ) covering is a collection of k-subsets (blocks) of a v-set such that every t-subset of points lies in at least λ blocks; the covering number Cλ(v,k,t) is the least number of blocks in such a collection, and one writes C(v,k,t) when λ=1. The recorded bounds for C(12,6,4) have been 40 ≤ C(12,6,4) ≤ 41. We show that no 4-(12,6,1) covering with 40 blocks exists, and hence that C(12,6,4)=41. A counting argument shows that in a hypothetical 40-block covering every point lies in exactly 20 blocks, the link of every point is an optimal 3-(11,5,1) covering with a forced degree sequence, and the six pairs of points of degree 10 form a perfect matching; an exhaustive case analysis over the orbits of a group of order 3840, carried out by satisfiability solving, then shows that no optimal 3-(11,5,1) covering occurs as such a link. Each of the 81 formulas in the primary proof has an unsatisfiability certificate checked by drat-trim and by the formally verified checker cakelpr; two additional cross-encoding certificates are checked by the same pipeline. The lower-bound argument uses no tabulated covering number: its only numerical input, C(10,4,2) ≥ 9, is itself certified. As a by-product the certificates yield a self-contained certified proof that the optimal 3-(11,5,1) covering is unique up to isomorphism. Equivalently, the Turán number T(12,8,6) is 41; the new value propagates to improved lower bounds for C(13,7,5), C(14,8,6), C(15,9,7) and C(16,10,8).