A Survey of Forbidden Configuration Results

NEW

Problem: Reconstructed statement (standard forbidden-configuration notation): let $K_k$ be the $k\times 2^k$ $(0,1)$-matrix containing all binary columns. A configuration $F'\prec K_k$ is critical if it is minimal under $\prec$ among configurations satisfying

For $k\ge2$, the only $(k-1)$-rowed critical substructures of $K_k$ are

This is supported by the survey’s definitions of $K_k$, $t\cdot A$, configurations, and critical substructures.

Result: Let $r=k-1$ and

by Sauer–Shelah.

First,

Indeed, avoiding $2\cdot 1_r$ means no $r$-set of rows is contained in two distinct columns/sets. Hence the columns of size at least $r$ inject into the $r$-subsets of $[m]$, while all columns of size $<r$ contribute at most $\sum_{i<r}\binom mi$. Equality is attained by all sets of size at most $r$. By complementation,

Their only proper nonempty substructures are $1_r$ and $0_r$, whose forbidden numbers are $\sum_{i=0}^{r-1}\binom mi<S_r(m)$ for large $m$. Thus both are critical.

Now define

the largest $r$-rowed subconfiguration of $K_{r+1}$ containing neither $2\cdot 0_r$ nor $2\cdot 1_r$.

We prove that, for $r\ge2$ and $m\ge 2r-1$,

Suppose not. Let $\mathcal A\subseteq 2^{[m]}$ be $H_r$-free with $|\mathcal A|=S_r(m)$. Since $H_r\prec K_{r+1}$, $\mathcal A$ is $K_{r+1}$-free and is therefore a maximum VC-dimension-$r$ family.

A standard equality-case consequence of the Sauer induction is: for every $U\subseteq[m]$ with $|U|=r+1$, the trace $\mathcal A|_U$ is missing exactly one binary pattern. Denote it by $\phi_U$. Also every $r$-set is shattered.

For an $r$-set $S$, since $H_r$ is absent on $S$, some nonconstant trace $\tau_S\in\{0,1\}^S$ occurs exactly once. If $x\notin S$, then among the two extensions of $\tau_S$ to $S\cup\{x\}$, exactly one appears, so the unique missing pattern satisfies

Thus for every $(r+1)$-set $U$, the traces $\tau_{U\setminus\{x\}}$ are all restrictions of the same $\phi_U$. Hence the $\tau_S$’s are mutually compatible on overlaps. Therefore there is a global binary vector $g\in\{0,1\}^{[m]}$ such that

for every $r$-set $S$.

But each $\tau_S$ is nonconstant, so no $r$-set lies entirely inside the 1-set of $g$, and no $r$-set lies entirely inside the 0-set of $g$. Hence both the number of ones and the number of zeros in $g$ are at most $r-1$, giving

contradicting $m\ge2r-1$. Therefore $\operatorname{forb}(m,H_r)<S_r(m)$ for large $m$.

Now let $F\prec K_{r+1}$ be $r$-rowed. If $F$ contains neither $2\cdot0_r$ nor $2\cdot1_r$, then $F\prec H_r$, so

for large $m$. Thus $F$ is not critical.

If $F$ contains $2\cdot0_r$ or $2\cdot1_r$, then $\operatorname{forb}(m,F)=S_r(m)$, but $F$ is minimal only when $F$ is exactly that contained duplicate extreme column configuration. Hence the only $(k-1)$-rowed critical substructures of $K_k$ are

Audit: the proof uses exactly the standard configuration order, simple matrices/set systems, and exact equality of forbidden functions; no extra regularity assumptions are introduced. The strict inequality for $H_r$ holds for all sufficiently large $m$, which is enough to exclude equality as a forbidden-number function.

Citation: Uses the Sauer–Perles–Shelah / Vapnik–Chervonenkis theorem: Sauer, N. “On the density of families of sets.” J. Combin. Theory A 13 (1972), 145–147; Shelah, S. “A combinatorial problem; stability and order for models and theories in infinitary languages.” Pacific J. Math. 41 (1972), 247–261; Vapnik and Chervonenkis (1971). No prior resolution of this specific problem is invoked.