A transmission problem in the calculus of variations

We study hölder regularity of minimizers of the functional , wherep(x) takes only two values and jumps across a Lipschitz surface. No restriction on the two values is imposed.This article was processed by the author using the Springer-Verlag T_EX PJourlg macro package 1991.     

Sur le comportement asymptotique des potentiels d'une chaîne de Markov sur ℝ d

Résumé Dans cet article j'étudie le comportement à l'infini des potentiels des chaînes de Markov sur ^d (d3) proches du mouvement brownien, tout spécialement le cas des marches aléatoires, ainsi que des critères de transience et de récurrence inspirés de la méthode utilisée.

---

We study the asymptotic behaviour of potentials of Markov chains on ^d (d3), closed to Brownian motion, and particularly the case of random walks. Following a similar approach, we give transience and recurrence criteria.

     

Convergence of diagonally stationary sequences in convex optimization

LetX be a real normed linear space,f, f ⁿ, n , be extended real-valued proper closed convex functions onX. A sequence {x _n} inX is called diagonally stationary for {f ⁿ} if for alln there existsx* _n f ⁿ (x _n) such that x* _{n *} 0. Such sequences arise in approximation methods for the problem of minimizingf. Some general convergence results based upon variational convergence theory and appropriate equi-well-posedness are presented.     

On the Durrmeyer-type modification of some discrete approximation operators

In [10], for continuous functionsf from the domain of certain discrete operatorsL _n the inequalities are proved concerning the modulus of continuity ofL _nf. Here we present analogues of the results obtained for the Durrmeyer-type modification $\tilde L_n $ ofL _n. Moreover, we give the estimates of the rate of convergence of $\tilde L_n f$ in Hölder-type norms     

Surgery on 3-manifolds with \mathbb{S} 1-actions

We study the topological structure of all 3-manifolds obtained by surgery along principal fibers of a closed orientable -manifold. As a consequence, we give alternative proofs of some classical results due to W. Heil and L. Moser. Moreover, we completely specify the Seifert invariants for the considered manifolds. Finally we classify the manifolds obtained by surgery along certain Seifert links and determine geometric presentations of their fundamental groups.Work performed under the auspices of C.N.R. (National Research Council) of Italy and partially supported by Ministero della Ricerca Scientifica e Tecnologica within the projects Geometria Reale e Complessa and Topologia.     

The maximal monotonicity of the subdifferentials of convex functions: Simons' problem

In the paper we deal with the problem when the graph of the subdifferential operator of a convex lower semicontinuous function has a common point with the product of two convex nonempty weak and weak^* compact sets, i.e. when graph (Q × Q ^*) 0. The results obtained partially solve the problem posed by Simons as well as generalize the Rockafellar Maximal Monotonicity Theorem.     

On the interpolation property of some intuitionistic modal logics

LetL be one of the intuitionistic modal logics considered in [7] (or one of its extensions) and letM _L be the algebraic semantics ofL. In this paper we will extend toL the equivalence, proved in the classical case (see [6]), among he weak Craig interpolation theorem, the Robinson theorem and the amalgamation property of varietyM _L. We will also prove the equivalence between the Craig interpolation theorem and the super-amalgamation property of varietyM _L. Then we obtain the Craig interpolation theorem and Robinson theorem for two intuitionistic modal logics, one ofS ₄-type and the other one ofS ₅-type, showing the super-amalgamation property of the corresponding algebraic semantics.     

Inclusion-exclusion: Exact and approximate

It is often required to find the probability of the union of givenn eventsA ₁ ,...,A _n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A _i )= _i – _i<j Pr(A _i A _j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A _i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums _|S|=j Pr( _iS A _i ) forj=1,...k, approximates Pr(A _i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v _l ^m C _i is an instance of the general problem that had been extensively studied [7]. HereA _i is the set of assignments that satisfyC _i , and Pr( _iS A _i )=a _S /2ⁿ where _iS C _i is satisfied bya _S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa _S for, say, all cardinalities . Quite surprisingly, already the numbersa _S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

Norm-graphs and bipartite turán numbers

For everyt>1 and positiven we construct explicit examples of graphsG with |V (G)|=n, |E(G)|c _t ·n ^2–1/t which do not contain a complete bipartite graghK _t,t !+1 This establishes the exact order of magnitude of the Turán numbers ex (n, K _t,s ) for any fixedt and allst!+1, improving over the previous probabilistic lower bounds for such pairs (t, s). The construction relies on elementary facts from commutative algebra.Research supported in part by NSF Grants DMS-8707320 and DMS-9102866.Research supported in part by Hungarian National Foundation for Scientific Research Grant