Colouring a graph frugally

We prove that any graph with maximum degree sufficiently large, has a proper vertex colouring using +1 colours such that each colour class appears at most log⁸ times in the neighbourhood of any vertex. We also show that for 1, the minimum number of colours required to colour any such graph so that each vertex appears at most times in the neighbourhood of any vertex is (+^1+1//), showing in particular that when =log/loglog, such a colouring cannot always be achieved with O() colours. We also provide a polynomial time algorithm to find such a colouring. This has applications to the total chromatic number of a graph.The second two authors were supported by NATO Collaborative Research Grant #CRG950235.     

Composition operators from large weighted Hardy spaces into the Dirichlet space

Given a large weighted Hardy space we show there exists a composition operatorC with that maps from that space into the unweighted Dirichlet space and lies in every Schatten p-class for 0<p<. This is in contrast to the situation in which the image space is a smaller weighted Dirichlet space. It is known that in that case it is not possible to find such a composition operator that is bounded.This research was supported in part by a summer stipend from Bellarmine College.     

Flow equivalence and stochastic equivalence in G-networks

G-networks are novel product form queuing networks that, in addition to ordinary customers, contain unusual entities such as negative customers which eliminate normal customers, and triggers that move other customers from some queue to another. Recently we introduced one more special type of customer, a reset, which may be sent out by any server at the end of a service epoch, and that will reset the queue to which it arrives into its steady state when that queue is empty. A reset which arrives to a non-empty queue has no effect at all. The sample paths of a system with resets is significantly different from that of a system without resets, because the arrival of a reset to an empty queue will provoke a finite positive jump in queue length which may be arbitrarily large, while without resets positive jumps are only of size + 1 and they occur only when a positive customer arrives to a queue. In this paper we review this novel model, and then discuss its traffic equations. We introduce the concept of stationary equivalence for queueing models, and of flow equivalence for distinct queueing models. We show that the flow equivalence of two G-networks implies that they are also stationary equivalent. We then show that the stationary probability distribution of a G-network with resets is identical to that of a G-network without resets whose transition probabilities for positive (ordinary) customers has been increased in a specific manner. Our results show that a G-network with resets has the same form of traffic equations and the same joint stationary probability distribution of queue length as that of a G-network without resets.     

Improvement of the Nash-Tognoli theorem

Let be a smooth closed manifold in ⁿ. The Nash-Tognoli theorem says that M can be arbitrarily well approximated (in the C^r-topology with r < ) in ⁿ by a nonsingular real algebraic set under the condition that dim <(n-1)/2 There is a familiar conjecture, going back at least to Nash, that the restriction on dim in the Nash-Tognoli theorem is unnecessary. However, up to now in unstable dimensions [i.e., for dim (n-1)/2 ] the possibility of approximating was known only for orientable of codimension (in ⁿ) 1 or 2. The goal of the paper is to prove the following theorem, relaxing the restriction on dim in the Nash-Tognoli theorem to dim M<(2n-1)/3. If is a smooth closed manifold in IK and dim M<(2n–1)/3, then can be arbitrarily well approximated in ⁿ by a nonsingular real algebraic set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 122, pp. 66–71, 1982.     

Superrigidity of lattices in solvable Lie groups

Summary Let be a closed, cocompact subgroup of a simply connected, solvable Lie groupG, such that Ad _G has the same Zariski closure as AdG. If : GL _n () is any finite-dimensional representation of , we show that virtually extends to a representation ofG. (By combining this with work of Margulis on lattices in semisimple groups, we obtain a similar result for lattices in many groups that are neither solvable nor semisimple.) Furthermore, we show that if is isomorphic to a closed, cocompact subgroup of another simply connected, solvable Lie groupG, then any isomorphism from to extends to a crossed isomorphism fromG toG. In the same vein, we prove a more concrete form of Mostow's theorem that compact solvmanifolds with isomorphic fundamental groups are diffeomorphic.Oblatum 5-VII-1994 & 15-IV-1995     

Spatial dynamics of time periodic solutions for the Ginzburg-Landau equation

We consider the dynamics of the Ginzburg-Landau equation in a small neighborhood of a known pulse solution by studying a Poincaré map,P: _{T T} , where _T is a section which is transverse to the pulse. Due to the fact that the Ginzburg-Landau equation possesses both a rotational symmetry and a spatial symmetry, we are able to conduct a detailed analytical study of this map in neighborhoods arbitrarily close to the pulse solution. Thus, we are able to complement the work of Holmes [8], who conducted an analytical study of the Poincaré map in a punctured neighborhood of the pulse. We find that the Poincaré map contains an invariant set _itT, where is not necessarily a Cantor set of points, such thatP: is homeomorphic to a shift map on (at least) two symbols. Furthermore, we find that for eachm 1 the mapP _itm possesses a fixed point. Since is not necessarily a Cantor set, this is not immediately clear. Finally, we find that when the pulse solution is broken, for eachm1 there exist parameter values such that pulses possessingm maxima appear.On leave at the University of Utah during 1993/94. Supported by the DFG, Habilitationsstipendium Ma 1587/1-1.     

Reflecting stationary sets and successors of singular cardinals

REF is the statement that every stationary subset of a cardinal reflects, unless it fails to do so for a trivial reason. The main theorem, presented in Sect. 0, is that under suitable assumptions it is consistent that REF and there is a which is ⁺ⁿ -supercompact. The main concepts defined in Sect. 1 are PT, which is a certain statement about the existence of transversals, and the bad stationary set. It is shown that supercompactness (and even the failure of PT) implies the existence of non-reflecting stationary sets. E.g., if REF then for many PT(, ₁). In Sect. 2 it is shown that Easton-support iteration of suitable Levy collapses yield a universe with REF if for every singular which is a limit of supercompacts the bad stationary set concentrates on the right cofinalities. In Sect. 3 the use of oracle c.c. (and oracle proper—see [Sh-b, Chap. IV] and [Sh 100, Sect. 4]) is adapted to replacing the diamond by the Laver diamond. Using this, a universe as needed in Sect. 2 is forced, where one starts, and ends, with a universe with a proper class of supercompacts. In Sect. 4 bad sets are handled in ZFC. For a regular {<⁺ : cf<} is good. It is proved in ZFC that if=cf>₁ then {<⁺ : cf<} is the union of sets on which there are squares.     

Some special results on convergent sequences of radon measures

Two problems will be considered. In Part I we consider a class of subsets of a topological space X and a Radon measure on X; if it is known that, for sufficiently many , the restrictions of the sets in constitutes a uniformity class in T w.r.t. the restriction of the given measure, then we ask if it follows that is a uniformity class in X.Part II, which can be read independently of Part I, is concerned with the question whether, to a given convergent sequence of Radon measures, say _n, there always exist sufficiently many compact sets K such that _n(K)(K).     

Descendants constructed from matter field in Landau-Ginzburg theories coupled to topological gravity

It is argued that gravitational descendants in the theory of topological gravity coupled to topological Landau-Ginzburg theory (not necessarily conformal) can be constructed from matter fields alone (without metric fields and ghosts). In this sense topological gravity is induced. We discuss the mechanism of this effect (that turns out to be connected with K. Saito's higher residue pairing: Kⁱ(_i(₁),₂)=K⁰(₁,₂)), and demonstrate how it works in a simplest nontrivial example: correlator on a sphere with four marked points. We also discuss some results on k-point correlators on a sphere. From the idea of induced topological gravity it follows that the theory of pure topological gravity (without topological matter) is equivalent to the trivial Landau-Ginzburg theory (with quadratic superpotential).Published in Teoreticheskaya i Matematicheskaya Fizika, Vol. 95, No. 2, pp. 307–316, May, 1993.     

Über einen Typ von injektiven Klassen

If u is a morphism, A an object of some category, we say, A is injective relative to u, iff Hom (u, A) is epi. In this paper we consider classesU of monomorphisms in categories of modules with the following property: if u, u are monos, such that uu exists and is inU, then u is inU. We show, that the closure a(U) ofU is an injective class in the sence of S. Eilenberg and J. C. Moore, that is, for each module A there is a mono a:AB, such that B is injective relative to u for all uU and that each module C, that is injective relative to u for all uU is injective relative to a.     

Bochner-Kähler metrics

A Kähler metric is said to be Bochner-Kähler if its Bochner curvature vanishes. This is a nontrivial condition when the complex dimension of the underlying manifold is at least . In this article it will be shown that, in a certain well-defined sense, the space of Bochner-Kähler metrics in complex dimension has real dimension and a recipe for an explicit formula for any Bochner-Kähler metric will be given.

It is shown that any Bochner-Kähler metric in complex dimension  has local (real) cohomogeneity at most . The Bochner-Kähler metrics that can be `analytically continued' to a complete metric, free of singularities, are identified. In particular, it is shown that the only compact Bochner-Kähler manifolds are the discrete quotients of the known symmetric examples. However, there are compact Bochner-Kähler orbifolds that are not locally symmetric. In fact, every weighted projective space carries a Bochner-Kähler metric.

The fundamental technique is to construct a canonical infinitesimal torus action on a Bochner-Kähler metric whose associated momentum mapping has the orbits of its symmetry pseudo-groupoid as fibers.

     

Constructing the Kähler and the symplectic structures from certain spinors on 4-manifolds

We show that, on an oriented Riemannian 4-manifold, existence of a non-zero parallel spinor with respect to a spin structure implies that the underlying smooth manifold admits a Kähler structure. A similar but weaker condition is obtained for the 4-manifold to admit a symplectic structure. We also show that the structure in which the non-zero parallel spinor lives is equivalent to the canonical spin structure associated to the Kähler structure.

     

Convergence of the Marcus–Lushnikov Process

The Smoluchowski coagulation equation describes the concentration c(t,x) of particles of mass x [ 0,] at the instant t 0, in an infinite system of coalescing particles. It is well-known that in some cases, gelation occurs: a particle with infinite mass appears. But this infinite particle is inert, in the sense that it does not interact with finite particles. We consider the so-called Marcus–Lushnikov process, which is a stochastic finite system of coalescing particles. This process is expected to converge, as the number of particles tends to infinity, to a solution of the Smoluchowski coagulation equation. We show that it actually converges, for t [0,], to a modified Smoluchowski equation, which takes into account a possible interaction between finite and infinite particles.     

Strong local homogeneity and coset spaces

We prove that for every homogeneous and strongly locally homogeneous separable metrizable space there is a metrizable compactification of such that, among other things, for all there is a homeomorphism such that . This implies that is a coset space of some separable metrizable topological group .

     

The canonical solution operator to restricted to Bergman spaces

We first show that the canonical solution operator to restricted to -forms with holomorphic coefficients can be expressed by an integral operator using the Bergman kernel. This result is used to prove that in the case of the unit disc in the canonical solution operator to restricted to -forms with holomorphic coefficients is a Hilbert-Schmidt operator. In the sequel we give a direct proof of the last statement using orthonormal bases and show that in the case of the polydisc and the unit ball in 1,$"> the corresponding operator fails to be a Hilbert-Schmidt operator. We also indicate a connection with the theory of Hankel operators.

     

Boundedness of operators on Hardy spaces via atomic decompositions

An example of a linear functional defined on a dense subspace of the Hardy space is constructed. It is shown that despite the fact that this functional is uniformly bounded on all atoms, it does not extend to a bounded functional on the whole . Therefore, this shows that in general it is not enough to verify that an operator or a functional is bounded on atoms to conclude that it extends boundedly to the whole space. The construction is based on the fact due to Y. Meyer which states that quasi-norms corresponding to finite and infinite atomic decompositions in , , are not equivalent.

     

Fine Densities for Excessive Measures and the Revuz Correspondence

Suppose that U is the resolvent of a Borel right process on a Lusin space X. If is a U-excessive measure on X then we show by analytical methods that for every U-excessive measure with the Radon–Nikodym derivative d/d possesses a finely continuous version. (Fitzsimmons and Fitzsimmons and Getoor gave a probabilistic approach for this result.) We extend essentially a technique initiated by Mokobodzki and deepened by Feyel. The result allows us to establish a Revuz type formula involving the fine versions, and to study the Revuz correspondence between the -finite measures charging no set that is both -polar and -negligible (U being the potential component of ) and the strongly supermedian kernels on X. This is an analytic version of a result of Azéma, Fitzsimmons and Dellacherie, Maisonneuve and Meyer, in terms of additive functionals or homogeneous random measures. Finally we give an application to the context of the semi-Dirichlet forms, covering a recent result of Fitzsimmons.     

A Computer-Assisted Proof of the Uniqueness of the Perkel Graph

The Perkel graph is a distance-regular graph of order 57, degree 6 and diameter 3, with intersection array (6, 5, 2; 1, 1, 3). We describe a computer assisted proof that every graph with this intersection array is isomorphic to the Perkel graph. The computer proof relies heavily on the fact that the minimal idempotents for , and their submatrices, are positive semidefinite.To minimize the risk of computer errors we have used two different methods to establish the same theorem and as an added precaution large parts of the corresponding programs were written by different authors.The first method generates plausible subgraphs induced by all vertices at distance 3 from a fixed vertex of and then tries to extend each of the generated graphs to a full graph with the given intersection array.The second method generates possible neighborhoods for a pentagon in . It turns out that every such pentagon can be extended to a Petersen graph in . We then prove mathematically that there is, up to isomorphism, only a single graph with this property.     

Control discipline necessity: Making the language as general as the implementation

The formal verification of control structure implementation techniques is a subject receiving increased attention among programming language researchers. Such correctness arguments relate source language control semantics to corresponding implementation effects. Most commonly, it is demonstrated that a particular implementation strategy is safe is some source language control discipline is observed. We term this asufficiency proof for with given . In this paper, the companion issue of thenecessity of is explored. That is, we consider the question of whether some more liberal discipline might also be sufficient for . The motivation is the observation that language designers often have particular control implementation strategies in minda priori, but at times over-restrict their final designs to ensure that the envisioned implementation remains applicable. The general notion of control discipline necessity proofs is illustrated by a proof that Wang and Dahl's CS condition on block-structured coroutines is necessary, given a simple scope-based deletion strategy, but that their CR condition is not necessary unless scope-based referencing constraints are taken into account.Work supported in part by the National Science Foundation under grant MCS-79-06102 to the University of Pittsburgh.     

On weak convergence to Brownian motion

Summary We consider a minimal form of the usual conditions for the dependent central limit theorem and invariance principle for near martingales. We show that these conditions imply convergence to Brownian motion in a way that is slightly stronger than weak convergence in D[0,). On the other hand, if a sequence of processes with paths in D[0,) converges to Brownian motion in this way, then we can always find a sequence of partitions of the time axis that is such that these conditions hold for the corresponding array of increments.