K-Chains Problem and Why it Matters for Extremal Contexts

NEW

Problem: Reconstructed conjecture: for positive integers $k\mid n$, every finite formal context $(G,M,I)$ with $|G|+|M|=2n$ and VC-dimension at most $k$ has at most $(n/k)^k$ concepts, with equality attained by the Cartesian product of $k$ chains $C(n/k)$. The VC-dimension convention is ambiguous, but the counterexample below has VC-dimension $2$ under the usual attribute-extents convention and also under the concept-extents convention.

Result: The conjecture is false already for $k=2,n=4$.

Let

with attribute extents

Thus $|G|+|M|=8=2n$.

The concept extents are exactly the intersections of these four sets, including the empty intersection $G$:

Hence the concept lattice has $10$ elements.

The attribute family shatters $\{1,3\}$:

No 3-set can be shattered by the four attribute extents, since shattering a 3-set would require $8$ distinct traces. Thus the usual VC-dimension is exactly $2$.

If VC-dimension is instead taken for the whole concept-extents family, it is still $2$: pairs are shattered, but every 3-subset contains either $\{1,2\}$ or $\{3,4\}$, and neither of those appears as a trace of a concept extent on such a triple.

For $k=2,n=4$, the conjectured maximum is

but this context has $10$ concepts. Even the natural off-by-one repair $(n/k+1)^k=3^2=9$ is refuted by the same example. The context is finite, balanced, and reduced; the failure is not caused by duplicate rows/columns or an empty/vacuous case.

Citation: No external citation is needed; this is an explicit finite counterexample.