Dense graphs and edge reconstruction

By a well-known result of Nash-Williams if a graphG is not edge reconstructible, then for all ,|A||E(G)| mod 2 we have a permutation ofV(G) such thatE(G)E(G)=A. Here we construct infinitely many graphsG having this curious property and more than edges.Research (partially) supported by Hungarian National Foundation for Scientific Research Grant No.T016389.     

Generic continuity of restricted weak upper semi-continuous set-valued mappings

Set-valued mappings from a topological space into subsets of a Banach space which satisfy a restricted form of weak upper semi-continuity, have particularly noteworthy properties. We establish a selection theorem for certain set-valued mappings from a (-) unfavourable topological space into subsets of a Banach space and as a consequence derive the property that restricted weak upper semi-continuous set-valued mappings which satisfy a minimality condition, from a (-) unfavourable topological space into subsets of a Banach space are single-valued and norm upper semi-continuous at the points of a residual subset of their domain.     

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.     

Stability inL 1 of some integral operators

A class of Markov operators appearing in biomathematics is investigated. It is proved that these operators are asymptotic stable inL ¹, i.e. lim _n P ⁿ f=0 forfL ¹ and f(x) dx=0.     

Topological hochschild homology of extensions of ?/p? by polynomials, and of ?[x]/(xn) and ?[x]/(xn?1)

Topological Hochschild homology is calculated for the rings /p[x]/(f(x)) (where p is prime and f(x) /p[x] any polynomial), [x]/(x ⁿ) and [x]/(x ⁿ–1). A spectral sequence argument is used for calculating the homology of the topological Hochschild homology spectrum, from which its stable homotopy structure can be read off since the spectrum is known for a priori reasons to be a restricted product of Eilenberg-MacLane spectra.     

Fermionic stochastic differential equations and the index of Fredholm operators

The index of a Fredholm operator associated to a-summable Fredholm module is expressed in terms of the vacuum expectation value of a unitary operator-valued stochastic process which satisfies a stochastic differential equation with unbounded coefficients driven by fermion noise.     

Functional connectedness and Darboux property of multivalued functions

To 80^th birthday of Paul Erds     

On PP-rings

A ringR is called a leftPP-ring if every principal left ideal is projective, equivalently if the left annihilatorl(a) is generated by an idempotent for allaR. These rings seem first to have been discussed by Hattori [2] and examples include (von Neumann) regular rings and domains (possibly noncommutative). In this note we give a new characterization of leftPP-rings, use that to give an elementary proof of a result of Xue [4] characterizing triangularPP-rings, and then determine when the ringT _n (R) of upper triangular matrices overR is a leftPP-ring. Throughout the paper all rings have a unity and all modules are unitary.This research was supported by NSERC Grant A8075     

Semistable measures and limit theorems on real andp-adic groups

For any locally compact groupG, we show that any locally tight homomorphism from a real directed semigroup intoM ¹ (G) (semigroup of probability measures onG) has a shift which extends to a continuous one-parameter semigroup. IfG is ap-adic algebraic group then the above holds even iff is not locally tight. These results are applied to give sufficient conditions for embeddability of some translate of limits of sequences of the form {v _n ^kn } and M ¹ (G) such that ()= ^M , for somek>1 and AutG (cf. Theorems 2.1, 2.4, 3.7).     

On sets of integers with prescribed gaps

For a fixed setI of positive integers we consider the set of paths (p _o,...,p _k ) of arbitrary length satisfyingp _l –p _l–1I forl=2,...,k andp ₀=1,p _k =n. Equipping it with the uniform distribution, the random path lengthT _n is studied. Asymptotic expansions of the moments ofT _n are derived and its asymptotic normality is proved. The step lengthsp _l –p _l–1 are seen to follow asymptotically a restricted geometrical distribution. Analogous results are given for the free boundary case in which the values ofp ₀ andp _k are not specified. In the special caseI={m+1,m+2,...} (for some fixed m) we derive the exact distribution of a random m-gap subset of {1,...,n} and exhibit some connections to the theory of representations of natural numbers. A simple mechanism for generating a randomm-gap subset is also presented.