9 Designs 9.2 Fisher’s inequality for designs 9.4 Projective Planes

9.3 Finite linear spaces

A generalization of both projective planes but with similarities to designs is the notion of linear spaces . A linear space over $\mathcal{P}$ is a family ${\mathcal{L}}\subset 2^{\mathcal{P}}$ whose elements are called as lines and such that every line contains atleast two points and any two points are on a unique line. Projective planes can be characterized as linear spaces with every line containing exaclty $q+1$ points. We again denote the number of lines by $b$ .

An example of a linear space that is not a design is the near pencil. Here there is one line containing all but one point and other lines are pairs (i.e., lines of size $2$ ) containing that point. Trivially $b=v$ and any two lines intersect exactly at one point !

Even in linear spaces the number of lines exceeds the number of points unless $b=1$ .

Proposition 9.10 (De Bruijn-Erdős (1948)).

For a linear space either $b=1$ or $b\geq v$ and equality in the latter implies that any two lines intersect exactly at one point

Proof.

This is another nice double counting proof and due to Conway. For $x\in\mathcal{P}$ , let $r_{x}$ be the replication number and let $k_{L}$ be the cardinality of $L$ for $L\in{\mathcal{L}}$ .

If $x\notin L$ , then there exist at least $k_{L}$ lines containing $x$ and so $r_{x}\geq k_{L}$ . If $b\leq v$ then $bk_{L}\leq vr_{x}$ and so $b(v-k_{L})\geq v(b-r_{x})$ . Thus, we have that

b=\sum_{x}\frac{1}{v}\sum_{L:x\notin L}\frac{1}{b-r_{x}}\leq\sum_{x}\sum_{L:x% \notin L}\frac{1}{b(v-k_{L})}=\sum_{L}\sum_{x:x\notin L}\frac{1}{b(v-k_{L})}=1.

Thus all intermediate inequalities are equalities and in particular $b=v$ and $r_{x}=k_{L}$ . The latter in particular implies that any two lines have an intersection point and this must be unique. ∎