DIMACS Discrete Math/Theory of Computing Seminar


Blocking sets in projective planes


Tamas Szonyi
Budapest and Yale


DIMACS Seminar Room 431, CoRE Building
Busch Campus, Rutgers University


4:30 PM
Tuesday, April 2, 1996


A blocking set in PG(2,q) (or in a projective plane of order q) is a set of points intersecting each line. A blocking set is minimal, when no proper subset of it is a blocking set. The smallest blocking set is a line. Using purely combinatorial techniques Bruen (and independently Pelik\'an) proved in 1970 that a blocking set (not containing a line) in a plane of order q contains at least q+\sqrt q+1 points. In case of equality the blocking set must be a subplane of order \sqrt q. Hence Bruen's result is sharp for PG(2,q), q square. Further combinatorial results were obtained later by Bruen--Thas, Bruen--Silverman, Bierbrauer and Kitto.

In case of affine planes Jamison and independently Brouwer--Schrijver proved that a blocking set of AG(2,q) contains at least 2q-1 points. This is sharp: take a line and one-one point on each line parallel to it. Their proof used polynomials over GF(q) in an ingenious way. This method is quite characteristic for Galois geometry. If one studies combinatorial properties of point sets in a projective plane the proofs often combine purely combinatorial arguments with algebraic tools using the coordinatizing field. A classical example is Segre's theory of complete arcs: to an arc an algebraic curve is associated which reflects some geometric properties of the arc.

In 1994 Blokhuis improved substantially the previously known bounds if q is not a square. His result is particularly attractive if q=p is a prime: a blocking set of PG(2,q) not containing a line contains at least 3(p+1)/2 points and this is sharp. In Blokhuis' proof lacunary polynomials, introduced by R\'edei, played a crucial role.

Recently, the present author introduced a method of associating a pair of curves to a minimal blocking set. The points of both curves correspond to lines intersecting the blocking set in more than one point. In particular, the two curves have the same set of GF(q)-rational points. Using this pair of curves one can prove that a blocking set of size less than 3(q+1)/2 intersects each line in 1 modulo p points confirming a conjecture of Blokhuis. In the particular case q=p^2 one can also show that a minimal blocking set (which is not a line) is either a subplane of order \sqrt q or contains at least 3(q+1)/2 points.

Document last modified on March 25, 1996