9 Designs 9.4 Projective Planes 9.6 Affine Planes

9.5 Blocking Set

A blocking set in a projective plane is a set of points intersecting every line. Trivially points in a line form a blocking set of cardinality $q+1$ and they are called trivial blocking sets. Thus non-trivial blocking sets are blocking sets which do not contain a line. If $q=1$ , there is no non-trivial blocking set. Let $q\geq 2$ . Can we have non-trivial blocking sets of cardinality $q+2,q+3$ and so on ? Trivially, we can rule out non-trivial blocking sets of cardinality $q+1$ .

Lemma 9.12.

If $B$ is a non-trivial blocking set in a projective plane of order $q$ , then $|B|\geq q+2$ .

Proof.

Let $x\neq y\in B$ and $L$ be the line determined by $x, y$ . Let $z\in L-B$ . Since there are $q+1$ lines through $z$ , there are $q$ lines through $z$ apart from $L$ . The only common point to each of these lines (including $L$ ) is $z$ and so each of the lines intersect a distinct point of $B$ apart from $x, y$ . Thus $|B|\geq q+2$ . ∎

Generalizing the argument, we conclude the following.

Lemma 9.13.

If $B$ is a non-trivial blocking set in a projective plane of order $q$ and $|B|=q+m$ then any line intersects with at most $m$ points in $B$ .

Proof.

Let $L$ be a line intersecting with $t$ points in $B$ . Let $z\in L-B$ and there are again $q$ lines through $z$ apart from $L$ . Eeach of these lines intersect a distinct point of $B$ apart from those in $L\cap B$ . Thus we have that $q+t\leq|B|=q+m$ and so implying $t\leq m$ as required. ∎

Using this, we derive the Bruen’s theorem extending the cardinality of non-trivial blocking sets even further.

Theorem 9.14 (Bruen 1970).

If $B$ is a non-trivial blocking set in a projective plane of order $q$ , then $|B|\geq q+\sqrt{q}+1$ .

Proof.

Assume $|B|=q+m$ for some $m\leq\sqrt{q}+1$ . Let $l_{i}$ be the number of lines that intersect exactly $i$ points in $B$ . By Lemma 9.13, $l_{i}=0$ for $i>m$ . Now double-counting lines, pairs $(x,L)$ such that $x\in B\cap L$ , triples $(x,y,L)$ such that $x\neq y\in B\cap L$ , we have

	$\displaystyle\sum_{i=1}^{m}l_{i}$	$\displaystyle=b=q^{2}+q+1,$
	$\displaystyle\sum_{i=1}^{m}il_{i}$	$\displaystyle=r\|B\|=(q+1)\|B\|,$
	$\displaystyle\sum_{i=1}^{m}i(i-1)l_{i}$	$\displaystyle=\|B\|(\|B\|-1).$

Since $m\leq\sqrt{q}+1$ we have $i\leq\sqrt{q}+1$ for all $i\leq m$ . Putting together,

	$\displaystyle 0$	$\displaystyle\geq\sum_{i=1}^{m}(i-1)(i-\sqrt{q}-1)l_{i}$
		$\displaystyle=\sum_{i}i(i-1)l_{i}-(\sqrt{q}+1)\sum_{i=1}^{m}il_{i}-(\sqrt{q}+1% )\sum_{i}l_{i}$
		$\displaystyle=\|B\|(\|B\|-1)-(\sqrt{q}+1)\|B\|(q+1)-(\sqrt{q}+1)(q^{2}+q+1)$
		$\displaystyle=[\|B\|-(q+\sqrt{q}+1)]\times[\|B\|-(q\sqrt{q}+1)].$

Since $|B|\leq q+\sqrt{q}+1$ , $|B|<q\sqrt{q}+1$ as $q\geq 2$ . Thus the above inequality implies that $|B|=q+\sqrt{q}+1$ . ∎

Exercise(A) 9.15.

Let $B$ be a non-trivial blokcing set in a projective plane of order $q$ . Show that $|B|\leq q^{2}-\sqrt{q}$ .

Exercise(A) 9.16.

Let $S$ be a set of $q+2$ points in a projective plane of order $q$ . Show that $|L\cap S|\geq 2$ for any line $L$ such that $L\cap S\neq\emptyset$ .

Exercise(A) 9.17.

Let $S$ be a set of points of a projective plane of order $q$ . Suppose that non three points of $S$ are colinear (i.e., lie on a line). Prove that then $|S|\leq q+1$ if $q$ is odd and $|S|\leq q+2$ if $q$ is even.

Exercise(A) 9.18.

Let $M$ be incidence matrix of a symmetric $2-(v,k,\lambda)$ design. Show that $N^{T}$ also is incidence matrix of a design.