Associated primes and cofiniteness of local cohomology modules

Let be an ideal of Noetherian ring R and let s be a non-negative integer. Let M be an R-module such that is finite R-module. If s is the first integer such that the local cohomology module is non -cofinite, then we show that is finite. In particular, the set of associated primes of is finite. Let be a local Noetherian ring and let M be a finite R-module. We study the last integer n such that the local cohomology module is not -cofinite and show that n just depends on the support of M.The research of the first author was supported in part by a grant from IPM (No. 83130114).The second author was supported by a grant from University of Tehran (No. 6103023/1/01).     

The feasibility pump

In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{c^Tx:Ax≥b,x_j integer ∀j ∈ }. Trivially, a feasible solution can be defined as a point x* ∈ P:={x:Ax≥b} that is equal to its rounding , where the rounded point is defined by := x*_j if j ∈ and := x*_j otherwise, and [·] represents scalar rounding to the nearest integer. Replacing “equal” with “as close as possible” relative to a suitable distance function Δ(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.     

Optimal 3-terminal cuts and linear programming

Given an undirected graph G=(V,E) and three specified terminal nodes t ₁,t ₂,t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c _e is specified for each e∈E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is -hard, and in fact, is max- -hard. An approximation algorithm having performance guarantee has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most times the optimal LP value. It is proved here that can be improved to , and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee . In addition, we show that is best possible for this algorithm. Research of this author was supported by NSERC PGSB. Research supported by a grant from NSERC of Canada.     

Greedy splitting algorithms for approximating multiway partition problems

Given a system (V,T,f,k), where V is a finite set, is a submodular function and k2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition ={V₁,V₂,...,V_k} of V that satisfiesfor all i and minimizes f(V₁)+f(V₂)+···+f(V_k), where is a k-partition of hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.Mathematics Subject Classification (1991): 20E28, 20G40, 20C20Acknowledgement This research is partially supported by the Scientific Grant-in-Aid from Ministry of Education, Science, Sports and Culture of Japan. The authors would like to thank the anonymous referees for their valuable comments and suggestions.     

The volumetric barrier for convex quadratic constraints

Let where and _i is an n×n positive semidefinite matrix. We prove that the volumetric and combined volumetric-logarithmic barriers for are and self-concordant, respectively. Our analysis uses the semidefinite programming (SDP) representation for the convex quadratic constraints defining , and our earlier results on the volumetric barrier for SDP. The self-concordance results actually hold for a class of SDP problems more general than those corresponding to the SDP representation of .Mathematics Subject Classification (1991):90C25, 90C30     

Fast convolution with radial kernels at nonequispaced knots

Summary. We develop a new algorithm for the fast evaluation of linear combinations of radial functions based on the recently developed fast Fourier transform at nonequispaced knots. For smooth kernels, e.g. the Gaussian, our algorithm requires arithmetic operations. In case of singular kernels an additional regularization procedure must be incorporated and the algorithm has the arithmetic complexity if either the points y_j or the points x_k are reasonably uniformly distributed. We prove error estimates to obtain clues about the choice of the involved parameters and present numerical examples for various singular and smooth kernels in two dimensions.Mathematics Subject Classification (2000): 65T40, 65T50, 65F30Revised version received December 3, 2003     

Topologically transitive extensions of bounded operators

Let X be any Banach space and T a bounded operator on X. An extension of the pair (X,T) consists of a Banach space in which X embeds isometrically through an isometry i and a bounded operator on such that When X is separable, it is additionally required that be separable. We say that is a topologically transitive extension of (X, T) when is topologically transitive on , i.e. for every pair of non-empty open subsets of there exists an integer n such that is non-empty. We show that any such pair (X,T) admits a topologically transitive extension , and that when H is a Hilbert space, (H,T) admits a topologically transitive extension where is also a Hilbert space. We show that these extensions are indeed chaotic.Mathematics Subject Classification (2000): 47 A 16     

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

Modified Ariki-Koike algebras and cyclotomic <Emphasis Type="Italic">q</Emphasis>-Schur algebras

The modified Ariki-Koike algebra is a variation of the original Ariki-Koike algebra over an integral domain R. When R is a rational function field over the independent parameters, But for general R, is not isomorphic to , and has a simpler structure than . In this paper, we construct a cellular basis of which has a similar property as the cellular basis of introduced by Dipper-James-Mathas. By comparing these two cellular bases, we obtain some estimate on the decomposition numbers of in terms of the decomposition numbers of . We also prove the integral form of the Schur-Weyl reciprocity between a certain quantum algebra U_q and on the tensor space      

The cofinality of the saturated uncountable random graph

Assuming CH, let be the saturated random graph of cardinality ₁. In this paper we prove that it is consistent that and can be any two prescribed regular cardinals subject only to the requirement      

Estimates for the -Neumann problem and nonexistence of C 2 Levi-flat hypersurfaces in

Let be a pseudoconvex domain with C² boundary in , n 2. We prove that the -Neumann operator N exists for square-integrable forms on . Furthermore, there exists a number ₀>0 such that the operators and the Bergman projection are regular in the Sobolev space W ( ) for <₀. The -Neumann operator is used to construct -closed extension on for forms on the boundary b. This gives solvability for the tangential Cauchy-Riemann operators on the boundary. Using these results, we show that there exist no non-zero L²-holomorphic (p, 0)-forms on any domain with C² pseudoconcave boundary in with p > 0 and n 2. As a consequence, we prove the nonexistence of C² Levi-flat hypersurfaces in .This paper is a revision of our preprint (May 2003) formerly titled Estimates for the -Neumann problem and nonexistence of Levi-flat hypersurfaces in where the nonexistence of C², Levi-flat hypersurfaces is proved for >0.All three authors are partially supported by NSF grants.An erratum to this article can be found at     

On Cross-intersecting Families of Sets

A family of -element subsets and a family of k-element subsets of an n-element set are cross-intersecting if every set from has a nonempty intersection with every set from . We compare two previously established inequalities each related to the maximization of the product , and give a new and short proof for one of them. We also determine the maximum of for arbitrary positive weights ,_k.     

On the logarithmic plurigenera of complements of plane curves

Let B be a (not necessarily irreducible) plane curve in ². In the present article, we prove that if and only if Moreover, we determine the curve B when and Mathematics Subject Classification (2000): 14R05, 14H50, 14J26     

Infinitely many solutions of a semilinear problem for the Heisenberg Laplacian on the Heisenberg group

We study the semilinear equationwhere is the Heisenberg Laplacian and is the Heisenberg group. The function f C²(×, ) is supposed to satisfy some (subcritical) growth conditions and to be left invariant under the action of the subgroup of consisting of points with integer coordinates.. We show the existence of infinitely many solutions in the space S₁²(), which is the Heisenberg analogue of the Sobolev space W^1,2(^N).Mathematics Subject Classification (2000): 22E30, 22E27     

Diophantine inequalities involving several power sums

Let denote the ring of power sums, i.e. complex functions of the form for some and _iA, where is a multiplicative semigroup. Moreover, let We consider Diophantine inequalities of the form where >1 is a quantity depending on the dominant roots of the power sums appearing as coefficients in F(n,y), and show that all its solutions have y parametrized by some power sums from a finite set. This is a continuation of the work of Corvaja and Zannier [4–6] and of the authors [10, 18] on such problems.Mathematics Subject Classification (2000):11D45,11D61Revised version: 6 May 2004     

A new condensation principle

We generalize (A), which was introduced in [Sch], to larger cardinals. For a regular cardinal >₀ we denote by (A) the statement that and for all regular >,is stationary in It was shown in [Sch] that can hold in a set-generic extension of L. We here prove that can hold in a set-generic extension of L as well. In both cases we in fact get equiconsistency theorems. This strengthens results of [Rä00] and [Rä01]. is equivalent with the existence of 0^#.Mathematics Subject Classification (1991): Primary 03E55, 03E15, Secondary 03E35, 03E60     

A -algorithm for convex minimization

For convex minimization we introduce an algorithm based on -space decomposition. The method uses a bundle subroutine to generate a sequence of approximate proximal points. When a primal-dual track leading to a solution and zero subgradient pair exists, these points approximate the primal track points and give the algorithm's , or corrector, steps. The subroutine also approximates dual track points that are -gradients needed for the method's -Newton predictor steps. With the inclusion of a simple line search the resulting algorithm is proved to be globally convergent. The convergence is superlinear if the primal-dual track points and the objective's -Hessian are approximated well enough. Dedicated to Terry Rockafellar who has had a great influence on our work via strong support for proximal points and for structural definitions that involve tangential convergence. On leave from INRIA Rocquencourt Research of the first author supported by the National Science Foundation under Grant No. DMS-0071459 and by CNPq (Brazil) under Grant No. 452966/2003-5. Research of the second author supported by FAPERJ (Brazil) under Grant No.E26/150.581/00 and by CNPq (Brazil) under Grant No. 383066/2004-2.     

On an eigenvalue problem related to the critical exponent

In this paper we study the eigenvalue problemwhere is a smooth bounded domain, and u is a positive solution of the problemsuch thatwhere S is the best Sobolev constant for the embedding of H¹₀() into L²*(), We prove several estimates for the eigenvalues _i, of (I), i=2,..,N+2 and some qualitative properties of the corresponding eigenfunctions.Supported by M.I.U.R., project Variational methods and nonlinear differential equations.     

On certain categories of modules for affine Lie algebras

In this paper, we exploit basic formal variable techniques to study certain categories of modules for an (untwisted) affine Lie algebra , motivated by Chari-Pressleys work on certain integrable modules. We define and study two categories and of -modules using generating functions, where is proved to contain the well known evaluation modules and to unify highest weight modules, evaluation modules and their tensor product modules. We classify integrable irreducible -modules in categories and and we determine the isomorphism classes of those irreducible modules. Finally we prove a result that relates fusion rules in the context of vertex operator algebras with integrable irreducible modules of Chari-Pressley.in final form: 12 November 2003Partially supported by a NSA grant and a grant from Rutgers Research Council.     

Integral varieties of the canonical cone structure on <Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">P</Emphasis>

The canonical cone structure on a compact Hermitian symmetric space G/P is the fiber bundle where is the cone of the highest weight vectors under the action of the reductive part of P. It is known that the cone coincides with the cone of the vectors tangent to the lines in G/P passing through x, when we consider G/P as a projective variety under its homogeneous embedding into the projective space of the irreducible representation space V of G with highest weight associated to P. A subvariety X of G/P is said to be an integral variety of at all smooth points xG/P. Equivalently, an integral variety of is a subvariety of G/P whose embedded projective tangent space at each smooth point is a linear space We prove a kind of rigidity of the integral varieties under some dimension condition. After making a uniform setting to study the problem, we apply the theory of Lie algebra cohomology as a main tool. Finally we show that the dimension condition is necessary by constructing counterexamples.