This article presents a spectrum result on minimal blocking sets with respect to the planes of PG(3,
q
),
q
odd. We prove that for every integer
k
in an interval of, roughly, size
q
2
/4, 3
q
2
/4, ...there exists such a minimal blocking set of size
k
in PG(3,
q
),
q
odd. A similar result on the spectrum of minimal blocking sets with respect to the planes of PG(3,
q
),
q
even, was presented in Rößing and Storme (Eur J Combin 31:349–361, 2010). Since minimal blocking sets with respect to the planes in PG(3,
q
) are tangency sets, they define maximal partial 1-systems on the Klein quadric
Q
+
(5,
q
), so we get the same spectrum result for maximal partial 1-systems of lines on the Klein quadric
Q
+
(5,
q
),
q
odd.
We prove that a non-trivial minimal blocking set with respect to hyperplanes in PG(r,2), r≥3, is a skeleton contained in some s-flat with odd s≥3. We also consider non-trivial minimal blocking sets ...with respect to lines and planes in PG(r,2), r≥3. Especially, we show that there are exactly two non-trivial minimal blocking sets with respect to lines and six non-trivial minimal blocking sets with respect to planes up to projective equivalence in PG(4,2). A characterization of an elliptic quadric in PG(5,2) as a special non-trivial minimal blocking set with respect to planes meeting every hyperplane in a non-trivial minimal blocking sets with respect to planes is also given.
A
blocking set
in a graph
G
is a subset of vertices that intersects every maximum independent set of
G
. Let
mmbs
(
G
)
be the size of a maximum (inclusion-wise) minimal blocking set of
G
. This ...parameter has recently played an important role in the kernelization of
Vertex Cover
with structural parameterizations. We provide a panorama of the complexity of computing
mmbs
parameterized by the natural parameter and the independence number of the input graph. We also consider the closely related parameter
mmhs
, which is the size of a maximum minimal hitting set of a hypergraph. Finally, we consider the problem of computing
mmbs
parameterized by treewidth, especially relevant in the context of kernelization. Since a blocking set intersects every
maximum-sized
independent set of a given graph and properties involving counting the sizes of arbitrarily large sets are typically non-expressible in monadic second-order logic, its tractability does not seem to follow from Courcelle’s theorem. Our main technical contribution is a fixed-parameter tractable algorithm for this problem.
In this paper, by using properties of Baer subplanes, we describe the construction of a minimal blocking set in the Hall plane of order $q^2$ of size $q^2+2q+2$ admitting $1-$, $2-$, $3-$, $4-$, ...$(q+1)-$ and $(q+2)-$secants. As a corollary, we obtain the existence of a minimal blocking set of a non-Desarguesian affine plane of order $q^2$ of size at most $4q^2/3+5q/3$, which is considerably smaller than $2q^2-1$, the Jamison bound for the size of a minimal blocking set in an affine Desarguesian plane of order $q^2$.We also consider particular André planes of order $q$, where $q$ is a power of the prime $p$, and give a construction of a small minimal blocking set which admits a secant line not meeting the blocking set in $1$ mod $p$ points. Furthermore, we elaborate on the connection of this problem with the study of value sets of certain polynomials and with the construction of small double blocking sets in Desarguesian projective planes; in both topics we provide some new results.
PDF
