Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

Weak-type Endpoint Estimates for Multilinear Singular Integral Operators

In this paper, the authors discuss a class of multilinear singular integrals and obtain that the operators are bounded from H^1(R^n) to weak L^1(R^n). Using this result, we can directly prove a main theorem in [5].     

Two constructions of oriented matroids with disconnected extension space

The extension space ℰ(ℳ) of an oriented matroid ℳ is the poset of all one-element extensions of ℳ, considered as a simplicial complex. We present two different constructions leading to rank 4 oriented matroids with disconnected extension space. We prove especially that if an elementf is not contained in any mutation of a rank 4 oriented matroid ℳ, then ℰ(ℳ\f) contains an isolated point. A uniform nonrealizable arrangement of pseudoplanes with this property is presented. The examples described contrast results of Sturmfels and Ziegler [12] who proved that for rank 3 oriented matroids the extension space has the homotopy type of the 2-sphere.     

Cantor set and interpolation

In 1998, Y. Benyamini published interesting results concerning interpolation of sequences using continuous functions ℝ → ℝ. In particular, he proved that there exists a continuous function ℝ → ℝ which in some sense “interpolates” all sequences (x _n ) _n∈ℤ ∈ [0, 1]^ℤ “simultaneously.” In 2005, M.R. Naulin and C. Uzcátegui unified and generalized Benyamini’s results. In this paper, the case of topological spaces X and Y with an Abelian group acting on X is considered. A similar problem of “simultaneous interpolation” of all “generalized sequences” using continuous mappings X → Y is posed. Further generalizations of Naulin-Uncátegui theorems, in particular, multidimensional analogues of Benyamini’s results are obtained.     

On the diffeomorphic type of the complement to a line arrangement in a projective plane

We show that the diffeomorphic type of the complement to a line arrangement in a complex projective plane P ² depends only on the graph of line intersections if no line in the arrangement contains more than two points in which at least two lines intersect. This result also holds for some special arrangements which do not satisfy this property. However it is not true in general, see [Rybnikov G., On the fundamental group of the complement of a complex hyperplane arrangement, Funct. Anal. Appl., 2011, 45(2), 137–148].     

Enriched homology and cohomology modules of simiplicial complexes

For a simplicial complex Δ on {1, 2,…, n} we define enriched homology and cohomology modules. They are graded modules over k[x ₁,…, x _n ] whose ranks are equal to the dimensions of the reduced homology and cohomology groups. We characterize Cohen-Macaulay, l-Cohen-Macaulay, Buchsbaum, and Gorenstein^* complexes Δ, and also orientable homology manifolds in terms of the enriched modules. We introduce the notion of girth for simplicial complexes and make a conjecture relating the girth to invariants of the simplicial complex. We also put strong vanishing conditions on the enriched homology modules and describe the simplicial complexes we then get. They are block designs and include Steiner systems S(c, d, n) and cyclic polytopes of even dimension. This paper is to a large extent a complete rewriting of a previous preprint, “Hierarchies of simplicial complexes via the BGG-correspondence”. Also Propositions 1.7 and 3.1 have been generalized to cell complexes in [11].     

Matroid Enumeration for Incidence Geometry

Matroids are combinatorial abstractions for point configurations and hyperplane arrangements, which are fundamental objects in discrete geometry. Matroids merely encode incidence information of geometric configurations such as collinearity or coplanarity, but they are still enough to describe many problems in discrete geometry, which are called incidence problems. We investigate two kinds of incidence problem, the points–lines–planes conjecture and the so-called Sylvester–Gallai type problems derived from the Sylvester–Gallai theorem, by developing a new algorithm for the enumeration of non-isomorphic matroids. We confirm the conjectures of Welsh–Seymour on ≤11 points in ℝ³ and that of Motzkin on ≤12 lines in ℝ², extending previous results. With respect to matroids, this algorithm succeeds to enumerate a complete list of the isomorph-free rank 4 matroids on 10 elements. When geometric configurations corresponding to specific matroids are of interest in some incidence problems, they should be analyzed on oriented matroids. Using an encoding of oriented matroid axioms as a boolean satisfiability (SAT) problem, we also enumerate oriented matroids from the matroids of rank 3 on n≤12 elements and rank 4 on n≤9 elements. We further list several new minimal non-orientable matroids.     

The universal partition theorem for oriented matroids

We consider realization spaces of a family of oriented matroids of rank three as point configurations in the affine plane. The fundamental problem arises as to which way these realization spaces partition their embedding space. The Universal Partition Theorem roughly states that such a partition can be as complicated as any partition of ℝ ⁿ into elementary semialgebraic sets induced by an arbitrary finite set of polynomials in ℤ[X]. We present the first proof of the Universal Partition Theorem. In particular, it includes the first complete proof of the so-called Universality Theorem. This work was supported by the Deutsche Forschungsgemeinschaft, Graduiertenkolleg “Analyse und Konstruktion in der Mathematik”.     

A combinatorial Lefschetz fixed point formula

We define a class of simplicial maps — those which are “expanding directions preserving” — from a barycentric subdivision to the original simplicial complex. These maps naturally induce a self map on the links of their fixed points. The local index at a fixed point of such a map turns out to be the Lefschetz number of the induced map on the link of the fixed point in relative homology. We also show that a weakly hyperbolic [4] simplicial map sdⁿK →K is expanding directions preserving.     

Castles in the air revisited

We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ ^d isO(n ^d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more than one “side” isO(n ^d−1 logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n ^d−1 log² n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement. Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Arrangements with one bounded component andp-adic integrals

In this article we study arrangementsA, such that ℝ ⁿ \A has exactly one bounded component. We obtain a result about their structure which gives us a method to construct all combinatorially different such arrangements in a given dimension. (A complete list for dimensions 1,2,3 and 4 is included). Furthermore we associate ap-adic integral to each such arrangement and proof that this integral can be written as a product ofp-adic beta functions. This is analogous to results of Varchenko and Loeser for integrals over ℝ and character sums over finite fields respectively.     

The van Kampen obstruction and its relatives

We review a cochain-free treatment of the classical van Kampen obstruction ϑ to embeddability of an n-polyhedron in ℝ²ⁿ and consider several analogs and generalizations of ϑ, including an extraordinary lift of ϑ, which has been studied by J.-P. Dax in the manifold case. The following results are obtained: (1) The mod 2 reduction of ϑ is incomplete, which answers a question of Sarkaria. (2) An odd-dimensional analog of ϑ is a complete obstruction to linkless embeddability (=“intrinsic unlinking”) of a given n-polyhedron in ℝ²ⁿ⁺¹. (3) A “blown-up” one-parameter version of ϑ is a universal type 1 invariant of singular knots, i.e., knots in ℝ³ with a finite number of rigid transverse double points. We use it to decide in simple homological terms when a given integer-valued type 1 invariant of singular knots admits an integral arrow diagram (= Polyak-Viro) formula. (4) Settling a problem of Yashchenko in the metastable range, we find that every PL manifold N nonembeddable in a given ℝ ^m , m ≥ $ \frac{{3(n + 1)}} {2} $ \frac{{3(n + 1)}} {2} , contains a subset X such that no map N → ℝ ^m sends X and N \ X to disjoint sets. (5) We elaborate on McCrory’s analysis of the Zeeman spectral sequence to geometrically characterize “k-co-connected and locally k-co-connected” polyhedra, which we embed in ℝ2 ^n−k for k < $ \frac{{n - 3}} {2} $ \frac{{n - 3}} {2} , thus extending the Penrose-Whitehead-Zeeman theorem.     

Generalized low pass filters and MRA frame wavelets

A tight frame wavelet ψ is an L ²(ℝ) function such that {ψ jk(x)} = {2^j/2 ψ(2 ^j x −k), j, k ∈ ℤ},is a tight frame for L ² (ℝ).We introduce a class of “generalized low pass filters” that allows us to define (and construct) the subclass of MRA tight frame wavelets. This leads us to an associated class of “generalized scaling functions” that are not necessarily obtained from a multiresolution analysis. We study several properties of these classes of “generalized” wavelets, scaling functions and filters (such as their multipliers and their connectivity). We also compare our approach with those recently obtained by other authors.     

On an oppenheim-type conjecture for systems of quadratic forms

In this paper we establish dimension freeL ^p (ℝ ⁿ ,|x|^α) norm inequalities (1<p<∞) for the oscillation and variation of the Riesz transforms in ℝ ⁿ . In doing so we findA _p -weighted norm inequalities for the oscillation and the variation of the Hilbert transform in ℝ. Some weighted transference results are also proved. Partially supported by European Commission via the TMR network “Harmonic Analysis”.     

Limitations to Fréchet’s metric embedding method

Fréchet’s classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Fréchet embedding is Bourgain's embedding [4]. The authors have recently shown [2] that for every ε>0, anyn-point metric space contains a subset of size at leastn ^1−ε which embeds into ℓ₂ with distortion . The embedding used in [2] is non-Fréchet, and the purpose of this note is to show that this is not coincidental. Specifically, for every ε>0, we construct arbitrarily largen-point metric spaces, such that the distortion of any Fréchet embedding into ℓ_p on subsets of size at leastn ^1/2+ε is Ω((logn)^1/p ). Supported in part by a grant from the Israeli National Science Foundation. Supported in part by a grant from the Israeli National Science Foundation. Supported in part by the Landau Center.     

Weak helix submanifolds of euclidean spaces

Let M⊂ℝ ⁿ be a submanifold of a euclidean space. A vector d∈ℝ ⁿ is called a helix direction of M if the angle between d and any tangent space T _p M is constant. Let ℋ(M) be the set of helix directions of M. If the set ℋ(M) contains r linearly independent vectors we say that M is a weak r-helix. We say that M is a strong r-helix if ℋ(M) is a r-dimensional linear subspace of ℝ ⁿ . For curves and hypersurfaces both definitions agree. The object of this article is to show that these definitions are not equivalent. Namely, we construct (non strong) weak 2-helix surfaces of ℝ⁴. The author is supported by the Project M.I.U.R. “Riemann Metrics and Differentiable Manifolds” and by G.N.S.A.G.A. of I.N.d.A.M., Italy.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

Dimension Gaps between Representability and Collapsibility

A simplicial complex K\mathsf{K} is called d -representable if it is the nerve of a collection of convex sets in ℝ ^d ; K\mathsf{K} is d -collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d−1 that is contained in a unique maximal face; and K\mathsf{K} is d -Leray if every induced subcomplex of K\mathsf{K} has vanishing homology of dimension d and larger. It is known that d-representable implies d-collapsible implies d-Leray, and no two of these notions coincide for d≥2. The famous Helly theorem and other important results in discrete geometry can be regarded as results about d-representable complexes, and in many of these results, “d-representable” in the assumption can be replaced by “d-collapsible” or even “d-Leray.”     

Square roots of elliptic second order divergence operators on strongly lipschitz domains:<Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript> theory

We prove the Kato conjecture for square roots of elliptic second order non-self-adjoint operators in divergence formL = -div(A∇) on strongly Lipschitz domains in ℝⁿ, n≥2, subject to Dirichlet or to Neumann boundary conditions. The method relies on a transference procedure from the recent positive result on ℝⁿ in [2].