On the number of nowhere zero points in linear mappings

LetA be a nonsingularn byn matrix over the finite fieldGF _q ,k=n/2,q=p ^a ,a1, wherep is prime. LetP(A,q) denote the number of vectorsx in (GF _q ) ⁿ such that bothx andAx have no zero component. We prove that forn2, and ,P(A,q)[(q–1)(q–3)] ^k (q–2) ^n–2k and describe all matricesA for which the equality holds. We also prove that the result conjectured in [1], namely thatP(A,q)1, is true for allqn+23 orqn+14.     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

Variations on Tilings in the Manhattan Metric

We investigate tilings of the integer lattice in the Euclidean n-dimensional space. The tiles considered here are the union of spheres defined by the Manhattan metric. We give a necessary condition for the existence of such a tiling for Z ⁿ when n 2. We prove that this condition is sufficient when n=2. Finally, we give some tilings of Z ⁿ when n 3.     

Invariance Principles for Paced Record Times and Applications

Let {Y_n:n0} be a sequence of independent and identically distributed random variables with continuous distribution function, and let {N(t):t0} be a point process. In this paper, making use of strong invariance principles, we establish limit laws for the paced record process {X(t):t0} based on {Y_n:n0} and {N(t):t0}. We consider as applications of our main results, the case of the classical and paced record models. We conclude by extensions of our theorems to non-homogeneous record processes.     

Covering a Finite Abelian Group by Subset Sums

Let G be an abelian group of order n. The critical number c(G) of G is the smallest s such that the subset sums set (S) covers all G for eachs ubset SG\{0} of cardinality |S|s. It has been recently proved that, if p is the smallest prime dividing n and n/p is composite, then c(G)=|G|/p+p–2, thus establishing a conjecture of Diderrich.We characterize the critical sets with |S|=|G|/p+p–3 and (S)=G, where p3 is the smallest prime dividing n, n/p is composite and n7p²+3p.We also extend a result of Diderrichan d Mann by proving that, for n67, |S|n/3+2 and S=G imply (S)=G. Sets of cardinality for which (S) =G are also characterized when n183, the smallest prime p dividing n is odd and n/p is composite. Finally we obtain a necessary and sufficient condition for the equality (G)=G to hold when |S|n/(p+2)+p, where p5, n/p is composite and n15p².* Work partially supported by the Spanish Research Council under grant TIC2000-1017 Work partially supported by the Catalan Research Council under grant 2000SGR00079     

On the singular Bochner-Martinelli integral

The Bochner-Martinelli (B.-M.) kernel inherits, forn2, only some of properties of the Cauchy kernel in . For instance it is known that the singular B.-M. operatorM _n is not an involution forn2. M. Shapiro and N. Vasilevski found a formula forM ₂ ² using methods of quaternionic analysis which are essentially complex-twodimensional. The aim of this article is to present a formula forM _n ² for anyn2. We use now Clifford Analysis but forn=2 our formula coincides, of course, with the above-mentioned one.     

The Higher K-Theory of Real Curves

If X is a smooth curve defined over the real numbers , we show that K _n (X) is the sum of a divisible group and a finite elementary Abelian 2-group when n 2. We determine the torsion subgroup of K _n (X), which is a finite sum of copies of and 2, only depending on the topological invariants of X() and X(), and show that (for n 2) these torsion subgroups are periodic of order 8.     

Triangles in arrangements of lines

Givenn lines in the real projective plane, Grünbaum conjectures that, for n16, the numberp ₃ of triangular regions determined by the lines is at most 1/3n(n–1). We show that ifn7 thenp ₃ 8/21n(n–1)+2/7, we also point out that if no vertex is a point of intersection of exactly three of the lines, thenp ₃1/3n(n–1).Professor Gu died while on a visit to Poland in April 1997     

A finite characterization ofK-matrices in dimensions less than four

The class of realn × n matricesM, known asK-matrices, for which the linear complementarity problemw – Mz = q, w 0, z 0, w ^T z =0 has a solution wheneverw – Mz =q, w 0, z 0 has a solution is characterized for dimensionsn <4. The characterization is finite and practical. Several necessary conditions, sufficient conditions, and counterexamples pertaining toK-matrices are also given. A finite characterization of completelyK-matrices (K-matrices all of whose principal submatrices are alsoK-matrices) is proved for dimensions <4.Partially supported by NSF Grant MCS-8207217.Research partially supported by NSF Grant No. ECS-8401081.     

On blocking sets of quadrics

We determine the three smallest blocking sets with respect to lines of the quadric Q(2n, q) withn 3 and the two smallest blocking sets with respect to lines of the quadric Q⁺(2n+1,q) withn 2. These results will be used in a forthcoming paper for determining the smallest blocking sets with respect to higher dimensional subspaces in the quadrics Q(2n, q) and Q⁺(2n+ 1, q).     

On the Minimum Size of Some Minihypers and Related Linear Codes

We denote by m_r,q(s) the minimum value of f for which an {f, _r-2+s ; r,q }-minihyper exists for r 3, 1 s q–1, where _j=(q^j+1–1)/(q–1). It is proved that m_3,q(s)=₁(₁+s) for many cases (e.g., for all q 4 when ) and that m_r,q(s) _r-1+s₁+q for 1 s q – 1,~q 3,~r 4. The nonexistence of some [n,k,n+s–q^k-2]_q codes attaining the Griesmer bound is given as an application.AMS classification: 94B27, 94B05, 51E22, 51E21     

The number of different distances determined by a set of points in the Euclidean plane

In 1946 P. Erdös posed the problem of determining the minimum numberd(n) of different distances determined by a set ofn points in the Euclidean plane. Erdös provedd(n) cn ^1/2 and conjectured thatd(n)cn/ logn. If true, this inequality is best possible as is shown by the lattice points in the plane. We showd(n)n ^4/5/(logn) ^c .The research of W. T. Trotter was supported in part by the National Science Foundation under DMS 8713994 and DMS 89-02481.     

On a hypothesis on Poincaré series

Let F(x₁,..., x_m) (m1) be a polynomial with integral p-adic coefficients, and let N, be the number of solutions of the congruence F(x₁,..., X_m)=0 mod A proof is given that the Poincaré series (t) = ₀ N t is rational for a class of isometrically-equivalent polynomials of m variables (m2) containing a form of degree n2 of two variables.Translated from Matematicheskie Zametki, Vol. 14, No. 3, pp. 453–463, September, 1973.The author wishes to thank N. G. Chudakov for discussing this paper and for his helpful advice.     

Paths with restricted degrees of their vertices in planar graphs

In this paper it is proved that every 3-connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23. Analogous results are stated for 3-connected planar graphs of minimum degree 4 and 5. Moreover, for every pair of integers n 3, k 4 there is a 2-connected planar graph such that every path on n vertices in it has a vertex of degree k.     

Weak Laws with Random Indices for Arrays of Random Elements in Rademacher Type p Banach Spaces

For a sequence of constants {a _n,n1}, an array of rowwise independent and stochastically dominated random elements { V _nj, j1, n1} in a real separable Rademacher type p (1p2) Banach space, and a sequence of positive integer-valued random variables {T _n, n1}, a general weak law of large numbers of the form is established where {c _nj, j1, n1}, _n , b _n are suitable sequences. Some related results are also presented. No assumption is made concerning the existence of expected values or absolute moments of the {V _nj, j1, n1}. Illustrative examples include one wherein the strong law of large numbers fails.     

A Sequence of Unique Quaternary Griesmer Codes

This paper establishes that there is no [98,5,72]₄ code. Such a code would meet the Griesmer bound and the weights of its codewords would all be divisible by 4. The proof of nonexistence uses the uniqueness of codes with parameters [n,4,n - 5]₄,14 n 17. The uniqueness of these codes for n 15 had been established geometrically by others; but it is rederived here, along with that of the [14,4,9]₄ code, by exploiting the Hermitian form obtained when the weight function is read modulo 2.     

Covering a convex body by smaller homothetic copies

Let a convex bodyAE ⁿ be covered bys smaller homothetic copies with coefficients ₁, ..., _s , respectively. It is conjectured that ₁ + ...+ _s n. This conjecture is confirmed in two cases:n is arbitrary ands=n+1;s is arbitrary andn=2.     

2-designs overGF(2 m )

At – (n, k, ; q) design is a collection ofk-dimensional subspaces of ann-dimensional vector space overGF(q) with the property that anyt-dimensional subspace is contained in exactly members of . It is also called a design over a finite field or aq-analoguet-design. The first nontrivial example fort 2 was given by S. Thomas. Namely, he constructed a series of 2 – (n, 3, 7; 2) design for alln 7 satisfying (n, 6) = 1. Under the same restriction onn, we show that the base field of Thomas' design is extensible toGF(2 ^m ), i.e., we construct a 2 – (n, 3, 2^2m + 2 ^m + 1; 2 ^m ) design for allm 1.Dedicated to Professor Tuyosi Oyama on his 60th Birthday     

Rates of convergence for the stability of large order statistics

Forr1 and eachnr, letM _nr be therth largest ofX ₁,X ₂, ...,X _n , where {X _n ,n1} is an i.i.d. sequence. Necessary and sufficient conditions are presented for the convergence of for all >0 and some –1, where {a _n } is a real sequence. Furthermore, it is shown that this series converges for all >–1, allr1 and all >0 if it converges for some >–1, somer1 and all >0.     

Complete stability of large order statistics

Fix an integerr1. For eachnr, letM _nr be the rth largest ofX ₁,...,X _n, where {X _n,n1} is a sequence of i.i.d. random variables. Necessary and sufficient conditions are given for the convergence of _n=r n P[|M _nr /a _n –1|<] for every >0, where {a _n} is a real sequence and –1. Moreover, it is shown that if this series converges for somer1 and some >–1, then it converges for everyr1 and every >–1.