Linear Algebra Methods in Combinatorics — Examples

Each singleton has odd size $1$, and any two distinct singletons meet in the empty set of even size $0$, so the family satisfies Oddtown.

The displayed incidence matrix has pairwise orthogonal rows and $N{N}^{\mathsf{T}}=I_4$, exactly as the Oddtown proof predicts.

A fifth set cannot be adjoined: by [L1] an Oddtown family on four points has at most four members, and [L2] says the bound is attained already.

In both displayed families every set has even size, and the intersection of any two displayed sets is again $\mathrm{\varnothing }$, $\{0,1\}$, $\{2,3\}$ or $\{0,1,2,3\}$, hence even.

For $n=4$ there are four sets, which is $2^2=2^{\lfloor 4\mathrm{/}2\rfloor }$; for $n=5$ there are again four sets, which is $2^2=2^{\lfloor 5\mathrm{/}2\rfloor }$.

The $n=5$ family is maximal by [L2], so the floor in the general bound is visible already in the first odd case.

Each displayed set has size $3$.

Let $T=\{0,1,3\}$. Its nonzero differences are $\pm 1,\pm 2,\pm 3$, that is, every nonzero residue modulo $7$ exactly once. Hence for distinct translates $T+a$ and $T+b$, an element $x$ lies in their intersection exactly when $x-a$ and $x-b$ both lie in $T$, equivalently when $b-a$ is a nonzero difference of two elements of $T$; that determines $x$ uniquely. So any two distinct displayed sets meet in exactly one point.

So the family has $m=7$ subsets on $n=7$ points with constant pairwise intersection size $1$, and [L1] gives $7\le 7$. The bound is therefore tight.

The three displayed graphs cover the edges $\{0,1\},\{0,2\},\{0,3\}$; then $\{1,2\},\{1,3\}$; then $\{2,3\}$, so every edge of $K_4$ is covered exactly once.

Hence $K_4$ has a complete bipartite decomposition with three parts. Since $n-1=3$, [L1] says that no decomposition into two parts can exist.

The set $\{0,1\}$ is shattered: every one of its subsets appears as a trace of the displayed family.

No three-element subset is shattered, because the three-element set itself is missing from the family and therefore cannot appear as a trace on that triple. Hence $\mathrm{VC}(\mathcal{F})=2$.

The family has exactly $11$ members, matching the bound of [L1].

Row operations reduce the matrix to a row-echelon form with four pivot rows, so its rank is $4$.

This agrees with [L1].

Direct multiplication also gives $W_{0,1}(4)W_{1,2}(4)=2W_{0,2}(4),$ since every pair contains exactly two points.

The sumset is $A+B=\{0,1,2,3,4\},$ since the nine sums reduce to $0,1,2,1,2,3,2,3,4$ modulo $7$.

Therefore $\mid A+B\mid =5=3+3-1$, so the lower bound of [L1] is attained.

The other branch of the theorem is also visible: if $A=\{0,1,2,3\}$ and $B=\{0,1,2,3,4\}$, then $A+B=\mathbb{Z}\mathrm{/}7$.

The total degree of $f$ is $3=2+1$, and the coefficient of $x^{2}y$ is $1\mathrm{\ne }0$. Since $\mid S_1\mid =3>2$ and $\mid S_2\mid =2>1$, [L1] applies.

Indeed $f(1,1)=1+1+1+1=4\mathrm{\ne }0$, so the theorem's conclusion is visible directly.

Reducing modulo $g_2(y)=y(y-1)$ replaces $y^2$ by $y$, so on the grid the polynomial agrees with $x^{2}y+xy+x+y$, illustrating [L2].

Any two distinct displayed sets meet in either $0$ or $1$ point, so the family is $\{0,1\}$-intersecting.

The family has six members, and [L1] gives the upper bound $1+4+6=11$.

For example, the polynomial attached to $\{0,1\}$ over $\mathbb{R}$ is $f(x)=⟨x,v_{\{0,1\}}⟩(⟨x,v_{\{0,1\}}⟩-1)\mathrm{.}$ It is nonzero at $v_{\{0,1\}}$, where its value is $2$, and vanishes at every other displayed pair, whose intersection with $\{0,1\}$ has size $0$ or $1$.

Every nonzero vertex of the cube has some coordinate equal to $1$, so it lies on at least one of the hyperplanes $H_i$. The origin has no coordinate equal to $1$, so it lies on none of them.

Thus the $n$ hyperplanes $H_0,\dots ,H_{n-1}$ cover exactly the nonzero cube vertices. By [L1], no smaller family can do so.

By [L1], the family $\{\{0\},\dots ,\{n-1\}\}$ is an Oddtown family with $n$ members.

Since $n$ is not at most $n-1$, the false claim fails for every $n\ge 1$.

Each chosen set and each pairwise intersection is a union of some of the three disjoint pairs, hence has even size. Thus the family satisfies the Eventown conditions of [L1], and all pairwise intersections have the same parity.

The family has $2^3-1=7$ distinct nonempty members on $n=6$ points. Since $7>6$, it satisfies every hypothesis of the false claim and violates its conclusion.

The family $\{\mathrm{\varnothing },\{0\}\}$ has VC dimension $1$: it shatters $\{0\}$ and nothing larger.

It has two members, while $n^d=1^1=1$. So the false claim already fails at $n=1$, $d=1$.

The vector $x=(1,1)$ is nonzero, but [L1] gives $⟨x,x⟩=1+1=0$ in ${\mathbb{F}}_2$.

An inner product cannot vanish on a nonzero vector, so the false claim fails.

The polynomial $f$ has total degree $2=1+1$, and each grid has size $2>1$.

But $f(0,0)=f(0,1)=f(1,0)=f(1,1)=0$. So the conclusion of the false claim fails.

The missing hypothesis is exactly the coefficient of $xy$, which is $0$ here. That is why [L1] does not apply.

Over ${\mathbb{F}}_2$, the three incidence vectors sum to $(0,0,0)$, so they are linearly dependent.

Over $\mathbb{R}$, suppose $a(1,1,0)+b(0,1,1)+c(1,0,1)=0$. The three coordinates give $a+c=0$, $a+b=0$, and $b+c=0$. Hence $b=c=-a$ and the last equation gives $-2a=0$, so $a=b=c=0$. Thus the vectors are linearly independent over $\mathbb{R}$.

The four sums are $0+0=0$, $0+2=2$, $2+0=2$ and $2+2=0$, so $A+B=\{0,2\}$ and therefore $\mid A+B\mid =2$.

The Cauchy-Davenport lower bound would be $\min \{4,2+2-1\}=3$, so the inequality fails for this composite modulus.

The failure occurs outside the theorem's prime-modulus hypothesis: here the modulus is $4$, not a prime $p$, so [L1] does not apply.

The polynomial $P(x)=x(x-1)$ is nonzero and has degree $2=\mid S\mid$.

Yet $P(0)=0$ and $P(1)=0$, so $P$ vanishes on all of $S$.

Therefore the conclusion of [L1] fails when the strict inequality is replaced by equality.