Ovoids of Parabolic Spaces

A new ovoid in the orthogonal space O(5,3⁵) is presented, along with its associated spreads and (semifield) translation planes. Sundry results on ovoids and spreads are given. In particular, we complete the calculation of the stabilisers of the known O(5,q) ovoids.     

Local Schur’s Lemma and Commutative Semifields

A set of linear maps , V a finite vector space over a field K, is regular if to each there corresponds a unique element such that R(x)=y. In this context, Schur’s lemma implies that is a field if (and only if) it consists of pairwise commuting elements. We consider when is locally commutative: at some μ ∈V*, AB(μ)=BA(μ) for all , and has been normalized to contain the identity. We show that such locally commutative are equivalent to commutative semifields, generalizing a result of Ganley, and hence characterizing commutative semifield spreads within the class of translation planes. This enables the determination of the orders |V| for which all locally commutative on V are (globally) commutative. Similarly, we determine a sharp upperbound for the maximum size of the Schur kernel associated with strictly locally commutative . We apply our main result to demonstrate the existence of a partial spread of degree 5, with nominated shears axis, that cannot be extend to a commutative semifield spread. Finally, we note that although local commutativity for a regular linear set implies that the set of Lie products consists entirely of singular maps, the converse is false.     

Polarity and transitive parabolic unitals in translation planes of odd order

A parabolic unital of a translation plane is called transitive, if the collineation group G fixing fixes the point at infinity of and acts transitively on the affine points of . It has been conjectured that if a transitive parabolic unital consists of the absolute points of a unitary polarity in a commutative semi-field plane, then the sharply transitive normal subgroupK of G is not commutative. So far, this has been proved for commutative twisted field planes of odd square order, see [1],[5]. Here we prove this conjecture for commutative Dickson planes. Received 14 May 2001.     

{0, 1/2}-Chvátal-Gomory cuts

Given the integer polyhedronP _t := conv{x ∈ℤ ⁿ :Ax⩽b}, whereA ∈ℤ ^{m × n} andb ∈ℤ ^m , aChvátal-Gomory (CG)cut is a valid inequality forP ₁ of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ ₊ ^m such that λτA∈ℤ ⁿ . In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2} ^m . We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of strong inequalities forP ₁. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.     

A translation plane of order 192 admitting SL(2,5), obtained by 12-nest replacement

The problem of determining two-dimensional translation planes admitting SL(2,5) in the translation complement has been intensively studied. Most examples arise from multiple-derivation of a Desarguesian plane. In this paper, we construct two translation planes of order 19² admitting SL(2,5), one of which is obtained by 12-nest replacement.      

Collineation groups of translation planes admitting hyperbolic Buekenhout or parabolic Buekenhout-Metz unitals

It is shown that for every semifield spread in PG(3,q) and for every parabolic Buekenhout-Metz unital, there is a collineation group of the associated translation plane that acts transitively and regularly on the affine points of the parabolic unital. Conversely, any spread admitting such a group is shown to be a semifield spread. For hyperbolic Buekenhout unitals, various collineation groups of translation planes admitting such unitals and the associated planes are determined.     

Simplectic spreads and finite semifields

It is well known that associated with a translation plane π there is a family of equivalent spreads. In this paper, we prove that if one of these spreads is symplectic and π is finite, then all the associated spreads are symplectic. Also, using the geometric intepretation of the Knuth’s cubical array, we prove that a symplectic semifield spread of dimension n over its left nucleus is associated via a Knuth operation to a commutative semifield of dimension n over its middle nucleus.      

On the complexity of matrix reduction over finite fields

In this paper we study the complexity of matrix elimination over finite fields in terms of row operations, or equivalently in terms of the distance in the Cayley graph of generated by the elementary matrices. We present an algorithm called striped matrix elimination which is asymptotically faster than traditional Gauss–Jordan elimination. The new algorithm achieves a complexity of row operations, and operations in total, thanks to being able to eliminate many matrix positions with a single row operation. We also bound the average and worst-case complexity for the problem, proving that our algorithm is close to being optimal, and show related concentration results for random matrices. Next we present the results of a large computational study of the complexities for small matrices and fields. Here we determine the exact distribution of the complexity for matrices from , with n and q small. Finally we consider an extension from finite fields to finite semifields of the matrix reduction problem. We give a conjecture on the behaviour of a natural analogue of GL_n for semifields and prove this for a certain class of semifields.     

On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.     

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²).     

Multiplicative Loops of 2-Dimensional Topological Quasifields

We determine the algebraic structure of the multiplicative loops for locally compact 2-dimensional topological connected quasifields. In particular, our attention turns to multiplicative loops which have either a normal subloop of positive dimension or which contain a 1-dimensional compact subgroup. In the last section, we determine explicitly the quasifields which coordinatize locally compact translation planes of dimension 4 admitting an at least 7-dimensional Lie group as collineation group.     

Lower bounds for coverings of pairs by large blocks

Letnkt be positive integers, andX—a set ofn elements. LetC(n, k, t) be the smallest integerm such that there existm k-tuples ofX B ₁ B ₂,...,B _m with the property that everyt-tuple ofX is contained in at least oneB _i . It is shown that in many cases the standard lower bound forC(n, k, 2) can be improved (k sufficiently large,n/k being fixed). Some exact values ofC(n, k, 2) are also obtained.     

A Characterization of Quaternion Planes, Revisited

It is shown that the group PSL₂(H) cannot act effectively on any eight-dimensional stable plane. Together with previous results, this entails that every eight-dimensional stable plane admitting a nontrivial action of SL₂(H) embeds into the projective plane over Hamilton's quaternions H.     

Ternary Operations as Primitive Notions for Constructive Plane Geometry V

In this paper we provide a quantifier-free, constructive axiomatization of metric-Euclidean and of rectangular planes (generalizations of Euclidean planes). The languages in which the axiom systems are expressed contain three individual constants and two ternary operations. We also provide an axiom system in algorithmic logic for finite Euclidean planes, and for several minimal metric-Euclidean planes. The axiom systems proposed will be used in a sequel to this paper to provide ‘the simplest possible’ axiom systems for several fragments of plane Euclidean geometry. Mathematics Subject Classification: 51M05, 51M15, 03F65.