The dominating number of a random cubic graph

We show that if G is a random 3-regular graph on n vertices, then its dominating number, D(G), almost surely satisfies .2636n ≤ D(G) ≤ .3126n. © 1995 John Wiley & Sons, Inc.     

Endomorphism valued cohomology and gauge-neutral matter

For several physically interesting Calabi-Yau manifolds, we count and parametrize gauge-neutral matter particles occurring in corresponding superstring compactifications. To this end, we use the technique of exact and spectral sequences and then describe and discuss our results in the more familiar tensor notation.Supported by the Robert A. Welch Foundation and the NSF Grant: PHY 8605978. On leave of absence from the Ruder Bokovi Institute, Bijenika 54, YU-41000 Zagreb, Croatia, Yugoslavia     

Active set algorithms for isotonic regression; A unifying framework

In this and subsequent papers we will show that several algorithms for the isotonic regression problem may be viewed as active set methods. The active set approach provides a unifying framework for studying algorithms for isotonic regression, simplifies the exposition of existing algorithms and leads to several new efficient algorithms. We also investigate the computational complexity of several algorithms.In this paper we consider the isotonic regression problem with respect to a complete order where eachw _i is strictly positive and eachy _i is an arbitrary real number. We show that the Pool Adjacent Violators algorithm (due to Ayer et al., 1955; Miles, 1959; Kruskal, 1964), is a dual feasible active set method and that the Minimum Lower Set algorithm (due to Brunk et al., 1957) is a primal feasible active set method of computational complexity O(n ²). We present a new O(n) primal feasible active set algorithm. Finally we discuss Van Eeden's method and show that it is of worst-case exponential time complexity.This work was supported by the National Science and Engineering Research Council of Canada under Research Grant A8189 and an Ontario Graduate Scholarship.     

A complementary thermodynamic limit for classical Coulomb matter

The canonical equilibrium measure of classical two-component Coulomb matter with regularized interactions is analyzed in a finite volume. It is shown that, in the mean-field regime, the one-particle density is inhomogeneous on a new characteristic length scale _inh. For a system ofN positive andN negative particles, _inh and the characteristic length scale of correlations _corr (=Debye screening length) are related via _inh=(2N)^1/2 _corr. The major conceptual conclusion that is drawn from this is that one needs two nontrivial complementary thermodynamic limits to define the equilibrium thermodynamics of two-component Coulomb systems. One of them is the standard thermodynamic limit (infinite volume), where one takesN, _corr fixed. Its complementary limit is characterized byN, _inh fixed, and is a finite-volume inhomogeneous mean-field limit. The most prominent new feature in the mean-field thermodynamic limit, which is absent in the standard thermodynamic limit, is an anomalous first-order phase transition where the Coulomb system explodes or implodes, respectively. The phase transition is connected with the existence of a metastable plasma phase far below the ionization temperature.     

The convergence rate for the strong law of large numbers: General lattice distributions

LetX ₁,X ₂, ... be a sequence of independent random variables with common lattice distribution functionF having zero mean, and let (S _n ) be the random walk of partial sums. The strong law of large numbers (SLLN) implies that for any and >0

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Block renormalization group for Euclidean Fermions

Block renormalization group transformations (RGT) for lattice and continuum Euclidean Fermions in d dimensions are developed using Fermionic integrals with exponential and -function weight functions. For the free field the sequence of actionsD _k generated by the RGT from D, the Dirac operator, are shown to have exponential decay; uniform ink, after rescaling to the unit lattice. It is shown that the two-point functionD ^–1 admits a simple telescopic sum decomposition into fluctuation two-point functions which for the exponential weight RGT have exponential decay. Contrary to RG intuition the sequence of rescaled actions corresponding to the -function RGT do not have uniform exponential decay and we give examples of initial actions in one dimension where this phenomena occurs for the exponenential weight RGT also.     

On the solution of singular linear systems of algebraic equations by semiiterative methods

Summary For a square matrixT ^n,n , where (I–T) is possibly singular, we investigate the solution of the linear fixed point problemx=T x+c by applying semiiterative methods (SIM's) to the basic iterationx ₀ ⁿ ,x _k T c _k–1+c(k1). Such problems arise if one splits the coefficient matrix of a linear systemA x=b of algebraic equations according toA=M–N (M nonsingular) which leads tox=M ^–1 N x+M ^–1 bT x+c. Even ifx=T x+c is consistent there are cases where the basic iteration fails to converge, namely ifT possesses eigenvalues 1 with ||1, or if =1 is an eigenvalue ofT with nonlinear elementary divisors. In these cases — and also ifx=T x+c is incompatible — we derive necessary and sufficient conditions implying that a SIM tends to a vector which can be described in terms of the Drazin inverse of (I–T). We further give conditions under which is a solution or a least squares solution of (I–T)x=c.Research supported in part by the Alexander von Humboldt-Stiftung