Independence Numbers of Planar Contact Graphs

Abstract. We show that for a large class of convex discs C (including strictly convex discs), there exists an ε=ε(C)>0 such that the independence number of the contact graph of any packing of n translates of C in the plane is at least (1/4 + ε)n . For C a circle, we improve the lower bound of Csizmadia to 8/31n .     

A Lower Bound for Weak ɛ -Nets in High Dimension

   Abstract. A finite set N ⊂ R ^d is a weak ε-net for an n -point set X ⊂ R ^d (with respect to convex sets) if it intersects each convex set K with |K ∩ X| ≥ ε n . It is shown that there are point sets X ⊂ R ^d for which every weak ε -net has at least const ⋅

Weierstrass points on trigonal curves I: The ramification points

LetC be a smooth curve of genusg≥5. Assume thatP is a Weierstrass point onC which first non-gap is equal to 3. The gap sequence atP is completely determinated by numbersn and ε satisfying (g−1)/3≤n≤g/2 and ε is 1 or 2 as follows. Given suchn and ε, the corresponding gap sequence is (1, 2, 4, 5,…, 3n−2, 3n−1, 3n+ε, 3n+3+ε, …, 3(g−n−1)+ε). We say thatP is of then-th kind andP is of type I (resp. II) if ε=1 (resp. 2). Because a curve of genusg≥5 has at most one linear systemg1/3, it follows that the Weierstrass points onC with first non-gap equal to 3 are of the same kind.     

Moduli of non-dentability and the radon-nikodým property in banach spaces

We show that for a separable Banach spaceX failing the Radon-Nikodym property (RNP), andε > 0, there is a symmetric closed convex subsetC of the unit ball ofX such that every extreme point of the weak-star closure ofC in the bidualX** has distance fromX bigger than 1 −ε. An example is given showing that the full strength of this theorem does not carry over to the non-separable case. However, admitting a renorming, we get an analogous result for this theorem in the non-separable case too. We also show that in a Banach space failing RNP there is, forε > 0, a convex setC of diameter equal to 1 such that each slice ofC has diameter bigger than 1 −ε. Some more related results about the geometry of Banach spaces failing RNP are given.     

On Regular Vertices of the Union of Planar Convex Objects

Let be a collection of n compact convex sets in the plane such that the boundaries of any pair of sets in intersect in at most s points for some constant s≥4. We show that the maximum number of regular vertices (intersection points of two boundaries that intersect twice) on the boundary of the union U of is O ^*(n ^4/3), which improves earlier bounds due to Aronov et al. (Discrete Comput. Geom. 25, 203–220, 2001). The bound is nearly tight in the worst case. In this paper, a bound of the form O ^*(f(n)) means that the actual bound is C _ε f(n)⋅n ^ε for any ε>0, where C _ε is a constant that depends on ε (and generally tends to ∞ as ε decreases to 0). Work by János Pach and Micha Sharir was supported by NSF Grant CCF-05-14079, and by a grant from the U.S.–Israeli Binational Science Foundation. Work by Esther Ezra and Micha Sharir was supported by grant 155/05 from the Israel Science Fund and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Work on this paper by the first author has also been supported by an IBM Doctoral Fellowship. A preliminary version of this paper has been presented in Proc. 23nd Annu. ACM Sympos. Comput. Geom., 2007, pp. 220–226. E. Ezra’s current address: Department of Computer Science, Duke University, Durham, NC 27708-0129, USA. E-mail: esther@cs.duke.edu     

Representing a Functional Curve by Curves with Fewer Peaks

In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f\bf f be an input piecewise linear functional curve of size n. We consider several variations of the problems. (1) Uphill–downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f\bf f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f\bf f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f\bf f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given ε>0, determine whether there is a feasible UDPR solution for f\bf f with an approximation error ε; its min-ε version: Compute the minimum approximation error ε ^∗ such that there is a feasible UDPR solution for f\bf f with error ε ^∗. For the UR problem, we study its min-k version: Given ε>0, find a feasible solution with the minimum number k ^∗ of unimodal curves for f\bf f with an error ε; its min-ε version: given k>0, compute the minimum error ε ^∗ such that there is a feasible solution with at most k unimodal curves for f\bf f with error ε ^∗. For the FPR problem, we study its min-k version: Given ε>0, find one feasible curve with the minimum number k ^∗ of peaks for f\bf f with an error ε; its min-ε version: given k≥0, compute the minimum error ε ^∗ such that there is a feasible curve with at most k peaks for f\bf f with error ε ^∗. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-ε version) in optimal O(n) time, and the UR min-ε version in O(n+mlog m) time, where m<n is the number of peaks of f\bf f. Our algorithms are based on new geometric observations and interesting techniques.     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds:

The relative isoperimetric inequality outside convex domains in R<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We prove that the area of a hypersurface Σ which traps a given volume outside a convex domain C in Euclidean space R ⁿ is bigger than or equal to the area of a hemisphere which traps the same volume on one side of a hyperplane. Further, when C has smooth boundary ∂C, we show that equality holds if and only if Σ is a hemisphere which meets ∂C orthogonally.     

On Stability of Cones in <Emphasis Type="Italic">R</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis>+1</Superscript> with Zero Scalar Curvature

In this work we generalize the case of scalar curvature zero the results of Simmons (Ann. Math. 88 (1968), 62–105) for minimal cones in Rⁿ⁺¹. If Mⁿ⁻¹ is a compact hypersurface of the sphere Sⁿ(1) we represent by C(M)ε the truncated cone based on M with center at the origin. It is easy to see that M has zero scalar curvature if and only if the cone base on M also has zero scalar curvature. Hounie and Leite (J. Differential Geom. 41 (1995), 247–258) recently gave the conditions for the ellipticity of the partial differential equation of the scalar curvature. To show that, we have to assume n ⩾ 4 and the three-curvature of M to be different from zero. For such cones, we prove that, for n ≤slant 7 there is an ε for which the truncate cone C(M)_ε is not stable. We also show that for n ⩾ 8 there exist compact, orientable hypersurfaces Mⁿ⁻¹ of the sphere with zero scalar curvature and S₃ different from zero, for which all truncated cones based on M are stable. Mathematics Subject Classifications (2000): 53C42, 53C40, 49F10, 57R70.     

On Rich Lines in Grids

In this paper we show that if one has a grid A×B, where A and B are sets of n real numbers, then there can be only very few “rich” lines in certain quite small families. Indeed, we show that if the family has lines taking on n ^ε distinct slopes, and where each line is parallel to n ^ε others (so, at least n ^2ε lines in total), then at least one of these lines must fail to be “rich”. This result immediately implies non-trivial sumproduct inequalities; though, our proof makes use of the Szemeredi-Trotter inequality, which Elekes used in his argument for lower bounds on |C+C|+|C.C|.     

Symmetric block bases of sequences with large average growth

We show that if 0<ε≦1, 1≦p<2 andx ₁, …,x _n is a sequence of unit vectors in a normed spaceX such thatE ‖∑ _l ⁿ ε_i x _l‖≧n ^1/p, then one can find a block basisy ₁, …,y _m ofx ₁, …,x _n which is (1+ε)-symmetric and has cardinality at leastγn ^2/p-1(logn)⁻¹, where γ depends on ε only. Two examples are given which show that this bound is close to being best possible. The first is a sequencex ₁, …,x _n satisfying the above conditions with no 2-symmetric block basis of cardinality exceeding 2n ^2/p-1. This sequence is not linearly independent. The second example is a sequence which satisfies a lowerp-estimate but which has no 2-symmetric block basis of cardinality exceedingCn ^2/p-1(logn)^4/3, whereC is an absolute constant. This applies when 1≦p≦3/2. Finally, we obtain improvements of the lower bound when the spaceX containing the sequence satisfies certain type-condition. These results extend results of Amir and Milman in [1] and [2]. We include an appendix giving a simple counterexample to a question about norm-attaining operators.     

Lip Automorphism Germ and Lip Automorphism

Let X be a metric space, ε^n(X) be the standard trivial Lip n-bundle over X, and Φ be a Lip automorphism germ of ε^n(X). This paper proves that there is a Lip automorphism Φ‘ of ε^n(X) such that the germ of Φ‘ is Φ.     

Isomorphic embedding of ℓ p n , 1<p<2, into ℓ 1 (1+ε)n

In this paper we partially answer a question posed by V. Milman and G. Schechtman by proving that ℓ _p ⁿ , (C logn)^1/q(1+1/ε)-embeds into ℓ ₁ ^(1+ε)n , where 1<p<2 and 1/p+1/q=1. Supported by ISF.     

Quasi-parabolic analytic transformations of <Emphasis Type="Bold">C</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>. Parabolic manifolds

In [Rong, F., Quasi-parabolic analytic transformations of C ⁿ , J. Math. Anal. Appl. 343 (2008), 99–109], we showed the existence of “parabolic curves” for certain quasi-parabolic analytic transformations of C ⁿ . Under some extra assumptions, we show the existence of “parabolic manifolds” for such transformations.     

Interpolation by holomorphic automorphisms and embeddings in Cn

Let n > 1 and let C ⁿ denote the complex n-dimensional Euclidean space. We prove several jet-interpolation results for nowhere degenerate entire mappings F:C ⁿ →C ⁿ and for holomorphic automorphisms of C ⁿ on discrete subsets of C ⁿ.We also prove an interpolation theorem for proper holomorphic embeddings of Stein manifolds into C ⁿ.For each closed complex submanifold (or subvariety) M ⊂ C ⁿ of complex dimension m < n we construct a domain Ω ⊂C ⁿ containing M and a biholomorphic map F: Ω → C ⁿ onto C ⁿ with J F ≡ 1such that F(M) intersects the image of any nondegenerate entire map G:C ^n−m →C ⁿ at infinitely many points. If m = n − 1, we construct F as above such that C ⁿ ∖F(M) is hyperbolic. In particular, for each m ≥ 1we construct proper holomorphic embeddings F:C ^m →C ^m−1 such that the complement C ^m+1 ∖F(C ^m )is hyperbolic.     

Convergence analysis of iterative sequences for a pair of mappings in Banach spaces

Let C be a nonempty closed convex subset of a real Banach space E. Let S ： C→ C be a quasi-nonexpansive mapping, let T ： C→C be an asymptotically demicontractive and uniformly Lipschitzian mapping, and let F ：= {x ∈C ： Sx = x and Tx = x}≠Ф Let {xn}n≥0 be the sequence generated irom an arbitrary x0∈Cby xn＋i=（1-cn）Sxn＋cnT^nxn, n≥0.We prove the necessary and sufficient conditions for the strong convergence of the iterative sequence {xn} to an element of F. These extend and improve the recent results of Moore and Nnoli.     

A finiteness result for groups which quasi-act on hyperbolic spaces

Let (X, d) be a Gromov-hyperbolic metric space endowed with a measure having finite entropy H and such that the measure of every ball of radius R > 0 is finite and bounded from below by a positive function of R. In this paper we look at the set Q(X; L, C, D) of the isomorphism classes of torsion-free groups Γ which admit a discrete, D-co-bounded (L, C)-quasi-action on X (D > 0, L ≥ 1, C ≥ 0) and we describe some algebraic conditions which, imposed on the groups Γ, define finite subsets of Q(X; L, C, D), provided C < ε for some ε > 0. As an example, these conditions are satisfied when Γ is assumed to admit a faithful, discrete, m-dimensional representation over some local field (in this case ε = ε(m, H, L)). In particular (set C = 0, L = 1), our results apply when the groups are assumed to act by isometries.     

Optimization of convex functions on w*-compact sets

We give a direct, self-contained, and iterative proof that for any convex, Lipschitz andw ^*-lower semicontinuous function ϕ defined on aw ^*-compact convex setC in a dual Banach spaceX ^* and for any ε>0 there is anx∈X, with ‖x‖≤ε, such that ϕ+x attains its supremum at an extreme point ofC. This result is implicitly contained in the work of Lindenstrauss [9] and the work of Ghoussoub and Maurey on strongw ^*−H _σ sets [8]. In addition, we discuss the applications of this result to the geometry of convex sets. Research supported in part by the NSERC of Canada under grant OGP41983 for the first author and grant OGP7926 for the second author.     

Manifolds polarized by vector bundles

LetX be a complex projective manifold of dimension n and let ε be an ample vector bundle of rank r. Let also τ = τ (X,ε) = min {t ∈ ℝ : K_X + t det ε is nef} be the nef value of the pair (X, ε). In this paper we classify the pairs (X, ε) such that{ Mathematics Subject Classification (2000)14J60; 14J40; 14E30