In geometry, specifically projective geometry, a blocking set is a set of points in a projective plane that every line intersects and that does not contain an entire line.
A second way to generalize would be to move into more abstract settings than projective geometry.
In a finite projective plane π of order n, a blocking set is a set of points of π that every line intersects and that contains no line completely.
A blocking set of smallest size is called a committee.
[1] It is sometimes useful to drop the condition that a blocking set does not contain a line.
In any projective plane of order n (each line contains n + 1 points), the points on the lines forming a triangle without the vertices of the triangle (3(n - 1) points) form a minimal blocking set (if n = 2 this blocking set is trivial) which in general is not a committee.
This produces a minimal blocking set of size 2n.
A projective triangle β of side m in PG(2,q) consists of 3(m - 1) points, m on each side of a triangle, such that the vertices A, B and C of the triangle are in β, and the following condition is satisfied: If point P on line AB and point Q on line BC are both in β, then the point of intersection of PQ and AC is in β.
A projective triad δ of side m is a set of 3m - 2 points, m of which lie on each of three concurrent lines such that the point of concurrency C is in δ and the following condition is satisfied: If a point P on one of the lines and a point Q on another line are in δ, then the point of intersection of PQ with the third line is in δ. Theorem: In PG(2,q) with q odd, there exists a projective triangle of side (q + 3)/2 which is a blocking set of size 3(q + 1)/2.
[2] Theorem: In PG(2,q) with q even, there exists a projective triad of side (q + 2)/2 which is a blocking set of size (3q + 2)/2.
[3] Theorem: In PG(2,p), with p a prime, there exists a projective triad of side (p + 1)/2 which is a blocking set of size (3p+ 1)/2.
[4] One typically searches for small blocking sets.
In the Desarguesian projective plane of order q, PG(2,q), the size of a blocking set B is bounded:[5] When q is a square the lower bound is achieved by any Baer subplane and the upper bound comes from the complement of a Baer subplane.
A more general result can be proved,[6] Any blocking set in a projective plane π of order n has at least
Moreover, if this lower bound is met, then n is necessarily a square and the blocking set consists of the points in some Baer subplane of π.
An upper bound for the size of a minimal blocking set has the same flavor,[7] Any minimal blocking set in a projective plane π of order n has at most
Moreover, if this upper bound is reached, then n is necessarily a square and the blocking set consists of the points of some unital embedded in π.
When n is not a square less can be said about the smallest sized nontrivial blocking sets.
One well known result due to Aart Blokhuis is:[4] Theorem: A nontrivial blocking set in PG(2,p), p a prime, has size at least 3(p + 1)/2.
In these planes a projective triangle which meets this bound exists.
Blocking sets originated[8] in the context of economic game theory in a 1956 paper by Moses Richardson.
[9] Players were identified with points in a finite projective plane and minimal winning coalitions were lines.
Jane W. DiPaola studied the minimum blocking coalitions in all the projective planes of order
[12] In any projective plane of order q, for any nontrivial blocking set B (with b = |B|, the size of the blocking set) consider a line meeting B in n points.
If for some line equality holds in this relation, the blocking set is called a blocking set of Rédei type and the line a Rédei line of the blocking set (note that n will be the largest number of collinear points in B).
[14] A set of points in the finite Desarguesian affine space
Jean Doyen conjectured in a 1976 Oberwolfach conference that this is the least possible size of a blocking set.
This was proved by R. E. Jamison in 1977,[15] and independently by A. E. Brouwer, A. Schrijver in 1978 [16] using the so-called polynomial method.
Jamison proved the following general covering result from which the bound on affine blocking sets follows using duality: Let