An upper bound for the cardinality of ans-distance subset in real euclidean space

IfX is ans-distance subset inR ^d , then |X|<( _s ^d+s )+( _s-1 ^d+s-1 . Supported in part by NSF grant MCS—7903128 (OSURF 711977).     

Universal non-completely-continuous operators

A bounded linear operator between Banach spaces is calledcompletely continuous if it carries weakly convergent sequences into norm convergent sequences. Isolated is a universal operator for the class of non-completely-continuous operators fromL ₁ into an arbitrary Banach space, namely, the operator fromL ₁ into ⊆_∞ defined byT ₀(f) = (∫r _n f d μ) _n>-0, wherer _n is thenth Rademacher function. It is also shown that there does not exist a universal operator for the class of non-completely-continuous operators between two arbitrary Banach spaces. The proof uses the factorization theorem for weakly compact operators and a Tsirelson-like space. Supported in part by NSF grant DMS-9306460. Participant, NSF Workshop in Linear Analysis & Probability, Texas A&M University (supported in part by NSF grant DMS-9311902). Supported in part by NSF grant DMS-9003550.     

On the range of accretive operators

The solvability of the nonlinear operator equationw=x+Bx, whereB is accretive in a general Banach spaceX is studied by means of discrete approximations. In particular, ifB is continuous and everywhere defined an algorithm is given for solving the equation. Sponsored by the United States Army under Contract No. DAAG29-75-C-0024. Supported in part by NSF grant MCS 76-10227     

Multiple integration with respect to Poisson and Lévy processes

Summary Necessary and sufficient conditions are given for the existence of a multiple stochastic integral of the form ...fdX ₁...dX_d, where X ₁, ..., X _d are components of a positive or symmetric pure jump type Lévy process in _d. Conditions are also given for a sequence of integrals of this type to converge in probability to zero or infinity, or to be tight. All arguments proceed via reduction to the special case of Poisson integrals.Dedicated to Klaus Krickeberg on the occasion of his 60th birthdaySupported by NSF grant DMS-8703804Supported by NSF grant DMS-8713103     

Elliptic curves of odd modular degree

The modular degree m _E of an elliptic curve E/Q is the minimal degree of any surjective morphism X ₀(N) → E, where N is the conductor of E. We give a necessary set of criteria for m _E to be odd. In the case when N is prime our results imply a conjecture of Mark Watkins. As a technical tool, we prove a certain multiplicity one result at the prime p = 2, which may be of independent interest. Supported in part by the American Institute of Mathematics. Supported in part by NSF grant DMS-0401545.     

Graph theoretic techniques in algebraic geometry II: construction of singular complex surfaces of the rational cohomology type of CP2

Methods of graph theory are used to obtain rational projective surfaces with only rational double points as singularities and with rational cohomology rings isomorphic to that of the complex projective plane. Uniqueness results for such cohomologyCP ²'s and for rational and integral homologyCP ²'s are given in terms of the typesA _k,D _k, orE _k of singularities allowed by the construction. Supported in part by National Science Foundation grant no. MCS 77-03540.     

Commensurability invariants for nonuniform tree lattices

We study nonuniform lattices in the automorphism groupG of a locally finite simplicial treeX. In particular, we are interested in classifying lattices up to commensurability inG. We introduce two new commensurability invariants:quotient growth, which measures the growth of the noncompact quotient of the lattice; andstabilizer growth, which measures the growth of the orders of finite stabilizers in a fundamental domain as a function of distance from a fixed basepoint. WhenX is the biregular treeX _m,n, we construct lattices realizing all triples of covolume, quotient growth, and stabilizer growth satisfying some mild conditions. In particular, for each positive real numberν we construct uncountably many noncommensurable lattices with covolumeν. Supported in part by NSF grants DMS-9704640 and DMS-0244542. Supported in part by an NSF postdoctoral research fellowship.     

A class of quasilinear stochastic partial differential equations of McKean-Vlasov type with mass conservation

Summary A system ofN particles inR ^d with mean field interaction and diffusion is considered. Assuming adiabatic elimination of the momenta the positions satisfy a stochastic ordinary differential equation driven by Brownian sheets (microscopic equation), where all coefficients depend on the position of the particles and on the empirical mass distribution process. This empirical mass distribution process satisfies a quasilinear stochastic partial differential equation (SPDE). This SPDE (mezoscopic equation) is solved for general measure valued initial conditions by extending the empirical mass distribution process from point measure valued initial conditions with total mass conservation. Starting with measures with densities inL ₂(R ^d ,dr), wheredr is the Lebesgue measure, the solution will have densities inL ₂(R ^d ,dr) and strong uniqueness (in the Itô sense) is obtained. Finally, it is indicated how to obtain (macroscopic) partial differential equations as limits of the so constructed SPDE's.This research was supported by NSF grant DMS92-11438 and ONR grant N00014-91J-1386     

A Functional LIL for <Emphasis Type="Italic">d</Emphasis>-Dimensional Stable Processes; Invariance for Lévy- and Other Weakly Convergent Processes

We establish a functional LIL for the maximal process M(t) :=sup _0≤s≤t ‖X(s)‖ of an ℝ ^d -valued α-stable Lévy process X, provided X(1) has density bounded away from zero over some neighborhood of the origin. We also provide a broad invariance result governing a class independent-increment processes related to the domain of attraction of X(1). This breadth is particularly notable for two types of processes captured: First, it not only describes any partial sum process built from iid summands in the domain of normal attraction of X(1), but also addresses those with arbitrary iid summands in the full domain of attraction (here we give a technical condition necessary and sufficient for the partial sum process to share the exact LIL we prove for X). Second, it reveals that any Lévy process L such that L(1) satisfies the technical condition just mentioned will also share the LIL of X. Supported in part by NSF Grant DMS 02-05034.     

A topological approach to evasiveness

The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the graph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity Ω(v ²) wherev is the number of vertices. Karp conjectured that every such property is evasive, i.e., requires that every entry of the incidence matrix be examined. In this paper the truth of Karp’s conjecture is shown to follow from another conjecture concerning group actions on topological spaces. A special case of the conjecture is proved which is applied to prove Karp’s conjecture for the case of properties of graphs on a prime power number of vertices. Supported in part by an NSF postdoctoral fellowship Supported in part by NSF under grant No. MCS-8102248     

A random 1-011-011-01algorithm for depth first search

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is anRNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on aP-RAM. The run time of the algorithm isO(T _MM(n) log³ n), and the number of processors used isP _MM (n) whereT _MM(n) andP _MM(n) are the time and number of processors needed to find a minimum weight perfect matching on ann vertex graph with maximum edge weightn.This research was done while the first author was visiting the Mathematical Research Institute in Berkeley. Research supported in part by NSF grant 8120790.Supported by Air Force Grant AFOSR-85-0203A.     

Dimension versus size

We investigate the behavior of f(d), the least size of a lattice of order dimension d. In particular we show that the lattice of a projective plane of order n has dimension at least n/ln(n), so that f(d)=O(d) ² log² d. We conjecture f(d)=(d ² ), and prove something close to this for height-3 lattices, but in general we do not even know whether f(d)/d.Supported in part by NSF grant MCS 83-01867, AFORS grant number 0271 and a Sloan Research Fellowship.     

Illumination by translates of convex sets

Let S be a compact set in the plane. If every three points of S are illuminated clearly by some translate of the compact convex set T, then there is a translate of T which illumines every point of S. Various analogues hold for translates of flats in R ^das well.Supported in part by NSF grant DMS-8705336.     

On solving certain nonlinear partial differential equations by accretive operator methods

We use similar functional analytic methods to solve (a) a fully nonlinear second order elliptic equation, (b) a Hamilton-Jacobi equation, and (c) a functional/partial differential equation from plasma physics. The technique in each case is to approximate by the solutions of simpler problems, and then to pass to limits using a modification of G. Minty’s device to the spaceL ^∞. Alfred P. Sloan fellow 1979–1981. Supported in part by NSF grant MCS 77-01952.     

On the structure of certain excursions of a Markov process

Summary Let X be a Markov process and M a homogeneous random set. For t0, we set G _t=Sup{st: sM}. The stochastic dependence between the past and the future of G _Tis investigated for certain stopping times T. This gives some insight to recent results of Getoor concerning the excursion straddling t and the first excursion exceeding a in length.This research was supported in part by NSF grant MCS76-8023     

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m] ^d ={1,2,3,...,m} ^d that hits every combinatorial rectangle in [m] ^d of volume at least , i.e., every subset of [m] ^d the formR ₁×R ₂×...×R _d of size at least m ^d . The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute.     

Martingales with given maxima and terminal distributions

Let μ be any probability measure onR with λ |x|dμ(x)<∞, and let μ^* denote its associated Hardy and Littlewood maximal p.m. It is shown that for any p.m.v for which μ<ν<μ^* in the usual stochastic order, there is a martingale (X _t)_0≦t≦1 for which sup_0≦t≦1 X _t andX ₁ have respective p.m. 'sv and μ. The proof uses induction and weak convergence arguments; in special cases, explicit martingale constructions are given. These results provide a converse to results of Dubins and Gilat [6]; applications are made to give sharp martingale and ‘prophet’ inequalities. Supported in part by NSF grants DMS-86-01153 and DMS-88-01818.     

On the long edges in the shortest tour throughN random points

Consider the shortest tour throughn pointsX ₁,...,X _n independently uniformly distributed over [0,1]². Then we show that for some universal constantK, the number of edges of length at leastun ^–1/2 is at mostKnxp(–u)²/K)with overwhelmingprobability.This research is in part supported by an NSF grant.     

Combinatorial representation and convex dimension of convex geometries

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.Supported in part by NSF grant no. DMS-8501948.     

Finite-dimensional crystals B 2,s for quantum affine algebras of type D (1) n

The Kirillov–Reshetikhin modules W^r,s are finite-dimensional representations of quantum affine algebras U’_q labeled by a Dynkin node r of the affine Kac–Moody algebra and a positive integer s. In this paper we study the combinatorial structure of the crystal basis B^2,s corresponding to W^2,s for the algebra of type D⁽¹⁾_n. 2000 Mathematics Subject Classification Primary—17B37; Secondary—81R10 Supported in part by the NSF grants DMS-0135345 and DMS-0200774.