Cyclic branched coverings of lens spaces

Some infinite family is constructed of orientable three-dimensional closed manifoldsM _n (p, q), where n ≥ 2, p ≥ 3, 0 < q < p, and (p, q) = 1, such that M _n (p, q) is an n-fold cyclic covering of the lens space L(p, q) branched over a two-component link.     

Bin packing can be solved within 1 + ε in linear time

For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997.     

On moduli of vector bundles on surfaces with negative Kodaira dimension

Summary Here we prove the following result. Fix integersq, τ,a’, b’, a’ _i, 1≤i≤τ,a’, b’, a’ _i, 1≤i≤τ; then there is an integerew such that for every integert≥w, for every algebraically closed fieldK for every smooth complete surfaceX with negative Kodaira dimension, irregularityq andK _X ² =8(1−q)−τ, the following condition holds; ifX→S is a sequence fo τ blowing-downs which gives a relatively minimal model with ruling ρ:S→C, take as basis of the Neron Severi groupNS(X) a smooth rational curve which is the total transform of a fiber ofC, the total transform of a minimal section of ρ and the total transformD _i, 1≤i≤τ, of the exceptional curver; then for everyH andL∈Pic (X) withH ample,H (resp.L) represented by the integersa’, b’, a’ _i, (resp.a’, b’, a’ _i), 1≤i≤τ, in the chosen basis ofNS(X) the moduli spaceM(ZX, 2,H, L, t) of rank 2H-stable vector bundles onX with determinantL andc ₂=t is generically smooth and the number, dimension and ?birational structure? of the irreducible components ofM(X, 2,H, L, t)_red do not depend on the choice ofK andX. Furthermore the birational structure of these irreducible components can be loosely described in terms of the birational structure of the components of suitableM(S, 2,H’, L’, t’)_red withS a relatively minimal model ofX.

---

Sunto SiaX una superficie algebrica liscia completa con dimensione di Kodaira negativa e definita su un campo algebricamente chiusoK; fissiamoH eL∈Pic (X),t∈Z; siaq l’irregolarità diX e τ≔8(1−q)−K _X ^Emphasis>2 ; siaM(X, 2,H, L, t) to schema dei moduli dei fibrati vettorialiH-stabili di rango 2 suX con determinateL ec ₂=t. Si dimostra che esiste una costantew che dipende solo daq, da τ e dalla classe numerica diH e diL (ma non da char (K) o dalla classe di isomorphismo diX) tale che per ognit≥w il numero, la dimensione e ?la struttura birazionale? delle componenti irriducibili diM(X, 2,H, L, t)_red non dipende dalla scelta di char (K),K eX ma solo daq, τ e dalle classi diH eL inNS(X). Inoltre la ?struttura birazionale? di queste componenti irriducibili può essere grossolanamente descritta in termini delle componenti di opportuni spazi di moduliM(S, 2,H’, L’, t’) (doveS è un modello minimale diX).

     

The lagrange intersections for (ℂP n , ℝP n )

Summary If (M, ω) is a compact symplectic manifold andL ⊂M a compact Lagrangian submanifold and if φ is a Hamiltonian diffeomorphism ofM then the V. Arnold conjecture states (possibly under additional conditions) that the number of intersection section points ofL and φ (L) can be estimated by #{Lϒφ (L)}≥ cuplength +1. We shall prove this conjecture for the special case (L, M)=(ℝP ⁿ , ℂP ⁿ ) with the standard symplectic structure.     

Efficient Computation of Rectilinear Geodesic Voronoi Neighbor in the Presence of Obstacles

In this paper we present an algorithm to compute the rectilinear geodesic voronoi neighbor of an arbitrary query pointqamong a setSofmpoints in the presence of a set ofnvertical line segment obstacles inside a rectangular floor. The distance between a pair of points α and β is the shortest rectilinear distance avoiding the obstacles in and is denoted by δ(α, β). The rectilinear geodesic voronoi neighbor of an arbitrary query pointq,RGVN(q) is the pointp_i ∈ Ssuch that δ(q, p_i) is minimum. The algorithm suggests a preprocessing of the elements of the setsSand inO((m + n)log(m + n)) time such that for an arbitrary query pointq, theRGVNquery can be answered inO(log(m + n)) time. The space required for storing the preprocessed information isO(n + m log m). If the points inSare placed on the boundary of the rectangular floor, a different technique is adopted to decrease the space complexity toO(m + n). This technique works even if the obstacles are rectangles instead of line segments. Finally, the parallelization of the preprocessing steps for the latter algorithm is suggested, which takesO(log³(m + n)) time, usingO((m + n)^1.5/log²(m + n)) processors andO(log(m + n)) query time.     

On countable stable structures which are homogeneous for a finite relational language

LetL be a finite relational language andH(L) denote the class of all countable structures which are stable and homogeneous forL in the sense of Fraissé. By convention countable includes finite and any finite structure is stable. A rank functionr :H(L) →ω is introduced and also a notion of dimension for structures inH(L). A canonical way of shrinking structures is defined which reduces their dimensions. The main result of the paper is that anyM ∈H(L) can be shrunk toM′ ∈H(L),M′ ⊆M, such that |M′| is bounded in terms ofr(M), and the isomorphism type ofM overM′ is uniquely determined by the dimensions ofM. Forr<ω we deduce thatH(L, r), the class of allM ∈H(L) withr(M)≦r, is the union of a finite number of classes within each of which the isomorphism type of a structure is completely determined by its dimensions. Dedicated to the memory of Abraham Robinson on the tenth anniversary of his death     

A new characterization of L 2(q) by its noncommuting graph

Let G be a non-abelian group and associate a non-commuting graph ∇(G) with G as follows: the vertex set of ∇(G) is G\Z(G) with two vertices x and y joined by an edge whenever the commutator of x and y is not the identity. In this short paper we prove that if G is a finite group with ∇(G) ≅ ∇(M), where M = L ₂(q) (q = p ⁿ , p is a prime), then G ≅ M.      

A Lower Bound for the Norm of the Minimal Residual Polynomial

Let S be a compact infinite set in the complex plane with 0∉S, and let R _n be the minimal residual polynomial on S, i.e., the minimal polynomial of degree at most n on S with respect to the supremum norm provided that R _n (0)=1. For the norm L _n (S) of the minimal residual polynomial, the limit k(S):=lim_n?￥ⁿ?{L_n(S)}\kappa(S):=\lim_{n\to\infty}\sqrt[n]{L_{n}(S)} exists. In addition to the well-known and widely referenced inequality L _n (S)≥κ(S) ⁿ , we derive the sharper inequality L _n (S)≥2κ(S) ⁿ /(1+κ(S)²ⁿ ) in the case that S is the union of a finite number of real intervals. As a consequence, we obtain a slight refinement of the Bernstein–Walsh lemma.     

On the Stanley depth of squarefree Veronese ideals

Let K be a field and S=K[x ₁,…,x _n ]. In 1982, Stanley defined what is now called the Stanley depth of an S-module M, denoted sdepth (M), and conjectured that depth (M)≤sdepth (M) for all finitely generated S-modules M. This conjecture remains open for most cases. However, Herzog, Vladoiu and Zheng recently proposed a method of attack in the case when M=I/J with J⊂I being monomial S-ideals. Specifically, their method associates M with a partially ordered set. In this paper we take advantage of this association by using combinatorial tools to analyze squarefree Veronese ideals in S. In particular, if I _n,d is the squarefree Veronese ideal generated by all squarefree monomials of degree d, we show that if 1≤d≤n<5d+4, then sdepth (I _n,d )=⌊(n−d)/(d+1)⌋+d, and if d≥1 and n≥5d+4, then d+3≤sdepth (I _n,d )≤⌊(n−d)/(d+1)⌋+d.     

The Helmholtz decomposition of weightedLq-spaces for Muckenhoupt weights

We consider weights of Muckenhoupt classA _q, 1<q<∞. For a bounded Lipschitz domain Ω⊂ℝⁿ we prove a compact embedding and a Poincaré inequality in weighted Sobolev spaces. These technical tools allow us to solve the weak Neumann problem for the Laplace equation in weighted spaces on ℝⁿ, ℝⁿ ₊, on bounded and on exterior domains Ω with boundary of classC ¹, which will yield the Helmholtz decomposition ofL _ω ^q(Ω)ⁿ for general ω∈A _q. This is done by transferring the method of Simader and Sohr [4] to the weighted case. Our result generalizes a result of Farwig and Sohr [2] where the Helmholtz decomposition ofL _ω ^p(Ω)ⁿ is proved for an exterior domain and weights of Muckenhoupt class without singularities or degeneracies in a neighbourhood of ϖΩ.

---

Sunto In questo lavoro consideriamo dei pesi della classe di MuckenhouptA _q, 1<q<∞. Per un dominio limitato lipschitziano Ω⊂ℝⁿ, dimostriamo una immersione compatta ed una disuguaglianza di Poincaré in spazi di Sobolev con peso. Questa tecnica ci consente di risolvere il problema debole di Neumann per l’equazione di Laplace in spazi pesati in ℝⁿ, ℝⁿ ₊ in domini limitati ed in domini esterni con frontiera di classeC ¹, che conduce alla decomposizione di Helmholtz diL _ω ^q(Ω)ⁿ per un qualsiasi ω∈A _q. Il risultato è ottenuto trasferendo il metodo di Simader e Sohr [4] al caso pesato. Quello qui presente estende un risultato di Farwig e Sohr [2] dove la decomposizione di Helmholtz diL _ω ^q(Ω)ⁿ è dimostrata per domini esterni e pesi della classe di Muckenhoupt privi di singolarità in un intorno di ϖΩ.

     

Test elements for endomorphisms of free groups and algebras

LetE be a bounded Borel subset of ℝⁿ,n≥2, of positive Lebesgue measure andP _E the corresponding ‘Pompeiu transform”. We prove thatP _E is injective onL ^p(ℝⁿ) if 1≤p≤2n/(n-1). We explore the connection between this problem and a Wiener-Tauberian type theorem for theM(n) action onL ^q(ℝⁿ) for various values ofq. We also take up the question of whenP _E is injective in caseE is of finite, positive measure, but is not necessarily a bounded set. Finally, we briefly look at these questions in the contexts of symmetric spaces of compact and non-compact type.     

A characterization of convexity and central symmetry for planar polygonal sets

LetS be a compact set inR ² with nonempty interior,L(u,k) be a line 〈u, x〉 =k, and ζ _u (k) be the linear Lebesgue measure ofS∩L(u,k). It is well known that for a convexS, ζ _u (k) is unimodal, that is, as a function ofk, it is first non-decreasing and then nonincreasing for everyu∈R ². Further, ifS is centrally symmetric with respect toM, ζ _u (k) achieves maximum whenL(u, k) passes throughM. Converse propositions are considered in this paper for polygonalS with Jordan boundary. It is shown that unimodality alone does not suffice for convexity. However, if ζ _u (k) achieves maximum wheneverL(u, k) passes through some fixed pointM then unimodality yields convexity as well as central symmetry. It is also shown that continuity of ζ _u (k) in the interior of its support implies convexity ofS. This last result, however, is false for non-polygonal sets. Research supported by National Science Foundation Grant GP-28154.     

The Quasi-Canonical Solution Operator to $${\bar \partial }$$ Restricted to the Fock-Space

We consider the solution operator S: ℱ_μ,(p,q) → L ²(μ)_{(p, q)} to the -operator restricted to forms with coefficients in ℱ_μ = {f: f is entire and ∫_ℂn |f(z)|² dμ(z) < ∞}. Here ℱ_μ,(p,q) denotes (p,q)-forms with coefficients in ℱ_μ, L ²(μ) is the corresponding L ²-space and μ is a suitable rotation-invariant absolutely continuous finite measure. We will develop a general solution formula S to . This solution operator will have the property Sv ⊥ ℱ_(p,q) ∀v ∈ ℱ_(p,q+1). As an application of the solution formula we will be able to characterize compactness of the solution operator in terms of compactness of commutators of Toeplitz-operators : ℱ_μ → L ²(μ).     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

Embedding Structures

 For any quasiordered set (`quoset') or topological space S, the set Sub S of all nonempty subquosets or subspaces is quasiordered by embeddability. Given any cardinal number n, denote by p _n and q _n the smallest size of spaces S such that each poset, respectively, quoset with n points is embeddable in Sub S. For finite n, we prove the inequalities n + 1 ≤p _n ≤q _n ≤p _n + l(n) + l(l(n)), where l(n) = min{k∈ℕ∣n≤2 ^k }. For the smallest size b _n of spaces S so that Sub S contains a principal filter isomorphic to the power set ?(n), we show n + l(n) − 1 ≤b _n ≤n + l(n) + l(l(n))+2. Since p _n ≤b _n , we thus improve recent results of McCluskey and McMaster who obtained p _n ≤n ². For infinite n, we obtain the equation b _n = p _n = q _n = n. Received: April 19, 1999 Final version received: February 21, 2000     

Sequentially equidistant points in metric spaces

A sequence (z ₀,z ₁,z ₂,, ...,z _n, z _n+1) of points fromp=z ₀ toq=z _n+1 in a metric spaceX is said to besequentially equidistant ifd(z _i−1,z _i)=d(z _i,z _i+1) for 1≦i≦n. If there is path inX fromp toq (or if a certain weaker condition holds), then such a sequence exists, with all points distinct, for every choice ofn, while ifX is compact and connected, then such a sequence exists at least forn=2. An example is given of a dense connected subspaceS ofR ^m ,m≧2, and an uncountable dense subsetE disjoint fromS for which there is no sequentially equidistant sequence of distinct points (n ≧ 2) inS ∪E between any two points ofE. Techniques of dimension theory are utilized in the construction of these examples, as well as in the proofs of some of the positive results. Supported in part by NSF Grant DMS-8701666.     

A Characterization of the Complement of a Hyperbolic Quadric in PG (3, q), for q Odd

The incidence structure NQ⁺(3, q) has points the points not on a non-degenerate hyperbolic quadric Q⁺(3, q) in PG(3, q), and its lines are the lines of PG(3, q) not containing a point of Q⁺(3, q). It is easy to show that NQ⁺(3, q) is a partial linear space of order (q, q(q−1)/2). If q is odd, then moreover NQ⁺(3, q) satisfies the property that for each non-incident point line pair (x,L), there are either (q−1)/2 or (q+1)/2 points incident with L that are collinear with x. A partial linear space of order (s, t) satisfying this property is called a ((q−1)/2,(q+1)/2)-geometry. In this paper, we will prove the following characterization of NQ⁺(3,q). Let S be a ((q−1)/2,(q+1)/2)-geometry fully embedded in PG(n, q), for q odd and q>3. Then S = NQ⁺(3, q).     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

Generalized Veronesean embeddings of projective spaces

We classify all embeddings θ: PG(n, q) → PG(d, q), with $d \geqslant \tfrac{{n(n + 3)}} {2}$d \geqslant \tfrac{{n(n + 3)}} {2}, such that θ maps the set of points of each line to a set of coplanar points and such that the image of θ generates PG(d, q). It turns out that d = ?n(n+3) and all examples are related to the quadric Veronesean of PG(n, q) in PG(d, q) and its projections from subspaces of PG(d, q) generated by sub-Veroneseans (the point sets corresponding to subspaces of PG(n, q)). With an additional condition we generalize this result to the infinite case as well.     

Safety Zone Problem

Given a simple polygon P, its safety zone S (of width δ) is a closed region consisting of straight line segments and circular arcs (of radius δ) bounding the polygon P such that there exists no pair of points p (on the boundary of P) and q (on the boundary of S) having their Euclidean distance d(p, q) less than δ. In this paper we present a linear time algorithm for finding the minimum area safety zone of an arbitrarily shaped simple polygon. It is also shown that our proposed method can easily be modified to compute the Minkowski sum of a simple polygon and a convex polygon in O(MN) time, where M and N are the number of vertices of both the polygons.