A minimal cutset of the boolean lattice with almost all members

Two almost explicit constructions are given satisfying the title.This research was done while the authors visited the Institute for Mathematics and its Applications at the University of Minnesota, Minneapolis, MN 55455.Research supported in part by Hungarian National Foundation for Scientific Research, grant no. 1812.Research supported in part by NSF Grant MDS 87-01475.Research supported in part by NSF grant DMS 86-06225 and Airforce Grant OSR-86-0076.     

Local spectral properties of multipliers on Banach algebras

Supported in part by NSF Grant DMS 90-96108. This work was completed while the first author visited Mississippi State University. Financial support and generous hospitality are gratefully acknowledged.     

Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited

Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.Dedicated to the Memory of Magnus R. Hestenes, 1906–1991This research was supported in part by NSF Cooperative Agreement CCR-88-09615 and was initiated while the first author was at Rice University as a Visiting Member of the Center for Research in Parallel Computation.The authors thank Yinyu Ye for constructive comments and discussions concerning this material.This author was supported in part by NSF Grant DMS-91-02761 and DOE Grant DE-FG05-91-ER25100.This author was supported in part by AFOSR Grant 89-0363, DOE Grant DE-FG05-86-ER25017, and ARO Grant 9DAAL03-90-G-0093.     

On the connected components of the space of line transversals to a family of convex sets

Let ℒ be the space of line transversals to a finite family of pairwise disjoint compact convex sets in ℝ³. We prove that each connected component of ℒ can itself be represented as the space of transversals to some finite family of pairwise disjoint compact convex sets. The research of J. E. Goodman was supported in part by NSF Grant DMS91-22065 and by NSA Grant MDA904-92-H-3069. R. Pollack's research was supported in part by NSF Grant CCR91-22103 and by NSA Grant MDA904-92-H-3075. The research of R. Wenger was supported in part by NSA Grant MDA904-93-H-3026 and by the NSF Regional Geometry Institute (Smith College, July 1993) Grant DMS90-13220.     

Scalar labelings for homotopy paths

Two scalar labelings are introduced for obtaining approximate solutions to systems of nonlinear equations by simplicial approximation. Under reasonable assumptions the new scalar-labeling algorithms are shown to follow, in a limiting sense, homotopy paths which can also be tracked by piecewise linear vector labeling algorithms. Though the new algorithms eliminate the need to pivot on a system of linear equations, the question of relative computational efficiency is unresolved.The work of this author was supported in part by NSF Grant No. MCS-77-15509 and by ARO Grant No. DAAG-29-78-G-0160.The work of this author was supported in part by ONR Grant No. N00014-75-C-0495 and NSF Grant No. 81058.     

Analysis of heuristics for the design of tree networks

We analyze the tour partitioning heuristics for the Capacitated Minimum Spanning Tree problem. Lower bounds for the worst-case performance ratios of these heuristics are obtained by using worst-case examples. We also generalize the heuristics to the multi-center case with the same worst-case bounds.The work of the first author was supported by a Dean Summer Research Grant from Owen Graduate School of Management, Vanderbilt University.Work done in part in the Department of Industrial Engineering and Operations Research at Columbia University.The work of the last two authors was supported in part by ONR contract N00014-90-J-1649, NSF contract DDM-8922712 and the Center for Telecommunications Research under NSF contract CDR 84-21402.     

An elementary approach to lower bounds in geometric discrepancy

For eachd≥2, it is possible to placen points ind-space so that, given any two-coloring of the points, a half-space exists within which one color outnumbers the other by as much ascn ^1/2−1/2d , for some constantc>0 depending ond. This result was proven in a slightly weaker form by Beck and the bound was later tightened by Alexander. It was recently shown to be asymptotically optimal by Matoušek. We present a proof of the lower bound, which is based on Alexander's technique but is technically simpler and more accessible. We present three variants of the proof, for three diffrent cases, to provide more intuitive insight into the “large-discrepancy” phenomenon. We also give geometric and probabilistic interpretations of the technique. Work by Bernard Chazelle has been supported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. Work by Jiří Matoušek has been supported by Charles University Grant No. 351, by Czech Republic Grant GAČR 201/93/2167 and in part by DIMACS. Work by Micha Sharir has been supported by NSF Grant CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

A counterexample to the finite height conjecture

There is an infinite subdirectly irreducible lattice which generates a variety that contains only finitely many subvarietes.The author was supported in part by NSF Grant DMS 94-00511     

Knot polynomials and Vassiliev's invariants

Summary A fundamental relationship is established between Jones' knot invariants and Vassiliev's knot invariants. Since Vassiliev's knot invariants have a firm grounding in classical topology, one obtains as a result a first step in understanding the Jones polynomial by topological methods.Oblatum 20-V-1991 & 10-VI-1992Research supported in part by NSF Grant DMS-88-055627.Research supported in part by NSF Grant DMS-90-04017.     

Geometric rigidity of transcendental meromorphic functions

The classes of dynamically and geometrically tame functions meromorphic outside a small set are introduced. The Julia sets of geometrically tame functions are proven to be either geometrical circle (in ) or to have Hausdorff dimension strictly larger than 1. Vast classes of dynamically and geometrically tame functions are identified. The research of both authors was supported in part by the Polish KBN Grant No 2 PO3A 034 25, the Warsaw University of Technology Grant no 504G 11200043000 and by the NSF/PAN grant INT-0306004. The research of the second author was supported in part by the NSF Grant DMS 0400481.     

Cord-slope form of Taylor's expansion in univariate global optimization

Interval arithmetic and Taylor's formula can be used to bound the slope of the cord of a univariate function at a given point. This leads in turn to bounding the values of the function itself. Computing such bounds for the function, its first and second derviatives, allows the determination of intervals in which this function cannot have a global minimum. Exploiting this information together with a simple branching rule yields an efficient algorithm for global minimization of univariate functions. Computational experience is reported.The first and second authors have been supported by FCAR (Fonds pour la Formation de Chercheurs et l'Aide à la Recherche) Grant 92EQ1048 and AFOSR Grant 90-0008 to Rutgers University. The first author has also been supported by NSERC (Natural Sciences and Engineering Research Council of Canada) Grant to HEC and NSERC Grant GP0105574. The second author has been supported by NSERC Grant GP0036426, FCAR Grant 90NC0305, and a NSF Visiting Professorship for Women in Science at Princeton University. Work of the third author was done in part while he was a graduate student at the Department of Mathematics, Rutgers University, New Brunswick, New Jersey, USA and during a visit to GERAD, June–August 1991.     

Universal deformation rings need not be complete intersections

We answer a question of M. Flach by showing that there is a linear representation of a profinite group whose (unrestricted) universal deformation ring is not a complete intersection. We show that such examples arise in arithmetic in the following way. There are infinitely many real quadratic fields F for which there is a mod 2 representation of the Galois group of the maximal unramified extension of F whose universal deformation ring is not a complete intersection. Finally, we discuss bounds on the singularities of universal deformation rings of representations of finite groups in terms of the nilpotency of the associated defect groups. The first author was supported in part by NSF Grant DMS01-39737 and NSA Grant H98230-06-1-0021. The second author was supported in part by NSF Grants DMS00-70433 and DMS05-00106.     

Null boundary controllability for semilinear heat equations

We consider null boundary controllability for one-dimensional semilinear heat equations. We obtain null boundary controllability results for semilinear equations when the initial data is bounded continuous and sufficiently small. In this work we also prove a version of the nonlinear Cauchy-Kowalevski theorem.W. Littman was partially supported by NSF Grant DMS 90-02919. The results of this paper were presented by Yung-Jen Lin Guo at the P.D.E. seminar at the University of Minnesota on January 27, 1993 and by W. Littman at the First International Conference on Dynamics Systems and Applications held in Atlanta in May 1993.     

Modified predictor-corrector algorithm for locating weighted centers in linear programming

In certain applications of linear programming, the determination of a particular solution, the weighted center of the solution set, is often desired, giving rise to the need for algorithms capable of locating such center. In this paper, we modify the Mizuno-Todd-Ye predictor-corrector algorithm so that the modified algorithm is guaranteed to converge to the weighted center for given weights. The key idea is to ensure that iterates remain in a sequence of shrinking neighborhoods of the weighted central path. The modified algorithm also possesses polynomiality and superlinear convergence.The work of the first author was supported in part by NSF Grant DMS-91-02761 and DOE Contract DE-FG05-91-ER25100.The work of the second author was supported in part by NSF Cooperative Agreement CCR-88-09615.     

Prime top extensions of division algebra

Every division algebra of degreep ^t has a prime-to-p extension which is a crossed product, ifft ≤ 2. Research of the first author supported in part by the NSA/MSP Grant MDA90-H4001 while the author was on Sabbatical at Yale University Second author is grateful for support order NSF grant DMS-8901778     

On a Conformal Gap and Finiteness Theorem for a Class of Four-Manifolds

In this paper we develop a bubble tree structure for a degenerating class of Riemannian metrics satisfying some global conformal bounds on compact manifolds of dimension 4. Applying the bubble tree structure, we establish a gap theorem, a finiteness theorem for diffeomorphism type for this class, and make a comparison of the solutions of the σ_k equations on a degenerating family of Bach-flat metrics. The first author is supported by NSF Grant DMS–0245266. The second author is supported in part by NSF Grant DMS–0402294. The third author is supported by NSF Grant DMS–0245266. Received: August 2005 Accepted: June 2006     

On degenerate elliptic operators of infinite type

The author was partially supported by NSF Grant DMS 91-01161     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

Uniqueness for diffusions with piecewise constant coefficients

Summary LetL be a second-order partial differential operator inR ^d. LetR ^d be the finite union of disjoint polyhedra. Suppose that the diffusion matrix is everywhere non singular and constant on each polyhedron, and that the drift coefficient is bounded and measurable. We show that the martingale problem associated withL is well-posed.The research of this author was partly supported by NSF Grant DMS 8500581