The second twisted Betti number and the convergence of collapsing Riemannian manifolds

Let M _i X denote a sequence of n-manifolds converging to a compact metric space, X, in the Gromov-Hausdorff topology such that the sectional curvature is bounded in absolute value and dim(X)<n. We prove the following stability result: If the fundamental groups of M _i are torsion groups of uniformly bounded exponents and the second twisted Betti numbers of M _i vanish, then there is a manifold, M, and a sequence of diffeomorphisms from M to a subsequence of {M _i } such that the distance functions of the pullback metrics converge to a pseudo-metric in C ⁰-norm. Furthermore, M admits a foliation with leaves diffeomorphic to flat manifolds (not necessarily compact) such that a vector is tangent to a leaf if and only if its norm converges to zero with respect to the pullback metrics. These results lead to a few interesting applications. Oblatum 17-I-2002 & 27-II-2002?Published online: 29 April 2002     

The computational complexity of basic decision problems in 3-dimensional topology

We study the computational complexity of basic decision problems of 3-dimensional topology, such as to determine whether a triangulated 3-manifold is irreducible, prime, ∂-irreducible, or homeomorphic to a given 3-manifold M. For example, we prove that the problem to recognize whether a triangulated 3-manifold is homeomorphic to a 3-sphere, or to a 2-sphere bundle over a circle, or to a real projective 3-space, or to a handlebody of genus g, is decidable in nondeterministic polynomial time (NP) of size of the triangulation. We also show that the problem to determine whether a triangulated orientable 3-manifold is irreducible (or prime) is in PSPACE and whether it is ∂-irreducible is in coNP. The proofs improve and extend arguments of prior author’s article on the recognition problem for the 3-sphere.      

Ideals in Graph Algebras

We show that the graph construction used to prove that a gauge-invariant ideal of a graph C ^???-algebra is isomorphic to a graph C ^???-algebra, and also used to prove that a graded ideal of a Leavitt path algebra is isomorphic to a Leavitt path algebra, is incorrect as stated in the literature. We give a new graph construction to remedy this problem, and prove that it can be used to realize a gauge-invariant ideal (respectively, a graded ideal) as a graph C ^???-algebra (respectively, a Leavitt path algebra).     

Buckling of an axisymmetric vesicle under compression: the effects of resistance to shear

We consider the axisymmetric deformation of an initially spherical,porous vesicle with incompressible membrane having finite resistanceto in-plane shearing, as the vesicle is compressed between parallelplates. We adopt a thin-shell balance-of-forces formulationin which the mechanical properties of the membrane are describedby a single dimensionless parameter, C, which is the ratio ofthe membrane's resistance to shearing to its resistance to bending.This results in a novel free-boundary problem which we solvenumerically to obtain vesicle shapes as a function of plateseparation, h. For small deformations, the vesicle contactseach plate over a small circular area. At a critical value ofplate separation, h_TC, there is a transcritical bifurcationfrom which a new branch of solutions emerges, representing buckledvesicles which contact each plate along a circular curve. Forthe values of C investigated, we find that the transcriticalbifurcation is subcritical and that there is a further saddle-nodebifurcation (fold) along the branch of buckled solutions ath = h_SN (where h_SN > h_TC). The resulting bifurcation structureis commensurate with a hysteresis loop in which a sudden transitionfrom an unbuckled solution to a buckled one occurs as h is decreasedthrough h_TC and a further sudden transition, this time froma buckled solution to an unbuckled one, occurs as h is increasedthrough h_SN. We find that h_SN and h_TC increase with C, thatis, vesicles that resist shear are more prone to buckling.     

On Simple Polygonalizations with Optimal Area

We discuss the problem of finding a simple polygonalization for a given set of vertices P that has optimal area. We show that these problems are very closely related to problems of optimizing the number of points from a set Q in a simple polygon with vertex set P and prove that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a given vertex set, resulting in a proof of NP-completeness for the corresponding area optimization problems. This answers a generalization of a question stated by Suri in 1989. Finally, we turn to higher dimensions, where we prove that, for 1 k d , 2 d , it is NP-hard to determine the smallest possible total volume of the k -dimensional faces of a d -dimensional simple nondegenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980. Received June 26, 1997, and in revised form February 13, 1999, and May 19, 1999.     

Itô’s excursion theory and random trees

We explain how Itô’s excursion theory can be used to understand the asymptotic behavior of large random trees. We provide precise statements showing that the rescaled contour of a large Galton–Watson tree is asymptotically distributed according to Itô’s excursion measure. As an application, we provide a simple derivation of Aldous’ theorem stating that the rescaled contour function of a Galton–Watson tree conditioned to have a fixed large progeny converges to a normalized Brownian excursion. We also establish a similar result for a Galton–Watson tree conditioned to have a fixed large height.     

On the composition of derivations

Posner ([9]) has shown that for any prime ringR of characteristic different from 2 the composition of any two non-zero derivations is not a derivation. On the other hand, it is well known ([4]) that if charR=n for a prime numbern andd is a derivation ofR, thend ⁿ is also a derivation. Our main objective is to extend the above mentioned result of Posner in the case of commutative domains, and to apply this results to the investigation of connections either between derivations and a center, or between derivations and a generalized centroid of a prime ring. For this purpose, we are first going to introduce a method of notation for the composition of derivations which, we hope, will also be useful in other situations.     

Delta-shocks and vacuum states in the vanishing pressure limit of solutions to the isentropic Euler equations for modified Chaplygin gas

The phenomena of concentration and cavitation and the formation of δ-shocks and vacuum states in solutions to the isentropic Euler equations for a modified Chaplygin gas are analyzed as the double parameter pressure vanishes. Firstly, the Riemann problem of the isentropic Euler equations for a modified Chaplygin gas is solved analytically. Secondly, it is rigorously shown that, as the pressure vanishes, any two-shock Riemann solution to the isentropic Euler equations for a modified Chaplygin gas tends to a δ-shock solution to the transport equations, and the intermediate density between the two shocks tends to a weighted δ-measure that forms the δ-shock; any two-rarefaction-wave Riemann solution to the isentropic Euler equations for a modified Chaplygin gas tends to a two-contact-discontinuity solution to the transport equations, the nonvacuum intermediate state between the two rarefaction waves tends to a vacuum state. Finally, some numerical results exhibiting the formation of δ-shocks and vacuum states are presented as the pressure decreases.     

Ring structures on groups of arithmetic functions

Using the theory of Witt vectors, we define ring structures on several well-known groups of arithmetic functions, which in another guise are formal Dirichlet series. The set of multiplicative arithmetic functions over a commutative ring R is shown to have a unique functorial ring structure for which the operation of addition is Dirichlet convolution and the operation of multiplication restricted to the completely multiplicative functions coincides with point-wise multiplication. The group of additive arithmetic functions over R also has a functorial ring structure. In analogy with the ghost homomorphism of Witt vectors, there is a functorial ring homomorphism from the ring of multiplicative functions to the ring of additive functions that is an isomorphism if R is a Q-algebra. The group of rational arithmetic functions, that is, the group generated by the completely multiplicative functions, forms a subring of the ring of multiplicative functions. The latter ring has the structure of a Bin(R)-algebra, where Bin(R) is the universal binomial ring equipped with a ring homomorphism to R. We use this algebra structure to study the order of a rational arithmetic function, as well the powersfα for α∈Bin(R) of a multiplicative arithmetic function f. For example, we prove new results about the powers of a given multiplicative arithmetic function that are rational. Finally, we apply our theory to the study of the zeta function of a scheme of finite type over Z.     

Regular orbits in powers of permutation representations

Let (Q,G) be a faithful permutation representation of a finite group G. Suppose that the G-set Q has t distinct non-zero marks. In a permutation representation analogue of a theorem of Brauer on linear representations, it is shown that the direct power (Q,G)^t of (Q,G) contains a regular orbit. As a corollary, the probability that a random element of Q^r lies in a regular orbit of (Q,G)^r is shown to tend to 1 exponentially fast as r tends to \infin\infin. Further, knowledge of the rate of convergence is equivalent to knowledge of the second largest value of the character of the linear permutation representation.     

Uniqueness cases in odd-type groups of finite Morley rank

There is a longstanding conjecture, due to Gregory Cherlin andBoris Zilber, that all simple groups of finite Morley rank aresimple algebraic groups. One of the major theorems in the areais Borovik's trichotomy theorem. The ‘trichotomy’here is a case division of the generic minimal counterexampleswithin odd type, that is, groups with a large and divisibleSylow° 2-subgroup. The so-called ‘uniqueness case’in the trichotomy theorem is the existence of a proper 2-generatedcore. It is our aim to drive the presence of a proper 2-generatedcore to a contradiction, and hence bind the complexity of theSylow° 2-subgroup of a minimal counterexample to the Cherlin–Zilberconjecture. This paper shows that the group in question is aminimal connected simple group and has a strongly embedded subgroup,a far stronger uniqueness case. As a corollary, a tame counterexampleto the Cherlin–Zilber conjecture has Prüfer rankat most two.     

Approximation algorithms for scheduling unrelated parallel machines

We consider the following scheduling problem. There arem parallel machines andn independent jobs. Each job is to be assigned to one of the machines. The processing of jobj on machinei requires timep _ij . The objective is to find a schedule that minimizes the makespan.Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints.In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unlessP = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.A preliminary version of this paper appeared in theProceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science (Computer Society Press of the IEEE, Washington, D.C., 1987) pp. 217–224.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

On connected dominating sets of restricted diameter

A connected dominating set (CDS) is commonly used to model a virtual backbone of a wireless network. To bound the distance that information must travel through the network, we explicitly restrict the diameter of a CDS to be no more than s leading to the concept of a dominating s-club. We prove that for any fixed positive integer s it is NP-complete to determine if a graph has a dominating s  -club, even when the graph has diameter s+1$s+1$. As a special case it is NP-complete to determine if a graph of diameter two has a dominating clique. We then propose a compact integer programming formulation for the related minimization problem, enhance the approach with variable fixing rules and valid inequalities, and present computational results.     

Pseudo-holomorphic maps and bubble trees

This paper proves a strong convergence theorem for sequences of pseudo-holomorphic maps from a Riemann surface to a symplectic manifoldN with tamed almost complex structure. (These are the objects used by Gromov to define his symplectic invariants.) The paper begins by developing some analytic facts about such maps, including a simple new isoperimetric inequality and a new removable singularity theorem. The main technique is a general procedure for renormalizing sequences of maps to obtain “bubbles on bubbles.” This is a significant step beyond the standard renormalization procedure of Sacks and Uhlenbeck. The renormalized maps give rise to a sequence of maps from a “bubble tree”—a map from a wedge Σ V S² V S² V ... →N. The main result is that the images of these renormalized maps converge in L^1,2 ∪C° to the image of a limiting pseudo-holomorphic map from the bubble tree. This implies several important properties of the bubble tree. In particular, the images of consecutive bubbles in the bubble tree intersect, and if a sequence of maps represents a homology class then the limiting map represents this class.     

Perverse coherent sheaves and the geometry of special pieces in the unipotent variety

Let X be a scheme of finite type over a Noetherian base scheme S admitting a dualizing complex, and let U⊂X be an open set whose complement has codimension at least 2. We extend the Deligne-Bezrukavnikov theory of perverse coherent sheaves by showing that a coherent intermediate extension (or intersection cohomology) functor from perverse sheaves on U to perverse sheaves on X may be defined for a much broader class of perversities than has previously been known. We also introduce a derived category version of the coherent intermediate extension functor.Under suitable hypotheses, we introduce a construction (called “S₂-extension”) in terms of perverse coherent sheaves of algebras on X that takes a finite morphism to U and extends it in a canonical way to a finite morphism to X. In particular, this construction gives a canonical “S₂-ification” of appropriate X. The construction also has applications to the “Macaulayfication” problem, and it is particularly well-behaved when X is Gorenstein.Our main goal, however, is to address a conjecture of Lusztig on the geometry of special pieces (certain subvarieties of the unipotent variety of a reductive algebraic group). The conjecture asserts in part that each special piece is the quotient of some variety (previously unknown for the exceptional groups and in positive characteristic) by the action of a certain finite group. We use S₂-extension to give a uniform construction of the desired variety.     

Full Ideals

Contractedness of 𝔪-primary integrally closed ideals played a central role in the development of Zariski's theory of integrally closed ideals in two-dimensional regular local rings (R, 𝔪). In such rings, the contracted 𝔪-primary ideals are known to be characterized by the property that I: 𝔪 = I: x for some x ∈ 𝔪 ?𝔪². We call the ideals with this property full ideals and compare this class of ideals with the classes of 𝔪-full ideals, basically full ideals, and contracted ideals in higher dimensional regular local rings. The 𝔪-full ideals are easily seen to be full. In this article, we find a sufficient condition for a full ideal to be 𝔪-full. We also show the equivalence of the properties full, 𝔪-full, contracted, integrally closed, and normal, for the class of parameter ideals. We then find a sufficient condition for a basically full parameter ideal to be full.     

Numerical study of the transition to chaos of a buoyant plume from a two-dimensional open cavity heated from below

The transition to a chaotic plume from a two-dimensional (2D) open cavity heated from below has been investigated using numerical simulation. A large range of Rayleigh numbers (Ra) pertaining to an aspect ratio of A = 1, and Prandtl number (Pr) of Pr = 0.71 (air) is numerically investigated. It is shown that there exists a complex transition of the plume from a steady reflection symmetry to a chaotic flow with a sequence of bifurcations. As the Rayleigh number increases, the plume from the open cavity undergoes a supercritical pitchfork bifurcation from a steady reflection symmetry to a steady reflection asymmetry flow. Once the Rayleigh number exceeds 7 × 10³, the plume appears as a distinct flapping namely, a Hopf bifurcation, and then as a distinct puffing. The chaotic plume has the possibility to exhibit an alternate appearance of flapping and puffing in the event the Rayleigh number exceeds 8 × 10⁴. Moreover, the dynamics of the plume from the open cavity is discussed, and the dependence on the Rayleigh number of heat and mass transfer of the plume from the open cavity is quantified.     

Tambarization of a Mackey functor and its application to the Witt–Burnside construction

For an arbitrary group G, a (semi-)Mackey functor is a pair of covariant and contravariant functors from the category of G-sets, and is regarded as a G-bivariant analog of a commutative (semi-)group. In this view, a G-bivariant analog of a (semi-)ring should be a (semi-)Tambara functor. A Tambara functor is firstly defined by Tambara, which he called a TNR-functor, when G is finite. As shown by Brun, a Tambara functor plays a natural role in the Witt–Burnside construction.It will be a natural question if there exist sufficiently many examples of Tambara functors, compared to the wide range of Mackey functors. In the first part of this article, we give a general construction of a Tambara functor from any Mackey functor, on an arbitrary group G. In fact, we construct a functor from the category of semi-Mackey functors to the category of Tambara functors. This functor gives a left adjoint to the forgetful functor, and can be regarded as a G-bivariant analog of the monoid-ring functor.In the latter part, when G is finite, we investigate relations with other Mackey-functorial constructions — crossed Burnside ring, Elliott?s ring of G-strings, Jacobson?s F-Burnside ring — all these lead to the study of the Witt–Burnside construction.     

On Mixed Error Estimates for Elliptic Obstacle Problems

We establish in this paper sharp error estimates of residual type for finite element approximation to elliptic obstacle problems. The estimates are of mixed nature, which are neither of a pure a priori form nor of a pure a posteriori form but instead they are combined by an a priori part and an a posteriori part. The key ingredient in our derivation for the mixed error estimates is the use of a new interpolator which enables us to eliminate inactive data from the error estimators. One application of our mixed error estimates is to construct a posteriori error indicators reliable and efficient up to higher order terms, and these indicators are useful in mesh-refinements and adaptive grid generations. In particular, by approximating the a priori part with some a posteriori quantities we can successfully track the free boundary for elliptic obstacle problems.