The local nature of Δ-coloring and its algorithmic applications

Given a connected graphG=(V, E) with |V|=n and maximum degree such thatG is neither a complete graph nor an odd cycle, Brooks' theorem states thatG can be colored with colors. We generalize this as follows: letG-v be -colored; then,v can be colored by considering the vertices in anO(log n) radius aroundv and by recoloring anO(log n) length augmenting path inside it. Using this, we show that -coloringG is reducible inO(log³ n/log) time to (+1)-vertex coloringG in a distributed model of computation. This leads to fast distributed algorithms and a linear-processorNC algorithm for -coloring.A preliminary version of this paper appeared as part of the paper Improved Distributed Algorithms for Coloring and Network Decomposition Problems, in theProceedings of the ACM Symposium on Theory of Computing pages 581–592, 1992. This research was done when the authors were at the Computer Science Department of Cornell University. The research was supported in part by NSF PYI award CCR-89-96272 with matching funds from UPS and Sun Microsystems.     

Isoperimetric inequalities in a boundary value problem on a Riemannian manifold

In this paper the problem u+1=0 in ,u=0 on is considered. Here is a finite domain on a Riemannian manifold and the associated Laplace-Beltrami operator. By means of maximum principles isoperimetric bounds for the maximum ofu and the maximum of the absolute value of the gradient ofu, as well as some related bounds are derived.

---

Zusammenfassung Diese Arbeit behandelt das Problem u+1=0 in ,u=0 auf , wobei ein Gebiet auf einer zweidimensionalen Riemann'schen Mannigfaltigkeit ist, und der zugehörige Laplace-Beltrami Operator. Es werden isoperimetrische Schranken für das Maximum vonu und |u| aus gewissen Maximumsprinzipien hergeleitet, sowie einige verwandte Resultate.

     

Implicit elliptic boundary-value problems with discontinuous nonlinearities

Let be a bounded domain in ⁿ (n3) having a smooth boundary, let be an essentially bounded real-valued function defined on × ^h, and let be a continuous real-valued function defined on a given subset Y of Y ^h. In this paper, the existence of strong solutions u W ^2,p (, ^h) W _o ^1,p (n/2<p<+) to the implicit elliptic equation (–u)=(x,u), with u=(u₁, u₂, ..., u_h) and u=(u ₁, u ₂, ..., u _h), is established. The abstract framework where the problem is placed is that of set-valued analysis.     

Generalization of Gδ*-Diagonals and ωΔ-Spaces

In this paper we introduce the concepts of a quasi-G*-diagonal and quasi--space as generalizations of the concepts of G*-diagonal and -space respectively. It is shown that a quasi-Moore space may be characterized in terms of these concepts. As a consequence we obtain the following metrization theorems: every paracompact -space with quasi-G-diagonal is metrizable and every collectionwise normal quasi--space is metrizable.     

On the distribution of square-full and cube-full integers

LetN _r (x) be the number ofr-full integers x and let _r (x) be the error term in the asymptotic formula forN _r (x). Under Riemann's hypothesis, we prove the estimates ₂(x)x^1/7+, ₃(x)x^97/804+(>0), which improve those of Cao and Nowak. We also investigate the distribution ofr-full andl-free numbers in short intervals (r=2,3). Our results sharpen Krätzel's estimates.     

Groups with the BNB-property

Let G be a group generated by a weak BN-pair in the sense of Delgado-Stellmacher. These amalgams do not determine the group G; in fact G ^*=P _* ¹ *_B P _* ² is infinite. We introduce a global condition which forces G to be finite and makes it possible to determine G. For this we use the associated graph and assume that there exists a circuit admitting an edge-transitive subgroup of G such that any two edges of lie on some conjugate of . It follows that G is a group of Lie type, ² F ₄(2), A ₆ or 3 · S ₆.Dedicated to Professor J. Tits on the occasion of his sixtieth birthdayResearch partially supported by NSF Grant DMS-87 00 838.     

Lattice Polytopes Associated to Certain Demazure Modules of sl n + 1

Let w be an element of the Weyl group of sl _{n + 1}. We prove that for a certain class of elements w (which includes the longest element w₀ of the Weyl group), there exist a lattice polytope R ^l(w) , for each fundamental weight _i of sl _{n + 1}, such that for any dominant weight = _{i = 1} ⁿ a _{i i} , the number of lattice points in the Minkowski sum _w = _{i = 1} ⁿ a _{i i} ^w is equal to the dimension of the Demazure module E _w (). We also define a linear map A ^w : R ^l(w) P _Z R where P denotes the weight lattice, such that char E _w () = e e^–A(x) where the sum runs through the lattice points x of ^w .     

Finite element convergence for singular data

Convergence of the finite element solutionu ^h of the Dirichlet problem u= is proved, where is the Dirac -function (unit impulse). In two dimensions, the Green's function (fundamental solution)u lies outsideH ¹, but we are able to prove that . Since the singularity ofu is logarithmic, we conclude that in two dimensions the function log can be approximated inL ² near the origin by piecewise linear functions with an errorO (h). We also consider the Dirichlet problem u=f, wheref is piecewise smooth but discontinuous along some curve. In this case,u just fails to be inH ^5/2, but as with the approximation to the Green's function, we prove the full rate of convergence:u–u ^h ₁=O (h ^8/2) with, say, piecewise quadratics.     

The self-similar solutions to a fast diffusion equation

A quasilinear equation u -x·u/2+f(u)=0 is studied, wheref(u)=–u+u , > 0, 0<. <1, >1 andx R ⁿ. The equation arises from the study of blow-up self-similar solutions of the heat equation _t =+. We prove the existence and non-existence of ground state for various combination of , and . In particular, we prove that when / < forn=1,2 or / < (n + 2) /(n – 2) forn 3 there exists no non-constant positive radial self-similar solution of the parabolic equation, but for many cases where / > (n + 2)/(n – 2) there exists an infinite number of non-constant positive radial self-similar solutions.     

Leaves in Representation Diagrams of Bipartite Distance-Regular Graphs

Let denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Let ₀ > ₁ ··· > _D denote the eigenvalues of and let q ^h _ij (0 h, i, j D) denote the Krein parameters of . Pick an integer h (1 h D – 1). The representation diagram = _h is an undirected graph with vertices 0,1,...,D. For 0 i, j D, vertices i, j are adjacent in whenever i j and q ^h _ij 0. It turns out that in , the vertex 0 is adjacent to h and no other vertices. Similarly, the vertex D is adjacent to D – h and no other vertices. We call 0, D the trivial vertices of . Let l denote a vertex of . It turns out that l is adjacent to at least one vertex of . We say l is a leaf whenever l is adjacent to exactly one vertex of . We show has a nontrivial leaf if and only if is the disjoint union of two paths.     

Partial Results in Δ 3 0 -Categoricity in Linear Orderings and Boolean Algebras

The notion of ₃ ⁰ -categoricity in linear orderings and Boolean algebras is examined. We provide a proof for the fact that there are uncountably many relatively ₃ ⁰ -categorical linear orderings, and furnish a proof of another fact which suggests that the (unrelatively) ₃ ⁰ -categorical linear orderings may be very difficult to classify. In stark contrast to these results for linear orderings, a complete classification of the relatively ₃ ⁰ -categorical Boolean algebras is given.     

Complementary permutations for abelian groups

Summary LetG be an additively written abelian group and leth: G G be a given function. M. Hall Jr. (1952) and L. Fuchs (1958) already answered the following question. For what functionsh: G G does the functional equation(x) + (x) = h(x) (x G) have as its solution a pair of permutations and ofG? In this paper, we give explicit constructions of such a pair, in a number of cases, in particular whenh(x) x andG is finite. We further determine the finite groupsG where the latter, can be chosen to be automorphisms.In the case whereG is an infinite topological group, we study in how far and can be chosen as Borel measurable permutations, given thath: G G itself is Borel measurable.     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).

     

A degenerate and strongly coupled quasilinear parabolic system not in divergence form

This paper deals with positive solutions of degenerate and strongly coupled quasi-linear parabolic system not in divergence form: u_t=v^p(u+au), v_t=u^q (v+bv) with null Dirichlet boundary condition and positive initial condition, where p, q, a and b are all positive constants, and p, q 1. The local existence of positive classical solution is proved. Moreover, it will be proved that: (i) When min {a, b} ₁ then there exists global positive classical solution, and all positive classical solutions can not blow up in finite time in the meaning of maximum norm (we can not prove the uniqueness result in general); (ii) When min {a, b} > ₁, there is no global positive classical solution (we can not still prove the uniqueness result), if in addition the initial datum (u₀v₀) satisfies u₀ + au₀ 0, v₀+bv₀ 0 in , then the positive classical solution is unique and blows up in finite time, where ₁ is the first eigenvalue of – in with homogeneous Dirichlet boundary condition.This project was supported by PRC grant NSFC 19831060 and 333 Project of JiangSu Province.     

On boundary controllability of a vibrating plate

A vibrating plate is here taken to satisfy the model equation:u _tt + ²u = 0 (where ²u:= (u); = Laplacian) with boundary conditions of the form:u _v = 0 and(u) _v = = control. Thus, the state is the pair [u, u _t] and controllability means existence of on := (0,T)× transfering any[u, u _t]₀ to any[u, u _t]_T. The formulation is given by eigenfunction expansion and duality. The substantive results apply to a rectangular plate. For largeT one has such controllability with = O(T ^–1/2). More surprising is that (based on a harmonic analysis estimate [11]) one has controllability for arbitrarily short times (in contrast to the wave equation:u _tt = u) with log = O(T ^–1) asT0. Some related results on minimum time control are also included.This research was partially supported under the grant AFOSR-82-0271.     

Inequalities in Products of Minors of Totally Nonnegative Matrices

Let _I,I be the minor of a matrix which corresponds to row set I and column set I. We give a characterization of the inequalities of the form _{I,I K,K J,J L,L} which hold for all totally nonnegative matrices. This generalizes a recent result of Fallat, Gekhtman, and Johnson.     

Optimal growth rates for a viscous Hamilton-Jacobi equation

The growth of the L^m-norm, m [1,], of non-negative solutions to the Cauchy problem _t u – u = |u| is studied for non-negative initial data decaying at infinity. More precisely, the function is shown to be bounded from above and from below by positive real numbers. This result indicates an asymptotic behaviour dominated by the hyperbolic Hamilton-Jacobi term of the equation. A one-sided estimate for ln u is also established.     

Groups acting simply transitively on the vertices of a building of typeà 2, II: The casesq=2 andq=3

If (P, L) is a projective plane and is a triangle presentation compatible with a point-line correspondence :P L, then gives rise to a group and a thick building of typeà ₂ on the vertices of which acts simply transitively. We find all triangle presentations (up to natural equivalence) compatible with some point-line correspondence :P L, when (P, L) is the projective plane of orderq=2 orq=3. For some, but not all, of these , is isomorphic to the building associated withG=PGL(3,K) whereK is a local field with discrete valuation and residual field of orderq. We identify the for which this is the case, and in these cases, find embeddings of intoG. We also describe the arithmetic nature of these groups.     

Teichmüller curves in moduli space,Eisenstein series and an application to triangular billiards

Summary There exists a Teichmüller disc _n containing the Riemann surface ofy ²+x ⁿ =1, in the genus [n–1/2] Teichmüller space, such that the stabilizer of _n in the mapping class group has a fundamental domain of finite (Poincaré) volume in _n . Application is given to an asymptotic formula for the length spectrum of the billiard in isosceles triangles with angles (/n, /n,n–2/n) and to the uniform distribution of infinite billiard trajectories in the same triangles.

---

---

Research supported by NSF-DMS-8521620     

Characterizations of Buchsbaum complexes

Letk be a field and an abstract simplicial complex with vertex set . In this article we study the structure of the Ext modules Ext _a ⁱ (A/m _(l ,k[]) of the Stanley-Reisner ringk[] whereA=k[x ₁,...,x _n ] andm _l =(x _l ¹ ,...,x _l ⁿ ). Using this structure theorem we give a characterization of Buchsbaumness ofk[] by means of the length of the modules Ext _A ⁱ (A/m _l ,k[]). That isk[] is Buchsbaum if and only if for allik[], the length of the modules Ext _A ⁱ (A/m _l ,k[]) is independent ofl.