A Decomposition Method for Global and Local Quadratic Minimization

We present a decomposition method for indefinite quadratic programming problems having n variables and m linear constraints. The given problem is decomposed into at most m QP subproblems each having m linear constraints and n-1 variables. All global minima, all isolated local minima and some of the non-isolated local minima for the given problem are obtained from those of the lower dimensional subproblems. One way to continue solving the given problem is to apply the decomposition method again to the subproblems and repeatedly doing so until subproblems of dimension 1 are produced and these can be solved directly. A technique to reduce the potentially large number of subproblems is formulated.     

Global Optimization: On Pathlengths in Min-Max Graphs

Let f be a smooth nondegenerate real valued function on a finite dimensional, compact and connected Riemannian manifold. The bipartite min-max graph is defined as follows. Its nodes are formed by the set of local minima and the set of local maxima. Two nodes (a local minimum and a local maximum) are connected in by means of an edge if some trajectory of the corresponding gradient flow connects them. Given a natural number k, we construct a function f such that the length of the shortest path in between two specific local minima exceeds k. The latter construction is independent of the underlying Riemannian metric.     

The non-existence of certain regular graphs of girth 5

For certain positive integers k it is shown that there is no k-regular graph with girth 5 having k² + 3 vertices. This provides a new lower bound for the number of vertices of girth 5 graphs with these valences.     

For mixing transformations rank(T k)=k·rank(T)

For the class of finite-rank transformations having no partial rigidity (this contains the class of mixing transformations) rank behaves like a logarithm on positive powers in that rk(T ^k)=k·rk(T). Research partially supported by National Science Foundation grant #DMS 8501519.     

Examples involving the geometric form of level curves of harmonic functions

In the x-y plane, we give, for example, a Jordan curve Γ containing exactly one local maximum and one local minimum in the y-direction, such that some level curve of the capacity potential in the exterior complement of Γ has at least n local maxima and n local minima in the y-direction, n being any prescribed number.     

Stationary layered solutions in {\mathbb{R}}^2 for a class of non autonomous Allen-Cahn equations

We consider a class of non autonomous Allen-Cahn equations where is a multiple-well potential and is a periodic, positive, non-constant function. We look for solutions to (0.1) having uniform limits as corresponding to minima of W. We show, via variational methods, that under a nondegeneracy condition on the set of heteroclinic solutions of the associated ordinary differential equation the equation (0.1) has solutions which depends on both the variables x andy. In contrast, when a is constant such nondegeneracy condition is not satisfied and all such solutions are known to depend only on x. Received April 16, 1999 / Accepted October 1, 1999 / Published online June 28, 2000     

Engel words and the Restricted Burnside Problem

The following theorem is proved. For any positive integers n and k there exists a number s = s(n, k) depending only on n and k such that the class of all groups G satisfying the identity ^n 1{\left(\left[x_1, {}_ky_1\right] \cdots \left[x_s, {}_ky_s\right]\right)^n \equiv 1} and having the verbal subgroup corresponding to the kth Engel word locally finite is a variety.     

Existence, multiplicity and concentration of bound states for a quasilinear elliptic field equation

In this paper we study existence, multiplicity and concentration of solutions for the following nonlinear field equation where the potential V is positive and W is an appropriate singular function. Here is regarded as a small parameter. Under suitable conditions on V and W we find solutions exhibiting a concentration behaviour at an absolute minimum of V as Such solutions are obtained as local minima for the associated functional; the proofs of our results rely on a careful analysis of the behaviour of minimizing sequences and use arguments inspired by the concentration-compactness principle. Received July 21, 1999; Accepted April 9, 2000 / Published online September 14, 2000     

Special monochromatic trees in two-colored complete graphs

For a positive integer k, a set of k + 1 vertices in a graph is a k-cluster if the difference between degrees of any two of its vertices is at most k − 1. Given any tree T with at least k³ edges, we show that for each graph G of sufficiently large order, either G or its complement contains a copy of T such that some vertices in the copy form a k-cluster in G. The same conclusion holds for any tree T having a vertex of degree more than k. © 1997 John Wiley & Sons, Inc.     

Local time and a particle picture for Euclidean field theory

We study intersection properties of Wiener processes in the plane. For each positive integer k we show that k independent Wiener processes intersect almost surely in a set of Hausdorff dimension two, and that the set of points a single process visits at least k distinct times also has dimension two. We construct a functional on configurations of k independent Wiener processes that measures the extent to which the trajectories of the k processes intersect. We prove certain L^p estimates for this functional and show that it is a local time for a certain vector-valued multiparameter stochastic process.     

Minima of initial segments of infinite sequences of reals

Suppose that 〈x_k〉_k∈? is a countable sequence of real numbers. Working in the usual subsystems for reverse mathematics, RCA₀ suffices to prove the existence of a sequence of reals 〈u_k〉_k∈? such that for each k, u_k is the minimum of {x₀, x₁, …, x_k}. However, if we wish to prove the existence of a sequence of integer indices of minima of initial segments of 〈x_k〉_k∈?, the stronger subsystem WKL₀ is required. Following the presentation of these reverse mathematics results, we will derive computability theoretic corollaries and use them to illustrate a distinction between computable analysis and constructive analysis. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Duality in the cohomology of crystalline local systems

Let k be a perfect field of a positive characteristic p, K-the fraction field of the ring of Witt vectors W(k) Let X be a smooth and proper scheme over W(k). We present a candidate for a cohomology theory with coefficients in crystalline local systems: p -adic étale local systems on X_K characterized by associating to them so called Fontaine-crystals on the crystalline site of the special fiber X _k. We show that this cohomology satysfies a duality theorem.     

The Typical Growth of the k th Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of .     

A semistrong sufficiency condition for optimality in nonconvex programming and its connection to the perturbation problem

What happens when a nonconvex program, having a local solutionx ⁰ at which the gradients of the binding constraints are linearly independent, but without strict complementarity hypothesis, is perturbed? Under a relatively weak second-order assumption (some nonnegative second-order terms are supposed to be strictly positive), the perturbed problem has, in the neighborhood ofx ⁰, a finite number of local minima, situated on curves that are connected to some pseudo-solutions of the tangent quadratic problem.     

An upper bound for the total chromatic number of dense graphs

In this paper we consider those graphs that have maximum degree at least 1/k times their order, where k is a (small) positive integer. A result of Hajnal and Szemerédi concerning equitable vertex-colorings and an adaptation of the standard proof of Vizing's Theorem are used to show that if the maximum degree of a graph G satisfies Δ(G) ≥ |V(G)/k, then X″(G) ≤ Δ(G) + 2k + 1. This upper bound is an improvement on the currently available upper bounds for dense graphs having large order.     

Simultaneous approximation in number fields

Summary We present here the solution of a problem of J.-J. Sansuc together with a natural generalization of it. This problem of Sansuc is, given a number fieldk, to find the smallest positive integerm for which there exists a finitely generated subgroup of rankm ofk ^x having a dense image in (R _Q k)^x under the canonical embedding. This integer is the number of archimedean places ofk plus one.Oblatum 28-I-1992This work was partially supported by NSERC and FCAR grants     

Some properties and characterizations for generalized multivariate Pareto distributions

In this paper, several distributional properties and characterization theorems of the generalized multivariate Pareto distributions are studied. It is found that the multivariate Pareto distributions have many mixture properties. They are mixed either by geometric, Weibull, or exponential variables. The multivariate Pareto, MP^(k)(I), MP^(k)(II), and MP^(k)(IV) families have closure property under finite sample minima. The MP^(k)(III) family is closed under both geometric minima and geometric maxima. Through the geometric minima procedure, one characterization theorem for MP^(k)(III) distribution is developed. Moreover, the MP^(k)(III) distribution is proved as the limit multivariate distribution under repeated geometric minimization. Also, a characterization theorem for the homogeneous MP^(k)(IV) distribution via the weighted minima among the ordered coordinates is developed. Finally, the MP^(k)(II) family is shown to have the truncation invariant property.     

Improvement on the northby algorithm for molecular conformation: Better solutions

In 1987, Northby presented an efficient lattice based search and optimization procedure to compute ground states ofn-atom Lennard-Jones clusters and reported putative global minima for 13n150. In this paper, we introduce simple data structures which reduce the time complexity of the Northby algorithm for lattice search fromO(n^5/3) per move toO(n^2/3) per move for ann-atom cluster involving full Lennard-Jones potential function. If nearest neighbor potential function is used, the time complexity can be further reduced toO(logn) per move for ann-atom cluster. The lattice local minimizers with lowest potential function values are relaxed by a powerful Truncated Newton algorithm. We are able to reproduce the minima reported by Northby. The improved algorithm is so efficient that less than 3 minutes of CPU time on the Cray-XMP is required for each cluster size in the above range. We then further improve the Northby algorithm by relaxingevery lattice local minimizer found in the process. This certainly requires more time. However, lower energy configurations were found with this improved algorithm forn=65, 66, 75, 76, 77 and 134. These findings also show that in some cases, the relaxation of a lattice local minimizer with a worse potential function value may lead to a local minimizer with a better potential function value.     

The Typical Growth of the kth Excess in a Random Integer Partition

 For a partition , of a positive integer n chosen uniformly at random from the set of all such partitions, the kth excess is defined by if . We prove a bivariate local limit theorem for as . The whole range of possible values of k is studied. It turns out that ρ and η _k are asymptotically independent and both follow the doubly exponential (extreme value) probability law in a suitable neighbourhood of . Received February 6, 2001; in revised form February 25, 2002 Published online August 5, 2002     

Local edge colorings that are global

A local (H, k)-coloring of K_n is a coloring of its edges in which each of its subgraphs isomorphic to H is colored by at most k colors. A necessary condition on H (conjectured to be sufficient) is found such that each local (H, k)-coloring is a k-coloring. Furthermore, necessary and sufficient conditions are given for each local (H, k)-coloring to be a coloring by a bounded number of colors.