Blocking set

<h2 id="definition">Definition</h2>
In a finite <a href="/facts/Projective_plane/p6ot8oNv">projective plane</a> π of order n, a blocking set is a set of points of π that every line intersects and that contains no line completely. Under this definition, if B is a blocking set, then complementary set of points, π\B is also a blocking set. A blocking set B is minimal if the removal of any point of B leaves a set which is not a blocking set. A blocking set of smallest size is called a committee. Every committee is a minimal blocking set, but not all minimal blocking sets are committees. Blocking sets exist in all projective planes except for the smallest projective plane of order 2, the <a href="/facts/Fano_plane/nNuh1gkH">Fano plane</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
It is sometimes useful to drop the condition that a blocking set does not contain a line. Under this extended definition, and since, in a projective plane every pair of lines meet, every line would be a blocking set. Blocking sets which contained lines would be called trivial blocking sets, in this setting.

<h2 id="examples">Examples</h2>
In any <a href="/facts/Projective_plane/p6ot8oNv">projective plane</a> 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.
Another general construction in an arbitrary projective plane of order n is to take all except one point, say P, on a given line and then one point on each of the other lines through P, making sure that these points are not all <a href="/facts/Collinear/SxbVBJYR">collinear</a> (this last condition can not be satisfied if n = 2.) 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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

Using <a href="/facts/Homogeneous_coordinates/TG9ebKN4">homogeneous coordinates</a>, let the vertices of the triangle be A = (1,0,0), B = (0,1,0) and C = (0,0,1). The points, other than the vertices, on side AB have coordinates of the form (-c, 1, 0), those on BC have coordinates (0,1,a) and those on AC have coordinates (1,0,b) where a, b and c are elements of the finite field GF(q). Three points, one on each of these sides, are collinear if and only if a = bc. By choosing all of the points where a, b and c are nonzero squares of GF(q), the condition in the definition of a projective triangle is satisfied.
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.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

The construction is similar to the above, but since the field is of <a href="/facts/Characteristic_(algebra)/D2VzcQaG">characteristic 2</a>, squares and non-squares need to be replaced by elements of <a href="/facts/Field_trace/shd5K3gR">absolute trace</a> 0 and absolute trace 1. Specifically, let C = (0,0,1). Points on the line X = 0 have coordinates of the form (0,1,a), and those on the line Y = 0 have coordinates of the form (1,0,b). Points of the line X = Y have coordinates which may be written as (1,1,c). Three points, one from each of these lines, are collinear if and only if a = b + c. By selecting all the points on these lines where a, b and c are the field elements with absolute trace 0, the condition in the definition of a projective triad is satisfied.
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.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="size">Size</h2>
One typically searches for small blocking sets. The minimum size of a blocking set of 
 
 
 
 H
 
 
 {\displaystyle H}
 
 is called 
 
 
 
 τ
 (
 H
 )
 
 
 {\displaystyle \tau (H)}
 
.
In the <a href="/facts/Desarguesian_plane/p6ot8oNv">Desarguesian projective plane</a> of order q, PG(2,q), the size of a blocking set B is bounded:<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

q
        +
        
          
            q
          
        
        +
        1
        ≤
        
          |
        
        B
        
          |
        
        ≤
        
          q
          
            2
          
        
        −
        
          
            q
          
        
        .
      
    
    {\displaystyle q+{\sqrt {q}}+1\leq |B|\leq q^{2}-{\sqrt {q}}.}

When q is a <a href="/facts/Square_number/jfakASPK">square</a> the lower bound is achieved by any Baer <a href="/facts/Projective_plane/p6ot8oNv">subplane</a> and the upper bound comes from the complement of a Baer subplane.
A more general result can be proved,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
Any blocking set in a projective plane π of order n has at least 
 
 
 
 n
 +
 
 
 n
 
 
 +
 1
 
 
 {\displaystyle n+{\sqrt {n}}+1}
 
 points. 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,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Any minimal blocking set in a projective plane π of order n has at most 
 
 
 
 n
 
 
 n
 
 
 +
 1
 
 
 {\displaystyle n{\sqrt {n}}+1}
 
 points. Moreover, if this upper bound is reached, then n is necessarily a square and the blocking set consists of the points of some <a href="/facts/Unital_(geometry)/pUDo5NRU">unital</a> 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:<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
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.

<h2 id="history">History</h2>
Blocking sets originated<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> in the context of economic <a href="/facts/Game_theory/zkEIj1ya">game theory</a> in a 1956 paper by Moses Richardson.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> Players were identified with points in a finite <a href="/facts/Projective_plane/p6ot8oNv">projective plane</a> and minimal winning coalitions were lines. A blocking coalition was defined as a set of points containing no line but intersecting every line. In 1958, J. R. Isbell<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> studied these games from a non-geometric viewpoint. Jane W. DiPaola studied the minimum blocking coalitions in all the projective planes of order 
 
 
 
 ≤
 9
 
 
 {\displaystyle \leq 9}
 
 in 1969.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="in-hypergraphs">In hypergraphs</h2>
Let 
 
 
 
 H
 =
 (
 X
 ,
 E
 )
 
 
 {\displaystyle H=(X,E)}
 
 be a hypergraph, so that 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a set of elements, and 
 
 
 
 E
 
 
 {\displaystyle E}
 
 is a collection of subsets of 
 
 
 
 X
 
 
 {\displaystyle X}
 
, called (hyper)edges. A blocking set of 
 
 
 
 H
 
 
 {\displaystyle H}
 
 is a subset 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 that has nonempty intersection with each hyperedge.
Blocking sets are sometimes also called "<a href="/facts/Hitting_set/MVzyBYs1">hitting sets</a>" or "<a href="/facts/Vertex_cover/WK86bJvf">vertex covers</a>".
Also the term "<a href="/facts/Transversal_(combinatorics)/HFg4qQfj">transversal</a>" is used, but in some contexts a transversal of 
 
 
 
 H
 
 
 {\displaystyle H}
 
 is a subset 
 
 
 
 T
 
 
 {\displaystyle T}
 
 of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 that meets each hyperedge in exactly one point.
A "<a href="/facts/Hypergraph/qIR2o2I3">two-coloring</a>" of 
 
 
 
 H
 
 
 {\displaystyle H}
 
 is a partition 
 
 
 
 {
 C
 ,
 D
 }
 
 
 {\displaystyle \{C,D\}}
 
 of 
 
 
 
 X
 
 
 {\displaystyle X}

into two subsets (color classes) such that no edge is monochromatic, i.e., no edge is contained entirely within 
 
 
 
 C
 
 
 {\displaystyle C}
 
 or within 
 
 
 
 D
 
 
 {\displaystyle D}
 
. Now both 
 
 
 
 C
 
 
 {\displaystyle C}
 
 and 
 
 
 
 D
 
 
 {\displaystyle D}
 
 are blocking sets.

<h2 id="complete-k-arcs">Complete k-arcs</h2>
In a <a href="/facts/Projective_plane/p6ot8oNv">projective plane</a> a <a href="/facts/Arc_(projective_geometry)/2yvR6hVe">complete k-arc</a> is a set of k points, no three <a href="/facts/Collinear/SxbVBJYR">collinear</a>, which can not be extended to a larger arc (thus, every point not on the arc is on a secant line of the arc–a line meeting the arc in two points.)
Theorem: Let K be a complete k-arc in Π = PG(2,q) with k < q + 2. The <a href="/facts/Duality_(projective_geometry)/dxrjhRbB">dual</a> in Π of the set of secant lines of K is a blocking set, B, of size k(k - 1)/2.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<h2 id="rdei-blocking-sets">Rédei blocking sets</h2>
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. Since no line is contained in B, there must be a point, P, on this line which is not in B. The q other lines though P must each contain at least one point of B in order to be blocked. Thus, 
 
 
 
 b
 ≥
 n
 +
 q
 .
 
 
 {\displaystyle b\geq n+q.}
 
 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).<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> Not all blocking sets are of Rédei type, but many of the smaller ones are. These sets are named after <a href="/facts/L%C3%A1szl%C3%B3_R%C3%A9dei/QkDzRIGk">László Rédei</a> whose monograph on Lacunary polynomials over finite fields was influential in the study of these sets.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

<h2 id="affine-blocking-sets">Affine blocking sets</h2>
A set of points in the finite Desarguesian affine space 
 
 
 
 A
 G
 (
 n
 ,
 q
 )
 
 
 {\displaystyle AG(n,q)}
 
 that intersects every hyperplane non-trivially, i.e., every hyperplane is incident with some point of the set, is called an affine blocking set. Identify the space with 
 
 
 
 
 
 F
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle \mathbb {F} _{q}^{n}}
 
 by fixing a coordinate system. Then it is easily shown that the set of points lying on the coordinate axes form a blocking set of size 
 
 
 
 1
 +
 n
 (
 q
 −
 1
 )
 
 
 {\displaystyle 1+n(q-1)}
 
. Jean Doyen conjectured in a 1976 <a href="/facts/Oberwolfach/VoqpUbE8">Oberwolfach</a> conference that this is the least possible size of a blocking set. 
This was proved by R. E. Jamison in 1977,<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> and independently by <a href="/facts/Andries_Brouwer/zdSqHqHR">A. E. Brouwer</a>, <a href="/facts/Alexander_Schrijver/eJHJNRGz">A. Schrijver</a> in 1978 <a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> 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 
 
 
 
 V
 
 
 {\displaystyle V}
 
 be an 
 
 
 
 n
 
 
 {\displaystyle n}
 
 dimensional vector space over 
 
 
 
 
 
 F
 
 
 q
 
 
 
 
 {\displaystyle \mathbb {F} _{q}}
 
. Then the number of 
 
 
 
 k
 
 
 {\displaystyle k}
 
-dimensional cosets required to cover all vectors except the zero vector is at least 
 
 
 
 
 q
 
 n
 −
 k
 
 
 −
 1
 +
 k
 (
 q
 −
 1
 )
 
 
 {\displaystyle q^{n-k}-1+k(q-1)}
 
. Moreover, this bound is sharp.

<h2 id="notes">Notes</h2>

<ul><li>Barwick, Susan; Ebert, Gary (2008), Unitals in Projective Planes, New York: Springer, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-0-387-76366-8">10.1007/978-0-387-76366-8</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-76364-4, <a href="/facts/ISSN_(identifier)/DPAflDvU">ISSN</a> <a href="https://search.worldcat.org/issn/1439-7382">1439-7382</a></li>
<li><a href="/facts/Claude_Berge/VPsApqnu">C. Berge</a>, Graphs and hypergraphs, North-Holland, Amsterdam, 1973. (Defines 
 
 
 
 τ
 (
 H
 )
 
 
 {\displaystyle \tau (H)}
 
.)</li>
<li>P. Duchet, Hypergraphs, Chapter 7 in: Handbook of Combinatorics, North-Holland, Amsterdam, 1995.</li>
<li><a href="/facts/J._W._P._Hirschfeld/4dUVRX3W">Hirschfeld, J.W.P.</a> (1979), <a href="https://archive.org/details/projectivegeomet0000hirs">Projective Geometries over Finite Fields</a>, Oxford: Oxford University Press, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-19-853526-3</li>
<li>Holder, Leanne D. (2001), Blocking Sets of Conics, Ph.D. thesis, University of Colorado Denver</li>
<li>De Beule, Jan; Storme, Leo (2011), <a href="https://web.archive.org/web/20160129010102/https://www.novapublishers.com/catalog/product_info.php?products_id=21439">Current Research Topics in Galois Geometry</a>, Nova Science Publishers, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-1-61209-523-3, archived from <a href="https://www.novapublishers.com/catalog/product_info.php?products_id=21439">the original</a> on 2016-01-29, retrieved 2016-01-23</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hirschfeld 1979, p. 366 - Hirschfeld, J.W.P. (1979), Projective Geometries over Finite Fields, Oxford: Oxford University Press, ISBN 978-0-19-853526-3 <a href="https://archive.org/details/projectivegeomet0000hirs" target="_blank">https://archive.org/details/projectivegeomet0000hirs</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hirschfeld 1979, p. 376, Theorem 13.4.1 - Hirschfeld, J.W.P. (1979), Projective Geometries over Finite Fields, Oxford: Oxford University Press, ISBN 978-0-19-853526-3 <a href="https://archive.org/details/projectivegeomet0000hirs" target="_blank">https://archive.org/details/projectivegeomet0000hirs</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Hirschfeld 1979, p. 377, Theorem 13.4.2 - Hirschfeld, J.W.P. (1979), Projective Geometries over Finite Fields, Oxford: Oxford University Press, ISBN 978-0-19-853526-3 <a href="https://archive.org/details/projectivegeomet0000hirs" target="_blank">https://archive.org/details/projectivegeomet0000hirs</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Blokhuis, Aart (1994), "On the size of a blocking set in PG(2,p)", Combinatorica, 14: 111–114, doi:10.1007/bf01305953 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Hirschfeld 1979, p. 376, Theorem 13.3.3 - Hirschfeld, J.W.P. (1979), Projective Geometries over Finite Fields, Oxford: Oxford University Press, ISBN 978-0-19-853526-3 <a href="https://archive.org/details/projectivegeomet0000hirs" target="_blank">https://archive.org/details/projectivegeomet0000hirs</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Barwick & Ebert 2008, p. 30, Theorem 2.15 - Barwick, Susan; Ebert, Gary (2008), Unitals in Projective Planes, New York: Springer, doi:10.1007/978-0-387-76366-8, ISBN 978-0-387-76364-4, ISSN 1439-7382 <a href="https://doi.org/10.1007%2F978-0-387-76366-8" target="_blank">https://doi.org/10.1007%2F978-0-387-76366-8</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Barwick & Ebert 2008, p. 30, Theorem 2.16 - Barwick, Susan; Ebert, Gary (2008), Unitals in Projective Planes, New York: Springer, doi:10.1007/978-0-387-76366-8, ISBN 978-0-387-76364-4, ISSN 1439-7382 <a href="https://doi.org/10.1007%2F978-0-387-76366-8" target="_blank">https://doi.org/10.1007%2F978-0-387-76366-8</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Blokhuis, Aart (1994), "On the size of a blocking set in PG(2,p)", Combinatorica, 14: 111–114, doi:10.1007/bf01305953 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Holder 2001, p. 45 - Holder, Leanne D. (2001), Blocking Sets of Conics, Ph.D. thesis, University of Colorado Denver <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Richardson, Moses (1956), "On Finite Projective Games", Proceedings of the American Mathematical Society, 7 (3): 458–465, doi:10.2307/2032754, JSTOR 2032754 <a href="/wiki/Proceedings_of_the_American_Mathematical_Society" target="_blank">/wiki/Proceedings_of_the_American_Mathematical_Society</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Isbell, J.R. (1958), "A Class of Simple Games", Duke Mathematical Journal, 25 (3): 425–436, doi:10.1215/s0012-7094-58-02537-7 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">DiPaola, Jane W. (1969), "On Minimum Blocking Coalitions in Small Projective Plane Games", SIAM Journal on Applied Mathematics, 17 (2): 378–392, doi:10.1137/0117036 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Hirschfeld 1979, p. 366, Theorem 13.1.2 - Hirschfeld, J.W.P. (1979), Projective Geometries over Finite Fields, Oxford: Oxford University Press, ISBN 978-0-19-853526-3 <a href="https://archive.org/details/projectivegeomet0000hirs" target="_blank">https://archive.org/details/projectivegeomet0000hirs</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Szőnyi, Tamás (1997), "Blocking Sets in Desarguesian Affine and Projective Planes", Finite Fields and Their Applications, 3 (3): 187–202, doi:10.1006/ffta.1996.0176 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Szőnyi, Tamás (1999), "Around Rédei's theorem", Discrete Mathematics, 208/209: 557–575, doi:10.1016/s0012-365x(99)00097-7 <a href="/wiki/Discrete_Mathematics_(journal)" target="_blank">/wiki/Discrete_Mathematics_(journal)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Jamison, Robert E. (1977), "Covering finite fields with cosets of subspaces", Journal of Combinatorial Theory, Series A, 22 (3): 253–266, doi:10.1016/0097-3165(77)90001-2 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Brouwer, Andries; Schrijver, Alexander (1978), "The blocking number of an affine space", Journal of Combinatorial Theory, Series A, 24 (2): 251–253, doi:10.1016/0097-3165(78)90013-4 <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
</ol>

Blocking set open-in-new

Blocking set