Search

Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. In this paper we prove an upper bound on the minimal length of minimal codes of dimension $k$ over the $q$-element Galois field which is linear in both $q$ and $k$, hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well. The contributions rely on geometric and probabilistic arguments., Comment: Minor improvement for higgledy-piggledy line sets in the even order case. The main proof is slightly simplified. Some smaller mistakes are corrected

We investigate the upper chromatic number of the hypergraph formed by the points and the $k$-dimensional subspaces of $\mathrm{PG}(n,q)$; that is, the most number of colors that can be used to color the points so that every $k$-subspace contains at least two points of the same color. Clearly, if one colors the points of a double blocking set with the same color, the rest of the points may get mutually distinct colors. This gives a trivial lower bound, and we prove that it is sharp in many cases. Due to this relation with double blocking sets, we also prove that for $t\leq \frac38p+1$, a small $t$-fold (weighted) $(n-k)$-blocking set of $\mathrm{PG}(n,p)$, $p$ prime, must contain the weighted sum of $t$ not necessarily distinct $(n-k)$-spaces., Comment: 21 pages

The main purpose of this paper is to find double blocking sets in $\mathrm{PG}(2,q)$ of size less than $3q$, in particular when $q$ is prime. To this end, we study double blocking sets in $\mathrm{PG}(2,q)$ of size $3q-1$ admitting at least two $(q-1)$-secants. We derive some structural properties of these and show that they cannot have three $(q-1)$-secants. This yields that one cannot remove six points from a triangle, a double blocking set of size $3q$, and add five new points so that the resulting set is also a double blocking set. Furthermore, we give constructions of minimal double blocking sets of size $3q-1$ in $\mathrm{PG}(2,q)$ for $q=13$, $16$, $19$, $25$, $27$, $31$, $37$ and $43$. If $q>13$ is a prime, these are the first examples of double blocking sets of size less than $3q$. These results resolve two conjectures of Raymond Hill from 1984., Comment: 2 figures, revised version

In this paper the metric dimension of (the incidence graphs of) particular partial linear spaces is considered. We prove that the metric dimension of an affine plane of order $q\geq13$ is $3q-4$ and describe all resolving sets of that size if $q\geq 23$. The metric dimension of a biaffine plane (also called a flag-type elliptic semiplane) of order $q\geq 4$ is shown to fall between $2q-2$ and $3q-6$, while for Desarguesian biaffine planes the lower bound is improved to $8q/3-7$ under $q\geq 7$, and to $3q-9\sqrt{q}$ under certain stronger restrictions on $q$. We determine the metric dimension of generalized quadrangles of order $(s,1)$, $s$ arbitrary. We derive that the metric dimension of generalized quadrangles of order $(q,q)$, $q\geq2$, is at least $\max\{6q-27,4q-7\}$, while for the classical generalized quadrangles $W(q)$ and $Q(4,q)$ it is at most $8q$.

We describe small dominating sets of the incidence graphs of finite projective planes by establishing a stability result which shows that dominating sets are strongly related to blocking and covering sets. Our main result states that if a dominating set in a projective plane of order $q>81$ is smaller than $2q+2[\sqrt{q}]+2$ (i.e., twice the size of a Baer subplane), then it contains either all but possibly one points of a line or all but possibly one lines through a point. Furthermore, we completely characterize dominating sets of size at most $2q+\sqrt{q}+1$. In Desarguesian planes, we could rely on strong stability results on blocking sets to show that if a dominating set is sufficiently smaller than 3q, then it consists of the union of a blocking set and a covering set apart from a few points and lines., Comment: 19 pages

A $t$-semiarc is a pointset ${\cal S}_t$ with the property that the number of tangent lines to ${\cal S}_t$ at each of its points is $t$. We show that if a small $t$-semiarc ${\cal S}_t$ in $\mathrm{PG}(2,q)$ has a large collinear subset ${\cal K}$, then the tangents to ${\cal S}_t$ at the points of ${\cal K}$ can be blocked by $t$ points not in ${\cal K}$. We also show that small $t$-semiarcs are related to certain small blocking sets. Some characterization theorems for small semiarcs with large collinear subsets in $\mathrm{PG}(2,q)$ are given., Comment: 15 pages, revised version. Most importantly, we corrected the definition of b(q) in Theorem 4.7

We consider the following $q$-analog of the basic combinatorial search problem: let $q$ be a prime power and $\GF(q)$ the finite field of $q$ elements. Let $V$ denote an $n$-dimensional vector space over $\GF(q)$ and let $\mathbf{v}$ be an unknown 1-dimensional subspace of $V$. We will be interested in determining the minimum number of queries that is needed to find $\mathbf{v}$ provided all queries are subspaces of $V$ and the answer to a query $U$ is YES if $\mathbf{v} \leqslant U$ and NO if $\mathbf{v} \not\leqslant U$. This number will be denoted by $A(n,q)$ in the adaptive case (when for each queries answers are obtained immediately and later queries might depend on previous answers) and $M(n,q)$ in the non-adaptive case (when all queries must be made in advance). In the case $n=3$ we prove $2q-1=A(3,q)

We show that the metric dimension of a finite projective plane of order $q\geq 23$ is $4q-4$, and describe all resolving sets of that size. Let $\tau_2$ denote the size of the smallest double blocking set in $\mathrm{PG}(2,q)$, the Desarguesian projective plane of order $q$. We prove that for a semi-resolving set $S$ in the incidence graph of $\mathrm{PG}(2,q)$, $|S|\geq \min \{2q+q/4-3, \tau_2-2\}$ holds. In particular, if $q\geq9$ is a square, then the smallest semi-resolving set in $\mathrm{PG}(2,q)$ has size $2q+2\sqrt{q}$., Comment: 21 pages, 3 figures. Version 3 contains clarifications and minor corrections regarding the list and the figure of the 32 types of smallest resolving sets, and a supplementary page explaining these modifications