Equipartite gregarious 6- and 8-cycle systems

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite gregarious 3-cycle systems are 3-GDDs, and necessary and sufficient conditions for their existence are known (see for instance the CRC Handbook of Combinatorial Designs, 1996, C.J. Colbourn, J.H. Dinitz (Eds.), Section III 1.3). The cases of equipartite and of almost equipartite 4-cycle systems were recently dealt with by Billington and Hoffman. Here, for both 6-cycles and for 8-cycles, we give necessary and sufficient conditions for existence of a gregarious cycle decomposition of the complete equipartite graph K_n(a) (with n parts, n?6 or n?8, of size a).     

Nets and their codes

A finitek-net of ordern is an incidence structure ofnk lines andn ² points, with any two lines either meeting once or being parallel, havingk parallel classes ofn lines each, and havingn points on each line. Finite nets are important to the study of finite planes and Latin squares.In this paper finite nets will be studied using the following linear codes: the row space of the incidence vectors of lines, the intersection of this code with its orthogonal, the code generated by differences of parallel lines, and the orthogonal to these codes. Using these codes we are able to recast the Moorhouse conjecture in terms of subcodes of the codes he uses, determine coding-theoretic reasons for a net's being maximal, and generalize a theorem of Assmus and Key which uses codes to classify finite planes of prime order.     

The non-existence of certain finite linear spaces

We study the existence of finite linear spaces with v points and n ²+n+2 lines, where n ²+1?v?n ²+n+1. For n?3, there is only one such linear space; it has ten points and fourteen lines.     

On the degree of points and lines in a restricted linear space

In this paper we show that, with the exception of a few easily characterized linear spaces, all restricted linear spaces of square order n have the maximal degree of the lines equal to n + 1, the degree of every point at least n + 1, and further we show that p ? n² + n + 1 ? q, where p is the number of points and q the number of lines.     

Maximum distance separable codes and arcs in projective spaces

Given any linear code C over a finite field GF(q) we show how C can be described in a transparent and geometrical way by using the associated Bruen-Silverman code.Then, specializing to the case of MDS codes we use our new approach to offer improvements to the main results currently available concerning MDS extensions of linear MDS codes. We also sharply limit the possibilities for constructing long non-linear MDS codes. Our proofs make use of the connection between the work of Rédei [L. Rédei, Lacunary Polynomials over Finite Fields, North-Holland, Amsterdam, 1973. Translated from the German by I. Földes. [18]] and the Rédei blocking sets that was first pointed out over thirty years ago in [A.A. Bruen, B. Levinger, A theorem on permutations of a finite field, Canad. J. Math. 25 (1973) 1060-1065]. The main results of this paper significantly strengthen those in [A. Blokhuis, A.A. Bruen, J.A. Thas, Arcs in PG(n,q), MDS-codes and three fundamental problems of B. Segre—Some extensions, Geom. Dedicata 35 (1-3) (1990) 1-11; A.A. Bruen, J.A. Thas, A.Blokhuis, On M.D.S. codes, arcs in PG(n,q) with q even, and a solution of three fundamental problems of B. Segre, Invent. Math. 92 (3) (1988) 441-459].     

Bounds on the number of autotopisms and subsquares of a Latin square

A subsquare of a Latin square L is a submatrix that is also a Latin square. An autotopism of L is a triplet of permutations (α, β, γ) such that L is unchanged after the rows are permuted by α, the columns are permuted by β and the symbols are permuted by γ. Let n!(n?1)!R _n be the number of n×n Latin squares. We show that an n×n Latin square has at most n ^{O(log k)} subsquares of order k and admits at most n ^{O(log n)} autotopisms. This enables us to show that {ie11-1} divides R _n for all primes p. We also extend a theorem by McKay and Wanless that gave a factorial divisor of R _n , and give a new proof that R _p ≠1 (mod p) for prime p.     

Latin squares and superqueens

Let L be a Latin square of order n with entries from {0, 1,…, n ? 1}. In addition, L is said to have the (n, k) property if, in each right or left wrap around diagonal, the number of cells with entries smaller than k is exactly k. It is established that a necessary and sufficient condition for the existence of Latin squares having the (n, k) property is that of (2|n ? 2| k) and (3|n ? 3| k). Also, these Latin squares are related to a problem of placing nonattacking queens on a toroidal chessboard.     

Symmetric Gobos in a finite projective plane

A gobo G in any incidence structure K is a (perhaps degenerate) tactical configuration having the property that no three points in G are collinear and no three lines in G are concurrent. General results are obtained where K is a finite projective plane of order n and G has k points and k lines such that each point (line) lies on r lines (points) of G. Particular attention is called to the contrast between the case r = 1 and the case r ≠ 1 when k = n.     

Planar and affine spaces

In this note, we characterize finite three-dimensional affine spaces as the only linear spaces endowed with set Ω of proper subspaces having the properties (1) every line contains a constant number of points, say n, with n>2; (2) every triple of noncollinear points is contained in a unique member of Ω; (3) disjoint or coincide is an equivalence relation in Ω with the additional property that every equivalence class covers all points. We also take a look at the case n=2 (in which case we have a complete graph endowed with a set Ω of proper complete subgraphs) and classify these objects: besides the affine 3-space of order 2, two small additional examples turn up. Furthermore, we generalize our result in the case of dimension greater than three to obtain a characterization of all finite affine spaces of dimension at least 3 with lines of size at least 3.     

On the number of k-subsets of a set of n points in the plane

For a configuration S of n points in $\text{E}$², H. Edelsbrunner (personal communication) has asked for bounds on the maximum number of subsets of size k cut off by a line. By generalizing to a combinatorial problem, we show that for 2k < n the number of such sets of size at most k is at most 2nk ? 2k² ? k. By duality, the same bound applies to the number of cells at distance at most k from a base cell in the cell complex determined by an arrangement of n lines in $\text{P}$².     

Multidimensional Latin bitrades

A subset of the n-dimensional k-valued hypercube is a unitrade or united bitrade whenever the size of its intersections with the one-dimensional faces of the hypercube takes only the values 0 and 2. A unitrade is bipartite or Hamiltonian whenever the corresponding subgraph of the hypercube is bipartite or Hamiltonian. The pair of parts of a bipartite unitrade is an n-dimensional Latin bitrade. For the n-dimensional ternary hypercube we determine the number of distinct unitrades and obtain an exponential lower bound on the number of inequivalent Latin bitrades. We list all possible n-dimensional Latin bitrades of size less than 2 ⁿ⁺¹. A subset of the n-dimensional k-valued hypercube is a t-fold MDS code whenever the size of its intersection with each one-dimensional face of the hypercube is exactly t. The symmetric difference of two single MDS codes is a bipartite unitrade. Each component of the corresponding Latin bitrade is a switching component of one of these MDS codes. We study the sizes of the components of MDS codes and the possibility of obtaining Latin bitrades of a size given from MDS codes. Furthermore, each MDS code is shown to embed in a Hamiltonian 2-fold MDS code.     

Latin parallelepipeds and cubes

For all n = 2^k, k ? 3, there are infinitely many Latin (n × n × (n ? 2))-parallelepipeds that cannot be embedded in any Latin cube of order n.     

Generalized Latin squares and their defining sets

A generalized Latin square of type (n,k) is an n×n array of symbols 1,2,…,k such that each of these symbols occurs at most once in each row and each column. Let d(n,k) denote the cardinality of the minimal set S of given entries of an n×n array such that there exists a unique extension of S to a generalized Latin square of type (n,k). In this paper we discuss the properties of d(n,k) for k=2n-1 and k=2n-2. We give an alternate proof of the identity d(n,2n-1)=n²-n, which holds for even n, and we establish the new result . We also show that the latter bound is tight for n divisible by 10.     

Latin squares with no small odd plexes

A k‐plex in a Latin square of order n is a selection of kn entries in which each row, column, and symbol is represented precisely k times. A transversal of a Latin square corresponds to the case k = 1. We show that for all even n > 2 there exists a Latin square of order n which has no k‐plex for any odd but does have a k‐plex for every other . © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 477–492, 2008     

Function spaces between BMO and critical Sobolev spaces

The function spaces Dk(Rn) are introduced and studied. The definition of these spaces is based on a regularity property for the critical Sobolev spaces Ws,p(Rn), where sp=n, obtained by J. Bourgain, H. Brezis, New estimates for the Laplacian, the div-curl, and related Hodge systems, C. R. Math. Acad. Sci. Paris 338 (7) (2004) 539-543 (see also J. Van Schaftingen, Estimates for L¹-vector fields, C. R. Math. Acad. Sci. Paris 339 (3) (2004) 181-186). The spaces Dk(Rn) contain all the critical Sobolev spaces. They are embedded in BMO(Rn), but not in VMO(Rn). Moreover, they have some extension and trace properties that BMO(Rn) does not have.     

Lines imply spaces in density Ramsey theory

Some results of geometric Ramsey theory assert that if F is a finite field (respectively, set) and n is sufficiently large, then in any coloring of the points of Fⁿ there is a monochromatic k-dimensional affine (respectively, combinatorial) subspace (see [9]). We prove that the density version of this result for lines (i.e., k = 1) implies the density version for arbitrary k. By using results in [3, 6] we obtain various consequences: a “group-theoretic” version of Roth's Theorem, a proof of the density assertion for arbitrary k in the finite field case when ∥F∥ = 3, and a proof of the density assertion for arbitrary k in the combinatorial case when ∥F∥ = 2.     

On a theorem of Erdös and Szekeres

In this note we generalize a theorem of Erdös and Szekeres, which states that every sequence of real numbers of length n² + 1 has a monotone subsequence of length n + 1, for points in certain metric spaces (R^k, d), where d is a Minkowski metric. Three theorems are proved concerning preassigned numbers of points which must lie on the same geodesic of the space, the last of which characterizes the class of Minkowski spaces under discussion.     

On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

Negative Latin square type partial difference sets and amorphic association schemes with Galois rings

A partial difference set (PDS) having parameters (n², r(n?1), n+r²?3r, r²?r) is called a Latin square type PDS, while a PDS having parameters (n², r(n+1), ?n+r²+3r, r² +r) is called a negative Latin square type PDS. There are relatively few known constructions of negative Latin square type PDSs, and nearly all of these are in elementary abelian groups. We show that there are three different groups of order 256 that have all possible negative Latin square type parameters. We then give generalized constructions of negative Latin square type PDSs in 2‐groups. We conclude by discussing how these results fit into the context of amorphic association schemes and by stating some open problems. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 266‐282, 2009     

Small point sets of PG(n, q 3) intersecting each k-subspace in 1 mod q points

The main result of this paper is that point sets of PG(n, q ³), q = p ^h , p ≥ 7 prime, of size less than 3(q ^3(n?k) + 1)/2 intersecting each k-space in 1 modulo q points (these are always small minimal blocking sets with respect to k-spaces) are linear blocking sets. As a consequence, we get that minimal blocking sets of PG(n, p ³), p ≥ 7 prime, of size less than 3(p ^3(n?k) + 1)/2 with respect to k-spaces are linear. We also give a classification of small linear blocking sets of PG(n, q ³) which meet every (n ? 2)-space in 1 modulo q points.