Maximal partial ovoids and maximal partial spreads in hermitian generalized quadrangles

Maximal partial ovoids and maximal partial spreads of the hermitian generalized quadrangles H(3,q²) and H(4,q²) are studied in great detail. We present improved lower bounds on the size of maximal partial ovoids and maximal partial spreads in the hermitian quadrangle H(4,q²). We also construct in H(3,q²), q=2^2h+1, h≥ 1, maximal partial spreads of size smaller than the size q²+1 presently known. As a final result, we present a discrete spectrum result for the deficiencies of maximal partial spreads of H(4,q²) of small positive deficiency δ. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 101–116, 2008     

Partial Ovoids in Classical Finite Polar Spaces

Ovoids in finite polar spaces are related to many other objects in finite geometries. In this article, we prove some new upper bounds for the size of partial ovoids in Q ^–(2n+1,q) and W(2n+ 1,q). Further, we give a combinatorial proof for the non-existence of ovoids of H(2n +1,q ²) for n>q ³.     

On Maximal Partial Spreads in PG(n, q)

In this paper we construct maximal partial spreads in PG(3, q) which are a log q factor larger than the best known lower bound. For n ≥ 5 we also construct maximal partial spreads in PG(n, q) of each size between cnq ^{n ? 2} log q and c′ q ^{n ? 1}.     

A new upper bound for constant distance codes of generators on hermitian polar spaces of type H(2d − 1, q 2)

We provide new bounds for the maximum size of a set of generators of H(2d ? 1, q ²) which pairwise intersect in codimension i by applying a multiplicity bound by C. D. Godsil. This implies a new bound on the maximum size of partial spreads of H(2d ? 1, q ²), d even.     

A characterization of two classes of strongly regular graphs

The half dual polar graphsD _4,4(q) and the alternating forms graphsAlt(4,q) are characterized among strongly regular graphs with classical parameters via the geometric structures of polar spaces and affine polar spaces of rank 4, respectively.     

Antidesigns and regularity of partial spreads in dual polar graphs

We give several examples of designs and antidesigns in classical finite polar spaces. These types of subsets of maximal totally isotropic subspaces generalize the dualization of the concepts of m ‐ovoids and tight sets of points in generalized quadrangles. We also consider regularity of partial spreads and spreads. The techniques that we apply were developed by Delsarte. In some polar spaces of small rank, some of these subsets turn out to be completely regular codes. © 2010 Wiley Periodicals, Inc. J Combin Designs 19: 202‐216, 2011     

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.      

Blocking sets and semifields

We find a relationship between semifield spreads of PG(3,q), small Rédei minimal blocking sets of PG(2,q²), disjoint from a Baer subline of a Rédei line, and translation ovoids of the hermitian surface H(3,q²).     

Generalized Hardy spaces

Hardy spaces with generalized parameter are introduced following the maximal characterization approach. As particular cases, they include the classical Hp spaces and the Hardy-Lorentz spaces H^p,q. Real interpolation results with function parameter are obtained, Based on them, the behavior of some classical operators is studied in this generalized setting.     

On Small and Large Hyperplanes of DW(5, q)

We determine lower and upper bounds for the size of a hyperplane of the dual polar space DW(5, q). In some cases, we also determine all hyperplanes attaining these bounds.     

A Tight Analysis of the Greedy Algorithm for Set Cover

We establish significantly improved bounds on the performance of the greedy algorithm for approximatingset cover. In particular, we provide the first substantial improvement of the 20-year-old classical harmonic upper bound,H(m), of Johnson, Lovász, and Chvátal, by showing that the performance ratio of the greedy algorithm is, in fact,exactlyln m − ln ln m + Θ(1), wheremis the size of the ground set. The difference between the upper and lower bounds turns out to be less than 1.1. This provides the first tight analysis of the greedy algorithm, as well as the first upper bound that lies belowH(m) by a function going to infinity withm. We also show that the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on theintegrality gap. Our improvements result from a new approach which might be generally useful for attacking other similar problems.     

Theorems of Erd?s-Ko-Rado type in polar spaces

We consider Erd?s-Ko-Rado sets of generators in classical finite polar spaces. These are sets of generators that all intersect non-trivially. We characterize the Erd?s-Ko-Rado sets of generators of maximum size in all polar spaces, except for H(4n+1,q²) with n?2.     

New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming

We give a new upper bound on the maximum size Aq(n,d) of a code of word length n and minimum Hamming distance at least d over the alphabet of q?3 letters. By block-diagonalizing the Terwilliger algebra of the nonbinary Hamming scheme, the bound can be calculated in time polynomial in n using semidefinite programming. For q=3,4,5 this gives several improved upper bounds for concrete values of n and d. This work builds upon previous results of Schrijver [A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory 51 (2005) 2859-2866] on the Terwilliger algebra of the binary Hamming scheme.     

Tight sets,weighted <Emphasis Type="Italic">m</Emphasis>-covers,weighted <Emphasis Type="Italic">m</Emphasis>-ovoids,and minihypers

Minihypers are substructures of projective spaces introduced to study linear codes meeting the Griesmer bound. Recently, many results in finite geometry were obtained by applying characterization results on minihypers (De Beule et al. 16:342–349, 2008; Govaerts and Storme 4:279–286, 2004; Govaerts et al. 28:659–672, 2002). In this paper, using characterization results on certain minihypers, we present new results on tight sets in classical finite polar spaces and weighted m-covers, and on weighted m-ovoids of classical finite generalized quadrangles. The link with minihypers gives us characterization results of i-tight sets in terms of generators and Baer subgeometries contained in the Hermitian and symplectic polar spaces, and in terms of generators for the quadratic polar spaces. We also present extendability results on partial weighted m-ovoids and partial weighted m-covers, having small deficiency, to weighted m-covers and weighted m-ovoids of classical finite generalized quadrangles. As a particular application, we prove in an alternative way the extendability of 53-, 54-, and 55-caps of PG(5,3), contained in a non-singular elliptic quadric Q⁻(5,3), to 56-caps contained in this elliptic quadric Q⁻(5,3).      

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.     

On the Spectrum of the Sizes of Maximal Partial Line Spreads in <Emphasis Type="Italic">PG</Emphasis>(2<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">q</Emphasis>), <Emphasis Type="Italic">n</Emphasis> ≥ 3

A lot of research has been done on the spectrum of the sizes of maximal partial spreads in PG(3,q) [P. Govaerts and L. Storme, Designs Codes and Cryptography, Vol. 28 (2003) pp. 51–63; O. Heden, Discrete Mathematics, Vol. 120 (1993) pp. 75–91; O. Heden, Discrete Mathematics, Vol. 142 (1995) pp. 97–106; O. Heden, Discrete Mathematics, Vol. 243 (2002) pp. 135–150]. In [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129], results on the spectrum of the sizes of maximal partial line spreads in PG(N,q), N 5, are given. In PG(2n,q), n 3, the largest possible size for a partial line spread is q^2n-1+q^2n-3+...+q³+1. The largest size for the maximal partial line spreads constructed in [A. Gács and T. Sznyi, Designs Codes and Cryptography, Vol. 29 (2003) pp. 123–129] is (q²ⁿ⁺¹–q)/(q²–1)–q³+q²–2q+2. This shows that there is a non-empty interval of values of k for which it is still not known whether there exists a maximal partial line spread of size k in PG(2n,q). We now show that there indeed exists a maximal partial line spread of size k for every value of k in that interval when q 9.J. Eisfeld: Supported by the FWO Research Network WO.011.96NP. Sziklai: The research of this author was partially supported by OTKA D32817, F030737, F043772, FKFP 0063/2001 and Magyary Zoltan grants. The third author is grateful for the hospitality of Ghent University.     

Tight sets and m-ovoids of finite polar spaces

An intriguing set of points of a generalised quadrangle was introduced in [J. Bamberg, M. Law, T. Penttila, Tight sets and m-ovoids of generalised quadrangles, Combinatorica, in press] as a unification of the pre-existing notions of tight set and m-ovoid. It was shown in [J. Bamberg, M. Law, T. Penttila, Tight sets and m-ovoids of generalised quadrangles, Combinatorica, in press] that every intriguing set of points in a finite generalised quadrangle is a tight set or an m-ovoid (for some m). Moreover, it was shown that an m-ovoid and an i-tight set of a common generalised quadrangle intersect in mi points. These results yielded new proofs of old results, and in this paper, we study the natural analogue of intriguing sets in finite polar spaces of higher rank. In particular, we use the techniques developed in this paper to give an alternative proof of a result of Thas [J.A. Thas, Ovoids and spreads of finite classical polar spaces, Geom. Dedicata 10 (1-4) (1981) 135-143] that there are no ovoids of H(2r,q²), Q⁻(2r+1,q), and W(2r−1,q) for r>2. We also strengthen a result of Drudge on the non-existence of tight sets in W(2r−1,q), H(2r+1,q²), and Q⁺(2r+1,q), and we give a new proof of a result of De Winter, Luyckx, and Thas [S. De Winter, J.A. Thas, SPG-reguli satisfying the polar property and a new semipartial geometry, Des. Codes Cryptogr. 32 (1-3) (2004) 153-166; D. Luyckx, m-Systems of finite classical polar spaces, PhD thesis, The University of Ghent, 2002] that an m-system of W(4m+3,q) or Q⁻(4m+3,q) is a pseudo-ovoid of the ambient projective space.     

Existence of (q,k, 1) difference families with q a prime power and k = 4, 5

The existence of a (q, k, 1) difference family in GF(q) has been completely solved for k = 3. For k = 4, 5 partial results have been given by Bose, Wilson, and Buratti. In this article, we continue the investigation and show that the necessary condition for the existence of a (q, k, 1) difference family in GF(q), i.e., q ≡ 1 (mod k(k − 1)) is also sufficient for k = 4, 5. For general k, Wilson's bound shows that a (q, k, 1) difference family in GF(q) exists whenever q ≡ 1 (mod k(k − 1)) and q > [k(k − 1)/2]^k(k−1). An improved bound on q is also presented. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 21–30, 1999     

On the Schur multipliers of finite p-groups of given coclass

In this paper we obtain bounds for the order and exponent of the Schur multiplier of a p-group of given coclass. These are further improved for p-groups of maximal class. In particular, we prove that if G is p-group of maximal class, then |H ₂(G, ℤ)| < |G| and expH ₂(G, ℤ) ≤ expG. The bound for the order can be improved asymptotically.     

Desarguesian partial parallelisms

This article establishes connections between Desarguesian partial parallelisms of deficiency one in PG(3,q) and translation planes of orderq ⁴ admitting a collineation group isomorphic to SL(2,q) which is generated by Baer collineations.The author is grateful to Professor Alan Prince for helpful conversations with respect to this article and, in particular, with respect to the actual bounds for certain maximal partial spreads.The author is grateful to the referee for helpful comments in the writing of this article.