Linear Point Sets and Rédei Type k-blocking Sets in PG(n, q)

In this paper, k-blocking sets in PG(n, q), being of Rédei type, are investigated. A standard method to construct Rédei type k-blocking sets in PG(n, q) is to construct a cone having as base a Rédei type k-blocking set in a subspace of PG(n, q). But also other Rédei type k-blocking sets in PG(n, q), which are not cones, exist. We give in this article a condition on the parameters of a Rédei type k-blocking set of PG(n, q = p ^h ), p a prime power, which guarantees that the Rédei type k-blocking set is a cone. This condition is sharp. We also show that small Rédei type k-blocking sets are linear.     

Cyclic caps in PG(3,q)

This article investigates cyclic completek-caps in PG(3,q). Namely, the different types of completek-capsK in PG(3,q) stabilized by a cyclic projective groupG of orderk, acting regularly on the points ofK, are determined. We show that in PG(3,q),q even, the elliptic quadric is the only cyclic completek-cap. Forq odd, it is shown that besides the elliptic quadric, there also exist cyclick-caps containingk/2 points of two disjoint elliptic quadrics or two disjoint hyperbolic quadrics and that there exist cyclick-caps stabilized by a transitive cyclic groupG fixing precisely one point and one plane of PG(3,q). Concrete examples of such caps, found using AXIOM and CAYLEY, are presented.     

Sharp homogeneity in some generalized polygons

We show that, if a collineation group G of a generalized (2n + 1)-gon $\Gamma$ has the property that every symmetry of any apartment extends uniquely to a collineation in G, then $\Gamma$ is the unique projective plane with 3 points per line (the Fano plane) and G is its full collineation group. A similar result holds if one substitutes apartment with path of length 2k 2n + 2.Received: 19 June 2002     

Self-dual sets of type (m, n) in projective spaces

In this paper we introduce and analyze the notion of self-dual k-sets of type (m, n). We show that in a non-square order projective space such sets exist only if the dimension is odd. We prove that, in a projective space of odd dimension and order q, self-dual k-sets of type (m, n), with , are of elliptic and hyperbolic type, respectively. As a corollary we obtain a new characterization of the non-singular elliptic and hyperbolic quadrics.     

On the code generated by the incidence matrix of points and k-spaces in and its dual

In this paper, we study the p-ary linear code C_k(n,q), q=p^h, p prime, h1, generated by the incidence matrix of points and k-dimensional spaces in PG(n,q). For kn/2, we link codewords of C_k(n,q)C_k(n,q) of weight smaller than 2q^k to k-blocking sets. We first prove that such a k-blocking set is uniquely reducible to a minimal k-blocking set, and exclude all codewords arising from small linear k-blocking sets. For k<n/2, we present counterexamples to lemmas valid for kn/2. Next, we study the dual code of C_k(n,q) and present a lower bound on the weight of the codewords, hence extending the results of Sachar [H. Sachar, The F_p span of the incidence matrix of a finite projective plane, Geom. Dedicata 8 (1979) 407–415] to general dimension.     

Note on the existence of large minimal blocking sets in galois planes

A subsetS of a finite projective plane of orderq is called a blocking set ifS meets every line but contains no line. For the size of an inclusion-minimal blocking setq+ +Sq +1 holds ([6]). Ifq is a square, then inPG(2,q) there are minimal blocking sets with cardinalityq +1. Ifq is not a square, then the various constructions known to the author yield minimal blocking sets with less than 3q points. In the present note we show that inPG(2,q),q1 (mod 4) there are minimal blocking sets having more thanqlog₂ q/2 points. The blocking sets constructed in this note contain the union ofk conics, whereklog₂ q/2. A slight modification of the construction works forq3 (mod 4) and gives the existence of minimal blocking sets of sizecqlog₂ q for some constantc.As a by-product we construct minimal blocking sets of cardinalityq +1, i.e. unitals, in Galois planes of square order. Since these unitals can be obtained as the union of parabolas, they are not classical.     

Complete caps in projective spaces PG (n, q)

A computer search in the finite projective spaces PG(n, q) for the spectrum of possible sizes k of complete k-caps is done. Randomized greedy algorithms are applied. New upper bounds on the smallest size of a complete cap are given for many values of n and q. Many new sizes of complete caps are obtained.     

New (k; r)-arcs in the projective plane of order thirteen

A (k;r)-arc $\cal K$ is a set of k points of a projective plane PG(2, q) such that some r, but no r +1 of them, are collinear. The maximum size of a (k; r)-arc in PG(2, q) is denoted by m _r (2, q). In this paper a (35; 4)-arc, seven (48; 5)-arcs, a (63; 6)-arc and two (117; 10)-arcs in PG(2, 13) are given. Some were found by means of computer search, whereas the example of a (63; 6)-arc was found by adding points to those of a sextic curve $\cal C$ that was not complete as a (54; 6)-arc. All these arcs are new and improve the lower bounds for m _r (2, 13) given in [10, Table 5.4]. The last section concerns the nonexistence of (40; 4)-arcs in PG(2, 13).     

Some families of complete caps of quadrics and symplectic polarities over GF(8)

A cap on a quadric is a set of its points whose pairwise joins are all chords. A cap is complete if it is not part of a larger one. The only field for which all complete quadric caps are known is GF(2). Those caps are small; the biggest for each quadric is of order the dimension of the ambient space. Apart from information about ovoids in dimensions at most 7, little else is known. Here, the evidence is increased by providing caps over GF(2), odd, which, if >1, have size of order the dimension cubed. In particular, complete caps are obtained for the quadrics Q _2m (8), Q ₊ ^8k+7 (8), Q _- ^8k+3 (8), Q ₊ ^8k+1 (8) and Q _- ^8k+5 (8). These caps on Q ₊ ^8k+7 (8) and Q _- ^8k+3 (8) are complete on any Q _n(8) of which their quadrics are sections; so is that that of Q ₄₊₂(8) for any Q _2n (8) of which Q ₄₊₂(8) is a section with the same kernel. From the correspondence with Q _2n (8) complete caps are obtained for symplectic polarities over GF(8).     

Extending MDS Codes

A q-ary (n, k)-MDS code, linear or not, satisfies n ≤ q + k − 1. A code meeting this bound is said to have maximum length. Using purely combinatorial methods we show that an MDS code with n = q + k − 2 can be uniquely extended to a maximum length code if and only if q is even. This result is best possible in the sense that there is, for example, a non-extendable 4-ary (5, 4)-MDS code. It may be that the proof of our result is as interesting as the result itself. We provide a simple necessary and sufficient condition for code extendability. In future work, this condition might be suitably modified to give an extendability condition for arbitrary (shorter) MDS codes.Received December 1, 2003     

Random constructions and density results

In this paper we outline a construction method which has been used for minimal blocking sets in PG(2, q) and maximal partial line spreads in PG(n, q) and which must have a lot of more applications. We also give a survey on what is known about the spectrum of sizes of maximal partial line spreads in PG(n, q). At the end we list some more elaborate random techniques used in finite geometry.      

Computer search in projective planes for the sizes of complete arcs

The spectrum of possible sizes k of complete k-arcs in finite projective planes PG(2, q) is investigated by computer search. Backtracking algorithms that try to construct complete arcs joining the orbits of some subgroup of collineation group PΓ L (3, q) and randomized greedy algorithms are applied. New upper bounds on the smallest size of a complete arc are given for q = 41, 43, 47, 49, 53, 59, 64, 71 ≤ q ≤ 809, q ≠ 529, 625, 729, and q = 821. New lower bounds on the second largest size of a complete arc are given for q = 31, 41, 43, 47, 53, 125. Also, many new sizes of complete arcs are obtained for 31 ≤ q ≤ 167.     

A geometric characterisation of linear k-blocking sets

In this paper we prove that any linear k-blocking set is either a canonical subgeometry or a projection of some canonical subgeometry. Received 6 February 2001.     

Some remarks on category of the real line

We find a characterization of the covering number , of the real line in terms of trees. We also show that the cofinality of is greater than or equal to for every where ( is the additivity number of the ideal of all Lebesgue measure zero sets) is the least cardinal number k for which the statement: fails. Received: 19 October 1994 / Revised version: 12 December 1996     

Classification of maximal caps in PG(3,5) different from elliptic quadrics

Ak-cap in PG(3,q) is a set of k points, no three of which are collinear. A k-cap is calledcomplete if it is not contained in a (k+1)-cap. The maximum valuem ₂(3, q) ofk for which there exists a k-cap in PG(3,q) is q²+1. Letm ₂(3, q) denote the size of the second largest complete k-cap in PG(3,q). This number is only known for the smallest values of q, namely for q=2, 3,4 (cf. [2], pp. 96–97 and [3], p. 303). In this paper we show thatm ₂(3,5)=20. We also prove that there are, up to isomorphism, only two complete 20-caps in PG(3,5) and determine their collineation groups.In memoriam Giuseppe TalliniWork done within the activity of GNSAGA of CNR and supported by MURST.     

Projektive Einbettung nicht lokal projektiver Räume

It is well known that every locally projective linear space (M,M) with dimM 3, fulfilling the Bundle Theorem (B) can be embedded in a projective space. We give here a new construction for the projective embedding of linear spaces which need not be locally projective. Essentially for this new construction are the assumptions (A) and (C) that for any two bundles there are two points on every line which are incident with a line of each of these bundles. With the Embedding Theorem (7.4) of this note for example a [0,m]-space can be embedded in a projective space.

     

Blockings-dimensional subspaces by lines inPG(2s,q)

We investigate sets of lines inPG(2s,q) such that everys-dimensional subspace contains a line of this set. We determine the minimum number of lines in such a set and show that there is only one type of such a set with this minimum number of lines.     

On proper secrets, (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-bases and linear codes

This paper contains three parts where each part triggered and motivated the subsequent one. In the first part (Proper Secrets) we study the Shamir’s “k-out-of-n” threshold secret sharing scheme. In that scheme, the dealer generates a random polynomial of degree k−1 whose free coefficient is the secret and the private shares are point values of that polynomial. We show that the secret may, equivalently, be chosen as any other point value of the polynomial (including the point at infinity), but, on the other hand, setting the secret to be any other linear combination of the polynomial coefficients may result in an imperfect scheme. In the second part ((t, k)-bases) we define, for every pair of integers t and k such that 1 ≤ t ≤ k−1, the concepts of (t, k)-spanning sets, (t, k)-independent sets and (t, k)-bases as generalizations of the usual concepts of spanning sets, independent sets and bases in a finite-dimensional vector space. We study the relations between those notions and derive upper and lower bounds for the size of such sets. In the third part (Linear Codes) we show the relations between those notions and linear codes. Our main notion of a (t, k)-base bridges between two well-known structures: (1, k)-bases are just projective geometries, while (k−1, k)-bases correspond to maximal MDS-codes. We show how the properties of (t, k)-independence and (t, k)-spanning relate to the notions of minimum distance and covering radius of linear codes and how our results regarding the size of such sets relate to known bounds in coding theory. We conclude by comparing between the notions that we introduce here and some well known objects from projective geometry.      

Small Universal Graphs for Bounded-Degree Planar Graphs

For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph. Received July 8, 1998 RID="*" ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

Sur les m-uples F-réguliers dans les espaces projectifs complexes

Résumé On étudie dans P ⁿ les m-uples de points, appelés F-réguliers, dont les sous-triplets ordonnés sont deux à deux isométriques. On montre qu'il existe au plus deux classes d'isométrie de quintuplets F-réguliers contenant un triangle équilatère T donné. On étudie aussi les m-uples F-réguliers, dont les sous k-uples (k<m) non ordonnés sont deux à deux isométriques. Ces m-uples sont appelés k-réguliers. On montre que la 4-régularité implique la k-régularité pour tous les k5.

---

We investigate in P ⁿ m-tuples of points in which all ordered triples are pairwise isometric. Such m-tuples are called F-regular. We show that for a given triangle T there exist at most two isometry classes of F-regular quintuples containing T. We also investigate F-regular m-tuples in which all (unordered) k-tuples (k<m) are pairwise isometric. Such m-tuples are called k-regular. We show that 4-regularity implies k-regularity for all k5.