Monotone subsequences in (0, 1)-matrices

A (0, 1)-matrix contains anS ₀(k) if it has 0-cells (i, j ₁), (i + 1,j ₂),..., (i + k – 1,j _k) for somei andj ₁ < ... < j_k, and it contains anS ₁(k) if it has 1-cells (i ₁,j), (i ₂,j + 1),...,(i _k ,j + k – 1) for somej andi ₁ < ... <i _k . We prove that ifM is anm × n rectangular (0, 1)-matrix with 1 m n whose largestk for anS ₀(k) isk ₀ m, thenM must have anS ₁(k) withk m/(k ₀ + 1). Similarly, ifM is anm × m lower-triangular matrix whose largestk for anS ₀(k) (in the cells on or below the main diagonal) isk ₀ m, thenM has anS ₁(k) withk m/(k ₀ + 1). Moreover, these results are best-possible.     

Some inequalities about the covering radius of Reed-Muller codes

Let R(r, m) be the rth order Reed-Muller code of length 2 ^m , and let (r, m) be its covering radius. We prove that if 2 k m - r - 1, then (r + k, m + k) (r, m + 2(k - 1). We also prove that if m - r 4, 2 k m - r - 1, and R(r, m) has a coset with minimal weight (r, m) which does not contain any vector of weight (r, m) + 2, then (r + k, m + k) (r, m) + 2k(. These inequalities improve repeated use of the known result (r + 1, m + 1) (r, m).This work was supported by a grant from the Research Council of Wright State University.     

Tangential chow forms — rank 1 hypersurfaces in a Grassmannian

Let X ⁿ P ^N be an n-dimensional projective variety, and N–n–1kN–1. The closure in the Grassmannian G(k+1, N+1) of the set of k-planes meeting the smooth locus of X nontransversally is a tangential Chow form (TCF) of X.TCF's are generally hypersurfaces. We show that a hypersurface is a TCF iff its conormal form has rank 1, and that a TCF is a hypersurface iff some quadric in the second fundamental form of X has rank n+k+1–N.     

Some extremal results on circles containing points

We define (n) to be the largest number such that for every setP ofn points in the plane, there exist two pointsx, y P, where every circle containingx andy contains (n) points ofP. We establish lower and upper bounds for (n) and show that [n/27]+2(n)[n/4]+1. We define for the special case where then points are restricted to be the vertices of a convex polygon. We show that .     

A generalization of the Bernoulli model occurring in order statistics. I.

Let X=(x₁, ..., x_n) and Y=(y₁, ..., y_m) be independent samples from populations G_x and G_y, x⁽¹⁾ ,... x⁽ⁿ⁾ be ordered statistics constructed from the sample X. A model of trials associated with the occurrence of dependent events A_k={y_k (x⁽ⁱ⁾}, x^(j), i < j, k=1, 2, ..., m, where x⁽ⁱ⁾, x^(j) are order statistics, is considered. This model is a generalization of the Bernoulli model. Distribution of frequencies of occurrences of events A_k and the limit theorems which describe asymptotic properties of these frequencies are investigated.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 4, pp. 518–528, April, 1990.     

Legitimate colorings of projective planes

For a projective plane _n of ordern, let( _n ) denote the minimum numberk, so that there is a coloring of the points of _n ink colors such that no two distinct lines contain precisely the same number of points of each color. Answering a question of A. Rosa, we show that for all sufficiently largen, 5 ( _n ) 8 for every projective plane _n of ordern. Research supported in part by Allon Fellowship and by a grant from the United States Israel Binational Science Foundation     

Error-Correcting Codes over an Alphabet of Four Elements

The problem of finding the values of A_q(n,d)—the maximum size of a code of length n and minimum distance d over an alphabet of q elements—is considered. Upper and lower bounds on A₄(n,d) are presented and some values of this function are settled. A table of best known bounds on A₄(n,d) is given for n 12. When q M < 2q, all parameters for which A_q(n,d) = M are determined.     

Counting finite posets and topologies

A refinement of an algorithm developed by Culberson and Rawlins yields the numbers of all partially ordered sets (posets) with n points and k antichains for n11 and all relevant integers k. Using these numbers in connection with certain formulae derived earlier by the first author, one can now compute the numbers of all quasiordered sets, posets, connected posets etc. with n points for n14. Using the well-known one-to-one correspondence between finite quasiordered sets and finite topological spaces, one obtains the numbers of finite topological spaces with n points and k open sets for n11 and all k, and then the numbers of all topologies on n14 points satisfying various degrees of separation and connectedness properties, respectively. The number of (connected) topologies on 14 points exceeds 10²³.     

On the sublattices of the Barnes-wall lattice

This paper is connected with the fundamental work of E.S. Barnes and G.E. Wall [1] in which the authors defined the so-called Barnes-Wall lattice. We shall determine the number of minima of some special sublattices of dimension 2 ⁿ –k of this lattice, where 1kn.Supported by Hung. Nat. Found for Sci. Research (OTKA) grant no. 1615 (1992)     

On elementary equivalence and isomorphism of clone segments

The principal application of a general theorem proved here shows that for any choice 1mnp of integers there exist metric spacesX andY such that the initialk-segments of their clones of continuous maps coincide exactly whenkm, are isomorphic exactly whenkn, and are elementarily equivalent exactly whenkp.Dedicated to Prof. László Fuchs on the occasion of his 70th birthday     

The asymptotic behavior of the spectral function of an operator in Lp with discrete spectrum

The asymptotic behavior in L ^p ,where 1 p + ,of the spectral function of a perturbed discrete operator, defined on an n-dimensional compact manifold, is found. Translated from Trudy Seminara imeni I. G. Petrovskogo, No. 16, pp. 182–185, 1992.     

Indices of Maximal Subgroups of Finite Soluble Groups

We look at the structure of a soluble group G depending on the value of a function m(G)= max m _p G), where m _p(G)=max{log_p|G:M| | M< G, |G:M|=p ^a}, p (G). Theorem 1 states that for a soluble group G, (1) r(G/ (G))= m(G); (2) d(G/ (G)) 1+ (m(G)) 3+m(G); (3) l _p(G) 1+t, where 2^t-1<m _p(G) 2^t. Here, (G) is the Frattini subgroup of G, and r(G), d(G), and l _p(G) are, respectively, the principal rank, the derived length, and the p-length of G. The maximum of derived lengths of completely reducible soluble subgroups of a general linear group GL(n,F) of degree n, where F is a field, is denoted by (n). The function m(G) allows us to establish the existence of a new class of conjugate subgroups in soluble groups. Namely, Theorem 2 maintains that for any natural k, every soluble group G contains a subgroup K possessing the following properties: (1) m(K); k; (2) if T and H are subgroups of G such that K T <_max <_max H G then |H:T|=p ^t for some prime p and for t>k. Moreover, every two subgroups of G enjoying (1) and (2) are mutually conjugate.     

Block SSOR preconditionings for high order 3d fe systems

For solving 3D high order hierarchical FE systems the block SSOR preconditioned CG algorithms based on new stripwise block two-color orderings of degrees of freedom and providing for efficient concurrent/vector implementation are suggested. As demonstrated by numerical results for the 3D Navier equations approximated using hierarchical orderp, 2 p 5, FE's the convergence rate of such BSSOR-CG algorithms is only slightly dependent onp and mesh nonunformity.     

Global optimization for molecular conformation problems

A primal-relaxed dual global optimization algorithm is presented along with an extensive review for finding the global minimum energy configurations of microclusters composed by particles interacting with any type of two-body central forces. First, the original nonconvex expression for the total potential energy is transformed to the difference of two convex functions (DC transformation) via an eigenvalue analysis performed for each pair potential that constitutes the total potential energy function. Then, a decomposition strategy based on the GOP algorithm [1–4] is designed to provide tight upper and lower bounds on the global minimum through the solutions of a sequence of relaxed dual subproblems. A number of theoretical results are included which expedite the computational effort by exploiting the special mathematical structure of the problem. The proposed approach attains-convergence to the global minimum in a finite number of iterations. Based on this procedure global optimum solutions are generated for small Lennard-Jones and Morse (a=3) microclustersn7. For larger clusters (8N24 for Lennard-Jones and 8N30 for Morse), tight lower and upper bounds on the global solution are provided which serve as excellent initial points for local optimization approaches.     

Convex independent sets and 7-holes in restricted planar point sets

For a finite setA of points in the plane, letq(A) denote the ratio of the maximum distance of any pair of points ofA to the minimum distance of any pair of points ofA. Fork>0 letc (k) denote the largest integerc such that any setA ofk points in general position in the plane, satisfying for fixed , contains at leastc convex independent points. We determine the exact asymptotic behavior ofc (k), proving that there are two positive constants=(), such thatk ^1/3c (k)k ^1/3. To establish the upper bound ofc (k) we construct a set, which also solves (affirmatively) the problem of Alonet al. [1] about the existence of a setA ofk points in general position without a 7-hole (i.e., vertices of a convex 7-gon containing no other points fromA), satisfying . The construction uses Horton sets, which generalize sets without 7-holes constructed by Horton and which have some interesting properties.     

Packing random items of three colors

Consider three colors 1,2,3, and forj3, considern items (X _i,j)in of colorj. We want to pack these items inn bins of equal capacity (the bin size is not fixed, and is to be determined once all the objects are known), subject to the condition that each bin must contain exactly one item of each color, and that the total item sizes attributed to any given bin does not exceed the bin capacity. Consider the stochastic model where the random variables (X _i,jj)in,j3 are independent uniformly distributed over [0,1]. We show that there is a polynomial-time algorithm that produces a packing which has a wasted spaceK logn with overwhelming probability.Work partially supported by an N.S.F. grant.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

Random Walks Crossing High Level Curved Boundaries

Let {S _n} be a random walk, generated by i.i.d. increments X _i which drifts weakly to in the sense that as n . Suppose k0, k1, and E|X ₁|^1\k = if k>1. Then we show that the probability that S. crosses the curve nan ^K before it crosses the curve n –an ^k tends to 1 as a . This intuitively plausible result is not true for k = 1, however, and for 1/2 <k<1, the converse results are not true in general, either. More general boundaries g(n) than g(n) = n ^k are also considered, and we also prove similar results for first passages out of regions like { (n, y): n1, |y| (a + n) ^k } as a .     

How large delays build up in a GI/G/1 queue

LetW _k denote the waiting time of customerk, k 0, in an initially empty GI/G/1 queue. Fixa> 0. We prove weak limit theorems describing the behaviour ofW _k /n, 0kn, given W_n >na. LetX have the distribution of the difference between the service and interarrival distributions. We consider queues for which Cramer type conditions hold forX, and queues for whichX has regularly varying positive tail.The results can also be interpreted as conditional limit theorems, conditional on large maxima in the partial sums of random walks with negative drift.Research supported by the NSF under Grant NCR 8710840 and under the PYI Award NCR 8857731.