Adaptive Galerkin boundary element methods with panel clustering

In this paper, we will propose a boundary element method for solving classical boundary integral equations on complicated surfaces which, possibly, contain a large number of geometric details or even uncertainties in the given data. The (small) size of such details is characterised by a small parameter and the regularity of the solution is expected to be low in such zones on the surface (which we call the wire-basket zones). We will propose the construction of an initial discretisation for such type of problems. Afterwards standard strategies for boundary element discretisations can be applied such as the h, p, and the adaptive hp-version in a straightforward way. For the classical boundary integral equations, we will prove the optimal approximation results of our so-called wire-basket boundary element method and discuss the stability aspects. Then, we construct the panel-clustering and -matrix approximations to the corresponding Galerkin BEM stiffness matrix. The method is shown to have an almost linear complexity with respect to the number of degrees of freedom located on the wire basket.     

The Poisson boundary of lamplighter random walks on trees

Let be the homogeneous tree with degree q + 1 ≥ 3 and a finitely generated group whose Cayley graph is . The associated lamplighter group is the wreath product , where is a finite group. For a large class of random walks on this group, we prove almost sure convergence to a natural geometric boundary. If the probability law governing the random walk has finite first moment, then the probability space formed by this geometric boundary together with the limit distribution of the random walk is proved to be maximal, that is, the Poisson boundary. We also prove that the Dirichlet problem at infinity is solvable for continuous functions on the active part of the boundary, if the lamplighter “operates at bounded range”. Supported by ESF program RDSES and by Austrian Science Fund (FWF) P15577.     

Random walk in random scenery and self-intersection local times in dimensions d ≥ 5

Let {S _k , k ≥ 0} be a symmetric random walk on , and an independent random field of centered i.i.d. random variables with tail decay . We consider a random walk in random scenery, that is . We present asymptotics for the probability, over both randomness, that {X _n > n ^β} for β > 1/2 and α > 1. To obtain such asymptotics, we establish large deviations estimates for the self-intersection local times process , where l _n (x) is the number of visits of site x up to time n.      

Hiding Cliques for Cryptographic Security

We demonstrate how a well studied combinatorial optimizationproblem may be used as a new cryptographic primitive. The problemin question is that of finding a "large" clique in a randomgraph. While the largest clique in a random graph with nvertices and edge probability p is very likely tobe of size about , it is widely conjecturedthat no polynomial-time algorithm exists which finds a cliqueof size with significantprobability for any constant > 0. We presenta very simple method of exploiting this conjecture by hidinglarge cliques in random graphs. In particular, we show that ifthe conjecture is true, then when a large clique—of size,say, is randomlyinserted (hidden) in a random graph, finding a clique ofsize remains hard.Our analysis also covers the case of high edge probabilitieswhich allows us to insert cliques of size up to . Our result suggests several cryptographicapplications, such as a simple one-way function.     

Valleys and the Maximum Local Time for Random Walk in Random Environment

Let ξ (n, x) be the local time at x for a recurrent one-dimensional random walk in random environment after n steps, and consider the maximum ξ^*(n) = max _x ξ(n, x). It is known that lim sup is a positive constant a.s. We prove that lim inf is a positive constant a.s. this answers a question of P. Révész [5]. The proof is based on an analysis of the valleys in the environment, defined as the potential wells of record depth. In particular, we show that almost surely, at any time n large enough, the random walker has spent almost all of its lifetime in the two deepest valleys of the environment it has encountered. We also prove a uniform exponential tail bound for the ratio of the expected total occupation time of a valley and the expected local time at its bottom.     

On the Kernel Rule for Function Classification

Let X be a random variable taking values in a function space , and let Y be a discrete random label with values 0 and 1. We investigate asymptotic properties of the moving window classification rule based on independent copies of the pair (X,Y). Contrary to the finite dimensional case, it is shown that the moving window classifier is not universally consistent in the sense that its probability of error may not converge to the Bayes risk for some distributions of (X,Y). Sufficient conditions both on the space and the distribution of X are then given to ensure consistency.     

Dissecting the 2-sphere by immersions

The self intersection of an immersion dissects S ² into pieces which are planar surfaces (unless i is an embedding). In this work we determine what collections of planar surfaces may be obtained in this way. In particular, for every n we construct an immersion with 2n triple points, for which all pieces are discs.      

All superconformal surfaces in $${\mathbb R^4}$$ in terms of minimal surfaces

We give an explicit construction of any simply connected superconformal surface in Euclidean space in terms of a pair of conjugate minimal surfaces . That is superconformal means that its ellipse of curvature is a circle at any point. We characterize the pairs (g, h) of conjugate minimal surfaces that give rise to images of holomorphic curves by an inversion in and to images of superminimal surfaces in either a sphere or a hyperbolic space by an stereographic projection. We also determine the relation between the pairs (g, h) of conjugate minimal surfaces associated to a superconformal surface and its image by an inversion. In particular, this yields a new transformation for minimal surfaces in .     

Density Theorems for Complete Minimal Surfaces in {\mathbb{R}}^{3}

In this paper we have proved several approximation theorems for the family of minimal surfaces in that imply, among other things, that complete minimal surfaces are dense in the space of all minimal surfaces endowed with the topology of C ^k convergence on compact sets, for any . As a consequence of the above density result, we have been able to produce the first example of a complete proper minimal surface in with uncountably many ends. This research is partially supported by MEC-FEDER Grant no. MTM2004 - 00160.     

Explicit finite volume criteria for localization in continuous random media and applications

We give finite volume criteria for localization of quantum or classical waves in continuous random media. We provide explicit conditions, depending on the parameters of the model, for starting the bootstrap multiscale analysis. A simple application to Anderson Hamiltonians on the continuum yields localization at the bottom of the spectrum in an interval of size C for large , where stands for the disorder parameter. A more sophisticated application proves localization for two-dimensional random Schrödinger operators in a constant magnetic field (random Landau Hamiltonians) up to a distance from the Landau levels for large B, where B is the strength of the magnetic field.     

Chvátal closures for mixed integer programming problems

Chvátal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedronP and integral vectorw, if max(wx|x P, wx integer} =t, thenwx t is valid for all integral vectors inP. We consider the variant of this step where the requirement thatwx be integer may be replaced by the requirement that be integer for some other integral vector . The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedronP, the set of vectors that satisfy every cutting plane forP with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvátal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.Supported by Sonderforschungsbereich 303 (DFG) and by NSF Grant Number ECS-8611841.Supported by NSF Grant Number ECS-8418392 and Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, FR Germany.     

Local boundedness of the number of solutions of Plateau’s problem for polygonal boundary curves

In the present article, the author proves two generalizations of his “finiteness-result” (I.H.P. Anal. Non-lineaire, 2006, accepted) which states for any extreme simple closed polygon that every immersed, stable disc-type minimal surface spanning Γ is an isolated point of the set of all disc-type minimal surfaces spanning Γ w.r.t. the C ⁰-topology. First, it is proved that this statement holds true for any simple closed polygon in , provided it bounds only minimal surfaces without boundary branch points. Also requiring that the interior angles at the vertices of such a polygon Γ have to be different from the author proves the existence of some neighborhood O of Γ in and of some integer , depending only on Γ, such that the number of immersed, stable disc-type minimal surfaces spanning any simple closed polygon contained in O, with the same number of vertices as Γ, is bounded by .      

Preserving geometric properties of the exponential matrix by block Krylov subspace methods

Given a large square real matrix A and a rectangular tall matrix Q, many application problems require the approximation of the operation . Under certain hypotheses on A, the matrix preserves the orthogonality characteristics of Q; this property is particularly attractive when the associated application problem requires some geometric constraints to be satisfied. For small size problems numerical methods have been devised to approximate while maintaining the structure properties. On the other hand, no algorithm for large A has been derived with similar preservation properties. In this paper we show that an appropriate use of the block Lanczos method allows one to obtain a structure preserving approximation to when A is skew-symmetric or skew-symmetric and Hamiltonian. Moreover, for A Hamiltonian we derive a new variant of the block Lanczos method that again preserves the geometric properties of the exact scheme. Numerical results are reported to support our theoretical findings, with particular attention to the numerical solution of linear dynamical systems by means of structure preserving integrators. AMS subject classification (2000) 65F10, 65F30, 65D30     

Structure theorems for generalized random processes

Generalized random processes are classified by various types of continuity. Representation theorems of a generalized random process on {M _p } on a set with arbitrary large probability, as well as representations of a correlation operator of a generalized random process on {M _p } and L ^r (R), r > 1, are given. Especially, Gaussian generalized random processes are proven to be representable as a sum of derivatives of classical Gaussian processes with appropriate growth rate at infinity. Examples show the essence of all the proposed assumptions. In order to emphasize the differences in the concept of generalized random processes defined by various conditions of continuity, the stochastic differential equation y′(ω; t) = f(ω; t) is considered, where y is a generalized random process having a point value at t = 0 in the sense of Lojasiewicz. This paper was supported by the project Functional analysis, ODEs and PDEs with singularities, No. 144016, financed by the Ministry of Science, Republic of Serbia.     

Structures of polyhedra determined by submodular functions on crossing families

The present paper shows that for any submodular functionf on a crossing family with , if the polyhedron is nonempty, then there exist a unique distributive lattice with and a unique submodular function with such thatB(f) coincides with the base polyhedron associated with the submodular system . Here, iff is integer-valued, thenf ₁ is also integer-valued. Based on this fact, we also show the relationship between the independent-flow problem considered by the author and the minimum cost flow problem considered by J. Edmonds and R. Giles.     

Additive group actions on Danielewski varieties and the cancellation problem

Given complex algebraic varieties X and Y of the same dimension, the Cancellation Problem asks if an isomorphism between X  ×  and Y  ×  induces an isomorphism between X and Y. Iitaka and Fujita (J. Fac. Sci. Univ. 24:123–127, 1977) established that the answer is positive for a large class of varieties of any dimension. In 1989, Danielewski constructed a counterexample using smooth rational affine surfaces. His construction was further generalized by Fieseler (Comment. Math. Helvetici 69:5–27, 1994) and Wilkens (C.R. Acad. Sci. Paris Sér. I Math. 326(9):1111–1116, 1998) to describe a larger class of affine surfaces. Here we introduce higher-dimensional analogues of these surfaces. By studying algebraic actions of the additive group on certain of these varieties, we obtain new counterexamples to the Cancellation Problem in every dimension d ≥ 2.     

Algorithmic randomness of continuous functions

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L?f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.     

A quantitative weak law of large numbers and its application to the delta method

Let T _n be a statistic of the form T _n = f(), where is the samplemean of a sequence of independent random variables and f denotes a prescribed function taking values in a separable Banach space. In order to establish asymptotic expansions for bias and variance of T _n conventional theorems typically impose restrictive boundedness conditions upon f or its derivatives; moreover, these conditions are sufficient but not necessary. It is shown that a quantitative version of the weak law of large numbers is both sufficient and necessary for the accuracy of Taylor expansions of T _n . In particular, boundedness conditions may be replaced by mild requirements upon the global growth of f.      

Finiteness of the number of solutions of Plateau’s problem for polygonal boundary curves II

In this article, the author proves that a simple closed polygon can bound only finitely many immersed minimal surfaces of disc-type if it meets the following two requirements: firstly it has to bound only minimal surfaces without boundary branch points, and secondly its total curvature, i.e. the sum of the exterior angles at its N + 3 vertices, has to be smaller than 6π.