Gauge symmetries and percolation in ±J Ising spin glasses

We consider the ±J spin glass on a finite graph G=(V,E), with i.i.d. couplings. Our approach considers the Z ₂ local gauge invariance of the system. We see the gauge group as a graph theoretic linear code ? over GF(2). The gauge is fixed by choosing a convenient linear supplement of ?. Assuming some relation between the disorder parameter p and the inverse temperature of the thermal bath β _pb , we study percolation in the random interaction random cluster model, and extend the results to dilute spin glasses. Received: 5 May 1997 / Revised version: 9 April 1998     

Uniqueness of solutions of aH ∞ optimization problem and complex geometric convexity

We study uniqueness of an H^∞ optimization problem which is central to the worst case frequency domain system design. It was known that if the so-called sublevel sets are strictly convex inC ^N, then the uniqueness holds. On the other hand, there are examples of non-uniqueness if the sublevel sets are just strictly pseudoconvex. In this paper we prove that uniqueness holds for a type of convexity which is strictly in-between geometric and pseudoconvexity.     

A double arity hierarchy theorem for transitive closure logic

In this paper we prove that thek-ary fragment of transitive closure logic is not contained in the extension of the (k–1)-ary fragment of partial fixed point logic by all (2k–1)-ary generalized quantifiers. As a consequence, the arity hierarchies of all the familiar forms of fixed point logic are strict simultaneously with respect to the arity of the induction predicates and the arity of generalized quantifiers.Although it is known that our theorem cannot be extended to the sublogic deterministic transitive closure logic, we show that an extension is possible when we close this logic under congruence.Supported by a grant from the University of Helsinki. This research was initiated while he was a Junior Researcher at the Academy of FinlandThis article was processed by the author using the LATEX style filepljourlm from Springer-Verlag.     

Necessary conditions for normed convergence of critical multitype Bienaymé-Galton-Watson processes without variance

The condition on the offspring distribution in the critical multitype Bienaymé-Galton-Watson process without variance, which was previously shown to be sufficient for the existence of the analogue of the exponential limit law, is now shown also to be necessary. This completely extends previous one-type work of R. S. Slack.     

On the time dependent behaviour of the truncated birth-death process

Conditions are obtained for the truncated birth-death process to be stochastically monotone in the long run.     

On the connectedness of self-affine attractors

Let T = T(A, D) be a self-affine attractor in defined by an integral expanding matrix A and a digit set D. In the first part of this paper, in connection with canonical number systems, we study connectedness of T when D corresponds to the set of consecutive integers . It is shown that in and , for any integral expanding matrix A, T(A, D) is connected. In the second part, we study connectedness of Pisot dual tiles, which play an important role in the study of -expansions, substitutions and symbolic dynamical systems. It is shown that each tile of the dual tiling generated by a Pisot unit of degree 3 is arcwise connected. This is naturally expected since the digit set consists of consecutive integers as above. However surprisingly, we found families of disconnected Pisot dual tiles of degree 4. We even give a simple necessary and sufficient condition of connectedness of the Pisot dual tiles of degree 4. Detailed proofs will be given in [4]. Received: 2 March 2003     

Synthesis of o-phenylphenol from cyclohexanone over platinum supported on calcined Mg/Al hydrotalcite

A kinetic model is proposed to account for the effect of oxygen during catalyst premodification on the rate and enantioselectivity in hydrogenation of methyl pyruvate over cinchonidine modified platinum catalysts.This revised version was published online in December 2005 with corrections to the Cover Date.     

On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

The Diameter of a Scale-Free Random Graph

We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabási and Albert [3], as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabási, Albert and Jeong [1,5] and heuristic arguments given by Newman, Strogatz and Watts [23] suggest that after n steps the resulting graph should have diameter approximately logn. We show that while this holds for m=1, for m2 the diameter is asymptotically log n/log logn.* Research supported in part by NSF grant no. DSM9971788     

Triangle Factors In Sparse Pseudo-Random Graphs

The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second eigenvalue of a d-regular graph G on 3n vertices is at most cd ³/n ² log n, for some sufficiently small constant c > 0, then G contains a triangle factor. We also show that a fractional triangle factor already exists if < 0.1d ²/n. The latter result is seen to be best possible up to a constant factor, for various values of the degree d = d(n).* Supported by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation and by a Bergmann Memorial Award. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich.