On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.     

A generalization of the ingleton—Main lemma and a class of non-algebraic matroids

Dedicated to professor Jan-Erik Roos on his fifthieth birthday     

Local n-connectivity of decomposition spaces

A corollary of the main result of this paper is the following Theorem. Suppose f: X → Y is a closed surjection of metrizable spaces whose point inverses are LC^{n + 1}-divisors (n ? 1). If Y is complete and f is homology n-stable, then Y is LC^{n + 1}provided X is LC^{n + 1}.Intuitively, f is homology n-stable if the ?ech homology groups of its point inverses are locally constant up to dimension n. In addition, we obtain sufficient conditions for the Freudenthal compactification to be LCⁿ.     

Relative efficiencies of estimates using patterned covariances or correlations in the multivariate normal estimation problem

Summary The relative efficiency of maximum likelihood estimates is studied when taking advantage of underlying linear patterns in the covariances or correlations when estimating covariance matrices. We compare the variances of estimates of the covariance matrix obtained under two nested patterns with the assumption that the more restricted pattern is the true state. Formulas for the asymptotic variances are given which are exact for linear covariance patterns when explicit maximum likelihood estimates exist. Several specific examples are given using complete symmetry, circular symmetry and general covariance patterns as well as an example involving a covariance matrix with a linear pattern in the correlations.     

Internal fundamental sequences and approximative retracts

We introduce the notion of internal fundamental sequence and prove that any shape morphism from an arbitrary compactum X to an internally movable compactum Y is induced by an internal fundamental sequence. We use this special kind of fundamental sequences to give characterizations and some properties of AANR_C-sets and AANR_N-sets. The paper ends with a section devoted to internal FANR's.     

Linear algorithms for testing the sign stability of a matrix and for findingZ-maximum matchings in acyclic graphs

Summary Ann×n real matrixA=(a _ij ) isstable if each eigenvalue has negative real part, andsign stable (orqualitatively stable) if each matrix B with the same sign-pattern asA is stable, regardless of the magnitudes ofB's entries. Sign stability is of special interest whenA is associated with certain models from ecology or economics in which the actual magnitudes of thea _ij may be very difficult to determine. Using a characterization due to Quirk and Ruppert, and to Jeffries, an efficient algorithm is developed for testing the sign stability ofA. Its time-and-space-complexity are both 0(n ²), and whenA is properly presented that is reduced to 0(max{n, number of nonzero entries ofA}). Part of the algorithm involves maximum matchings, and that subject is treated for its own sake in two final sections.     

Foncteurs isomorphes des catégories d'actions à des catégories de fibrarations

Sans résumé

---

This article is the text of a talk given at the Symposium on Differential Geometry in Debrecen, Hungary, on August 28–September 3, 1975.     

A remark on the tail probability of a distribution

Let {X_n}_n≥1 be a sequence of independent and identically distributed random variables. For each integer n ≥ 1 and positive constants r, t, and ?, let S_n = Σ_j=1ⁿX_j and $\text{E{N}{}_{\mathrm{\infty }}\text{(r, t, ?)} = Σ}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{n}{}^{\mathrm{r?2}}\text{P{|S}{}_{\mathrm{n}}\text{| > ?n}{}^{\mathrm{<mtext>r</mtext><mtext>t</mtext>}}\text{}}$. In this paper, we prove that (1) lim_?→0+?^α(r?1)E{N_∞(r, t, ?)} = K(r, t) if E(X₁) = 0, Var(X₁) = 1, and E(| X₁ |^t) < ∞, where 2 ≤ t < 2r ≤ 2t, $\text{K(r, t) =}\text{{2}{}^{\mathrm{<mtext>\alpha (r?1)</mtext><mtext>2</mtext>}}\text{Γ(}\text{(1 + α(r ? 1))}\text{2}\text{)}}\text{{(r ? 1) Γ(}\text{1}\text{2}\text{)}}$, and $\text{α =}\text{2t}\text{(2r ? t)}$; (2) $\text{lim}{}_{\mathrm{?\to 0+}}\text{G(t, ?)}\text{H(t, ?)}\text{= 0}$ if 2 < t < 4, E(X₁) = 0, Var(X₁) > 0, and E(|X₁|^t) < ∞, where G(t, ?) = E{N_∞(t, t, ?)} = Σ_n=1^∞n^t?2P{| S_n | > ?n} → ∞ as ? → 0+ and $\text{H(t, ?) = E{N}{}_{\mathrm{\infty }}\text{(t, t, ?)} = Σ}{}_{\mathrm{n=1}}{}^{\mathrm{\infty }}\text{n}{}^{\mathrm{t?2}}\text{P{| S}{}_{\mathrm{n}}\text{| > ?n}{}^{\mathrm{<mtext>2</mtext><mtext>t</mtext>}}\text{} → ∞}\text{as}\text{? → 0+}$, i.e., H(t, ?) goes to infinity much faster than G(t, ?) as ? → 0+ if 2 < t < 4, E(X₁) = 0, Var(X₁) > 0, and E(| X₁ |^t) < ∞. Our results provide us with a much better and deeper understanding of the tail probability of a distribution.     

Limit laws for upper and lower extremes from stationary mixing sequences

The aim of this paper is to examine the weak limiting behavior of upper and lower extremes from stationary sequences satisfying dependence conditions similar to D and D′ introduced by Leadbetter (Z. Wahrsch. Verw. Gebiete28 (1974), 289–303). By establishing the convergence in distribution of an associated sequence of point processes, the joint limiting distribution of any collection of upper and lower extremes can be determined. Sufficient and, in some cases, necessary conditions for the asymptotic independence of the upper and lower extremes are also given.     

The rate of strong uniform consistency for the multivariate product-limit estimator

The general asymptotic order of magnitude is determined for the maximal deviation of the multivariate product-limit estimate from the estimated survival function on R^k. This order depends on the joint behavior of the censoring and censored distributions in a well-defined way. Corresponding to specific joint behaviors, several lim sup results are deduced generalizing everything that is known in the univariate case. The results are also extended for the variable censoring model.