Bounds for arrays of dots with distinct slopes or lengths

Ann×m sonar sequence is a subset of then×m grid with exactly one point in each column, such that the vectors determined by them are all distinct. We show that for fixedn the maximalm for which a sonar sequence exists satisfiesn–Cn ^11/20<m<n+4n ^2/3 for alln andm>n+c logn log logn for infinitely manyn.Another problem concerns the maximal numberD of points that can be selected from then×m grid so that all the vectors have slopes. We proven ^1/2Dn ^4/5 Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901Research conducted by Herbert Taylor was sponsored in part by the Office of Naval Research under ONR Contract No. N00014-90-J-1341.     

Irrepresentability of short semilattices by euclidean subspaces

A semilatticeS isrepresentable by subspaces of R ^k if, to eachx S we can assign a subspace so thatx y=z inS if and only if . Every height-2 semilattice is representable inR ². We show that for everyk there is a height-3 semilattice which is not representable by subspaces ofR ^k.Presented by J. Berman.Research supported in part by the National Science Foundation.Research supported in part by the Office of Naval Research.     

d-Cube decompositions ofK n/K m

Necessary conditions onn, m andd are given for the existence of an edge-disjoint decomposition ofK _n/K _m into copies of the graph of ad-dimensional cube. Sufficiency is shown whend=3 and, in some cases, whend=2^t. We settle the problem of embedding 3-cube decompositions ofK _m into 3-cube decompositions ofK _n, wherenm.Research of P.A. and D.E.B. supported by Australian Research Council grant A49532750Research of D.E.B. supported by Australian Research Council grant ARCPDF015GResearch of S.I.E. and C.V.E. supported by Illinois State University Research Office     

Higher order asymptotic theory for normalizing transformations of maximum likelihood estimators

Suppose thatX _n =(X ₁,...X _n) is a collection ofm-dimensional random vectorsX _i forming a stochastic process with a parameter . Let be the MLE of . We assume that a transformationA( ) of has thek-thorder Edgeworth expansion (k=2,3). IfA extinguishes the terms in the Edgeworth expansion up tok-th-order (k2), then we say thatA is thek-th-order normalizing transformation. In this paper, we elucidate thek-th-order asymptotics of the normalizing transformations. Some conditions forA to be thek-th-order normalizing transformation will be given. Our results are very general, and can be applied to the i.i.d. case, multivariate analysis and time series analysis. Finally, we also study thek-th-order asymptotics of a modified signed log likelihood ratio in terms of the Edgeworth approximation.Research supported by the Office of Naval Research Contract N00014-91-J-1020.     

An extrapolation method for the quadrature of functions with singularities in the vicinity of the interval of integration

Summary A method is proposed for the calculation of integrals and for positive small values ofb withg(x) analytic in a disk centered at the origin andr positive rational. The integrals are splitted into a singular part and a regular function ofb ^r which can be extrapolated to smallb's. A principal value integral and special cases whereg(x) is not analytic at the origin are also considered.     

Methods of conjugate directions versus quasi-Newton methods

It is shown that algorithms for minimizing an unconstrained functionF(x), x E ⁿ , which are solely methods of conjugate directions can be expected to exhibit only ann or (n–1) step superlinear rate of convergence to an isolated local minimizer. This is contrasted with quasi-Newton methods which can be expected to exhibit every step superlinear convergence. Similar statements about a quadratic rate of convergence hold when a Lipschitz condition is placed on the second derivatives ofF(x). Research was supported in part by Army Research Office, Contract Number DAHC 19-69-C-0017 and the Office of Naval Research, Contract Number N00014-71-C-0116 (NR 047-99).     

Ordering distributions by scaled order statistics

Motivated by applications in reliability theory, we define a preordering (X ₁, ...,X _n) (Y ₁ ...,Y _n) of nonnegative random vectors by requiring thek-th order statistic ofa ₁ X ₁,..., a _n X _n to be stochastically smaller than thek-th order statistic ofa ₁ Y ₁, ...,a _n Y _n for all choices ofa _i >0,i=1, 2, ...,n. We identify a class of functionsM _{k, n} such that if and only ifE(X)E(Y) for allM _k,n. Some preservation results related to the ordering are obtained. Some applications of the results in reliability theory are given.Supported by the Air Force Office of Scientific Research, U.S.A.F., under Grant AFOSR-84-0205.     

Halfspace range search: An algorithmic application ofk-sets

Given a fixed setS ofn points inE ³ and a query plane, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side of. We prove that withO(n(logn)⁸ (loglogn)⁴) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE ³ isO(nk ⁵); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.Supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.Supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424.     

A lower bound for the optimal crossing-free Hamiltonian cycle problem

Consider a drawing in the plane ofK _n , the complete graph onn vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing ofK _n . If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let (n) represent the maximum number of cfhc's of any drawing ofK _n , and (n) the maximum number of cfhc's of any rectilinear drawing ofK _n . The problem of determining (n) and (n), and determining which drawings have this many cfhc's, is known as the optimal cfhc problem. We present a brief survey of recent work on this problem, and then, employing a recursive counting argument based on computer enumeration, we establish a substantially improved lower bound for (n) and (n). In particular, it is shown that (n) is at leastk × 3.2684 ⁿ . We conjecture that both (n) and (n) are at mostc × 4.5 ⁿ .This research, part of which was conducted at Queen's University, was supported by an N.S.E.R.C. postgraduate scholarship.     

Error bounds for strongly convex programs and (super)linearly convergent iterative schemes for the least 2-norm solution of linear programs

Given an arbitrary point (x, u) inR ⁿ × R ₊ ^m , we give bounds on the Euclidean distance betweenx and the unique solution to a strongly convex program in terms of the violations of the Karush-Kuhn-Tucker conditions by the arbitrary point (x, u). These bounds are then used to derive linearly and superlinearly convergent iterative schemes for obtaining the unique least 2-norm solution of a linear program. These schemes can be used effectively in conjunction with the successive overrelaxation (SOR) methods for solving very large sparse linear programs.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Science Foundation Grant No. DCR-8420963 and Air Force Office of Scientific Research Grant No. AFOSR-ISSA-85-00080.On leave from CRAI, via Bernini 5, Rende, Cosenza, Italy.     

On set systems not containing delta systems

Some constructions of systems ofn-sets not containing (k) systems are given. The constructions were produced by both analytical and computational methods.Research supported by Office of Naval Research Grant No. N0014-88-K0211.     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

Beste Quadraturformeln für Integrale mit einer Gewichtsfunktion

Let be a fixed matrix with elements that are 0 or 1 and letX be a fixed set ofm+1 different knots. The problem is to find necessary and sufficient conditions for (E, X) to guarantee the existence of a quadrature formula with a remainder term of type for any choice of a weight functionw(t) and satisfyingR(f)=0 forf a polynomial of degree at mostn–1. The result generalizes the corresponding result ofI. J. Schoenberg for the special case of quasi-Lagrange-matricesE. —in case of the existence ofR it is possible to calculate the best quadrature formulaR ^* in the sense ofSard by integrating splines of degree 2n–1. But ifE contains onlyn ones it is sufficient to integrate polynomials of degreen–1.     

Containing and shrinking ellipsoids in the path-following algorithm

We describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vectors. Furthermore, the volumes of the ellipsoids shrink at the ratio , in comparison to 2^–(1) in Karmarkar's algorithm and 2^–(1/n) in the ellipsoid method. We also show how to use these ellipsoids to identify the optimal basis in the course of the algorithm for linear programming.Research supported by The U.S. Army Research Office through The Mathematical Sciences Institute of Cornell University when the author was visiting at Cornell.Research supported in part by National Science Foundation Grant ECS-8602534 and Office of Naval Research Contract N00014-87-K-0212.     

Electron density distribution in a cylinder

Zusammenfassung Die radiale Elektronendichteverteilung in einem unendlich langen Zylinder wird für den Gleichgewichtsfall berechnet. Dabei ergibt sich die Existenz einer maximalen Dichten _max*, welchem Wert die Dichte in der Achse des Zylinders zustrebt, wenn die mittlere Dichte im Querschnitt gegen unendlich geht. Figur 1 zeigt, dass für <n _max* die Dichte über den Querschnitt praktisch konstant ist. Fürn>n _max* steigt die Dichte an der Wand mit an.

---

---

This research was supported in part by the United States Air Force through the Air Force Office of Scientific Research of the Air Research and Development Command under Contract No. AF 49(638)-401     

A PL homotopy for finding all the roots of a polynomial

This paper presents a constructive method which gives, for any polynomialF(Z) of the degreen, approximate values of all the roots ofF(Z).. The point of the method is on the use of a piecewise linear function (Z, t) which approximates a homotopyH(Z, t) betweenF(Z) and a polynomialG(Z) of the degreen withn known simple roots. It is shown that the set of solutions to (Z, t) = 0 includesn distinct paths,m of which converges to a root ofF(Z) if and only if the root has the multiplicitym. Starting from givenn roots ofG(Z), a complementary pivot algorithm generates thosen paths.This work was supported by grants from Management Science Development Foundation and Takeda Science Foundation.     

Eigenvalues of the adjacency matrix of tetrahedral graphs

A tetrahedral graph is defined to be a graphG, whose vertices are identified with the unordered triplets onn symbols, such that vertices are adjacent if and only if the corresponding triplets have two symbols in common. Ifn ₂ (x) denotes the number of verticesy, which are at distance 2 fromx andA(G) denotes the adjacency matrix ofG, thenG has the following properties: P₁) the number of vertices is . P₂)G is connected and regular. P₃)n ₂ (x) = 3/2(n–3)(n–4) for allx inG. P₄) the distinct eigenvalues ofA(G) are –3, 2n–9,n–7, 3(n–3). We show that, ifn > 16, then any graphG (with no loops and multiple edges) having the properties P₁)–P₄) must be a tetrahedral graph. An alternative characterization of tetrahedral graphs has been given by the authors in [1].This research was supported by the National Science Foundation Grant No. GP-5790, and the Army Research Office (Durham) Grant No. DA-ARO-D-31-12-G910. (Institute of Statistics Mimeo Series No. 571, March 1968.)     

On the isomorphisms and automorphism groups of circulants

Denote byC _n(S) the circulant graph (or digraph). LetM be a minimal generating element subset ofZ _n, the cyclic group of integers modulon, and In this paper, we discuss the problems about the automorphism group and isomorphisms ofC _n(S). When M S , we determine the automorphism group ofC _n(S) and prove that for any T if and only ifT = S, where is an integer relatively prime ton. The automorphism groups and isomorphisms of some other types of circulant graphs (or digraphs) are also considered. In the last section of this paper, we give a relation between the isomorphisms and the automorphism groups of circulants.     

Law of the iterated logarithm for perturbed empirical distribution functions evaluated at a random point for nonstationary random variables

We consider perturbed empirical distribution functions , where {Ginn, n1} is a sequence of continuous distribution functions converging weakly to the distribution function of unit mass at 0, and {X _{i, i}1} is a non-stationary sequence of absolutely regular random variables. We derive the almost sure representation and the law of the iterated logarithm for the statistic whereU _n is aU-statistic based onX ₁,...,X _n . The results obtained extend or generalize the results of Nadaraya,⁽⁷⁾ Winter,⁽¹⁶⁾ Puri and Ralescu,^(9,10) Oodaira and Yoshihara,⁽⁸⁾ and Yoshihara,⁽¹⁹⁾ among others.Research supported by the Office of Naval Research Contract N00014-91-J-1020.     

Excursions of a Markov process induced by continuous additive functionals

Summary Let be a continuous additive functional with supportC of a Hunt processX={X _t;t0}. LetS={S _t;t0} be the inverse of and put . For each time of discontinuityu ofS, letZ _u be the corresponding excursion ofX outside ofC. The conditional structure of the excursion process {Z _u;u0} given the paths ofY={Y _t;t0} is studied. It is shown that conditionally, givenY, the excursion process is a Poisson random measure.Support from the Office of Naval Research (Contract Number N-00014-67-A-0112-0011) and the National Science Foundation (Grant Number ENG 75-02026) is gratefully acknowledged