On the complexity of the disjoint paths problem

In this paper we consider the disjoint paths problem. Given a graphG and a subsetS of the edge-set ofG the problem is to decide whether there exists a family of disjoint circuits inG each containing exactly one edge ofS such that every edge inS belongs to a circuit inC. By a well-known theorem of P. Seymour the edge-disjoint paths problem is polynomially solvable for Eulerian planar graphsG. We show that (assumingPNP) one can drop neither planarity nor the Eulerian condition onG without losing polynomial time solvability. We prove theNP-completeness of the planar edge-disjoint paths problem by showing theNP-completeness of the vertex disjoint paths problem for planar graphs with maximum vertex-degree three. This disproves (assumingPNP) a conjecture of A. Schrijver concerning the existence of a polynomial time algorithm for the planar vertex-disjoint paths problem. Furthermore we present a counterexample to a conjecture of A. Frank. This conjecture would have implied a polynomial algorithm for the planar edge-disjoint paths problem. Moreover we derive a complete characterization of all minorclosed classes of graphs for which the disjoint paths problem is polynomially solvable. Finally we show theNP-completeness of the half-integral relaxation of the edge-disjoint paths problem. This implies an answer to the long-standing question whether the edge-disjoint paths problem is polynomially solvable for Eulerian graphs.Supported by Sonderforschungsbereich 303 (DFG)     

Contributions to the relativistic mechanics of continuous media

This is a translation from German of an article originally published inProceedings of the Mathematical-Natural Science Section of the Mainz Academy of Science and Literature, Nr. 11, 1961 (pp. 792–837) (printed by Franz Steiner and Co, Wiesbaden), which is Paper IV in the series Exact Solutions of the Field Equations of General Relativity Theory by Pascual Jordan, Jürgen Ehlers, Wolfgang Kundt and Rainer K. Sachs. The translation has been carried out by G. F. R. Ellis (Department of Applied Mathematics, University of Cape Town), assisted by P. K. S. Dunsby, so that this outstanding review paper can be readily accessible to workers in the field today. As far as possible, the translation has preserved both the spirit and the form of the original paper. Despite its age, it remains one of the best reviews available in this area.     

Generalized Bethe ansatz solution of a one-dimensional asymmetric exclusion process on a ring with blockage

We present a model for a one-dimensional anisotropic exclusion process describing particles moving deterministically on a ring of lengthL with a single defect, across which they move with probability 0 p 1. This model is equivalent to a two-dimensional, six-vertex model in an extreme anisotropic limit with a defect line interpolating between open and periodic boundary conditions. We solve this model with a Bethe ansatz generalized to this kind of boundary condition. We discuss in detail the steady state and derive exact expressions for the currentj, the density profilen(x), and the two-point density correlation function. In the thermodynamic limitL the phase diagram shows three phases, a low-density phase, a coexistence phase, and a high-density phase related to the low-density phase by a particle-hole symmetry. In the low-density phase the density profile decays exponentially with the distance from the boundary to its bulk value on a length scale . On the phase transition line diverges and the currentj approaches its critical valuej _c = p as a power law,j _c – j ^–1/2. In the coexistence phase the width of the interface between the high-density region and the low-density region is proportional toL ^1/2 if the density f 1/2 and=0 independent ofL if = 1/2. The (connected) two-point correlation function turns out to be of a scaling form with a space-dependent amplitude n(x₁, x₂) =A(x₂)A ^Ke^–r/ withr = x ₂ –x ₁ and a critical exponent = 0.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

Chern-Simons theory with finite gauge group

We construct in detail a 2+1 dimensional gauge field theory with finite gauge group. In this case the path integral reduces to a finite sum, so there are no analytic problems with the quantization. The theory was originally introduced by Dijkgraaf and Witten without details. The point of working it out carefully is to focus on the algebraic structure, and particularly the construction of quantum Hilbert spaces on closed surfaces by cutting and pasting. This includes the Verlinde formula. The careful development may serve as a model for dealing with similar issues in more complicated cases.The first author is supported by NSF grant DMS-8805684, an Alfred P. Sloan Research Fellowship, a Presidential Young Investigators award, and by the O'Donnell Foundation. The second author is supported by NSF grant DMS-9207973     

Computer controlled spreading resistance system for measurement of carrier concentration profiles of silicon structures

A new computer controlled equipment for carrier concentration profile determination of silicon structures by a spreading resistance technique is presented. The required data and plots can easily be obtained by means of a new software package, which has been specially developed for this purpose. Measurements have been performed on different structures in order to verify the suitability of both the measuring system and the software package. The reproducibility has been found to be within 5% for the investigated structures.