title: Closed ideals of the algebra of absolutely convergent Taylor series

abstract: Let $\Gamma$ be the unit circle, $A(\Gamma)$ the Wiener algebra of continuous functions whose series of Fourier coefficients are absolutely convergent, and $A^+$ the subalgebra of $A(\Gamma)$ of functions whose negative coefficients are zero. If $I$ is a closed ideal of $A^+$, we denote by $S_I$ the greatest common divisor of the inner factors of the nonzero elements of $I$ and by $I^A$ the closed ideal generated by $I$ in $A(\Gamma)$. It was conjectured that the equality $I^A= S_I H^\infty \cap I^A$ holds for every closed ideal $I$. We exhibit a large class $\scr F$ of perfect subsets of $\Gamma$, including the triadic Cantor set, such that the above equality holds whenever $h(I)\cap\Gamma\in\scr F$. We also give counterexamples to the conjecture.


title: A theory of characteristic currents associated with a singular connection

abstract: This note announces a general construction of characteristic currents for singular connections on a vector bundle. It develops, in particular, a Chern-Weil-Simons theory for smooth bundle maps $\alpha : E \rightarrow F$ which, for smooth connections on $E$ and $F$, establishes formulas of the type $$ \phi \ = \ \text{\rm Res}_{\phi}\Sigma_{\alpha} + dT. $$ Here $\phi$ is a standard charactersitic form, $\text{Res}_{\phi}$ is an associated smooth ``residue'' form computed canonically in terms of curvature, $\Sigma_{\alpha}$ is a rectifiable current depending only on the singular structure of $\alpha$, and $T$ is a canonical, functorial transgression form with coefficients in $\loc$. The theory encompasses such classical topics as: Poincar\'e-Lelong Theory, Bott-Chern Theory, Chern-Weil Theory, and formulas of Hopf. Applications include:\ \ a new proof of the Riemann-Roch Theorem for vector bundles over algebraic curves, a $C^{\infty}$-generalization of the Poincar\'e-Lelong Formula, universal formulas for the Thom class as an equivariant characteristic form (i.e., canonical formulas for a de Rham representative of the Thom class of a bundle with connection), and a Differentiable Riemann-Roch-Grothendieck Theorem at the level of forms and currents. A variety of formulas relating geometry and characteristic classes are deduced as direct consequences of the theory.


title: Alexander's and Markov's theorems in dimension four

abstract: Alexander's and Markov's theorems state that any link type in $R^3$ is represented by a closed braid and that such representations are related by some elementary operations called Markov moves. We generalize the notion of a braid to that in 4-dimensional space and establish an analogue of these theorems.


title: Open sets of diffeomorphisms having two attractors, each with an everywhere dense basin

abstract: We announce the discovery of a diffeomorphism of a three-dimensional manifold with boundary which has two disjoint attractors. Each attractor attracts a set of positive $3$-dimensional Lebesgue measure whose points of Lebesgue density are dense in the whole manifold. This situation is stable under small perturbations.


title: Selberg's Conjectures and Artin $L$-functions

abstract: The author reviews results and conjectures of Selberg on a class of Dirichlet series functions which share properties with the Riemann zeta function, and he relates this work to the theory of Artin L-functions.


title: A report on Wiles' Cambridge lectures

abstract: In lectures at the Newton Institute in June of 1993, Andrew Wiles announced a proof of a large part of the Taniyama-Shimura Conjecture and, as a consequence, Fermat's Last Theorem. This report for nonexperts discusses the mathematics involved in Wiles' lectures, including the necessary background and the mathematical history.


title: Diffeomorphisms of manifolds with finite fundamental group

abstract: We show that the group ${\Cal D}(M)$ of pseudoisotopy classes of diffeomorphisms of a manifold of dimension $\geq 5$ and of finite fundamental group is commensurable to an arithmetic group. As a result $\pi_0(\text{{\it Diff\,M}})$ is a group of finite type.


title: Extremal length estimates and product regions in Teichm\"uller space

abstract: We study the Teichm\"uller metric on the Teichm\"uller space of a surface of finite type, in regions where the injectivity radius of the surface is small. The main result is that in such regions the Teichm\"uller metric is approximated up to bounded additive distortion by the sup metric on a product of lower dimensional spaces. The main technical tool in the proof is the use of estimates of extremal lengths of curves in a surface based on the geometry of their hyperbolic geodesic representatives.


title: Acceleration of bouncing balls in external fields

abstract: We introduce two models, the Fermi-Ulam model in an external field and a one dimensional system of bouncing balls in an external field above a periodically oscillating plate. For both models we investigate the possibility of unbounded motion. In a special case the two models are equivalent.


title: Properties of the Class of Measure Separable Compact Spaces

abstract: We investigate properties of the class of compact spaces on which every regular Borel measure is separable. This class will be referred to as MS. We discuss some closure properties of MS, and show that some simply defined compact spaces, such as compact ordered spaces or compact scattered spaces, are in MS. Most of the basic theory for regular measures is true just in ZFC. On the other hand, the existence of a compact ordered scattered space which carries a non-separable (non-regular) Borel measure is equivalent to the existence of a real-valued measurable cardinal less or equal to c. We show that not being in MS is preserved by all forcing extensions which do not collapse omega_1, while being in MS can be destroyed even by a ccc forcing.


title: Remarks on aleph_1-metrizable not metrizable first countable spaces and CWH

abstract: CWH, CWN stand for collectionwise Hausdorff and collectionwise normal respectively. We analyze the statement "there is a lambda-CWH not CWH first countable (Hausdorff topological) space". We prove the existence of such a space under various conditions, show its equivalence to: there is a lambda-CWN not CWN first countable space and give an equivalent set theoretic statement; the nicest version we can obtain is in \S4. The author had a flawed proof of the existence of such spaces in ZFC, for some lambda > aleph_1, in June of 1992; still we decided that there is some interest in the correct part and some additions.


title: Co-elementary equivalence, co-elementary maps, and generalized arcs

abstract: By a {\bf generalized arc\/} we mean a continuum with exactly two non-separating points; an {\bf arc} is a metrizable generalized arc. It is well known that any two arcs are homeomorphic (to the real closed unit interval); we show that any two generalized arcs are co-elementarily equivalent, and that co-elementary images of generalized arcs are generalized arcs. We also show that if $f:X \to Y$ is a function between compact Hausdorff spaces and if $X$ is an arc, then $f$ is a co-elementary map if and only if $Y$ is an arc and $f$ is a monotone continuous surjection.


title: On the logical strength of Nash-Williams' theorem on transfinite sequences

abstract: We show that Nash-Williams' theorem asserting that the countable transfinite sequences of elements of a better-quasi-ordering ordered by embeddability form a better-quasi-ordering is provable in the subsystem of second order arithmetic Pi^1_1-CA_0 but is not equivalent to Pi^1_1-CA_0. We obtain some partial results towards the proof of this theorem in the weaker subsystem ATR_0 and we show that the minimality lemmas typical of wqo and bqo theory imply Pi^1_1-CA_0 and hence cannot be used in such a proof.


title: The basic sequence problem

abstract: We construct a quasi-Banach space $X$ which contains no basic sequence.


title: The existence of primitives for continuous functions in a quasi-Banach space

abstract: We show that if $X$ is a quasi-Banach space with trivial dual then every continuous function $f:[0,1]\to X$ has a primitive, answering a question of M.M. Popov.


title: Unconditional bases and unconditional finite-dimensional decompositions in Banach spaces

abstract: Let $X$ be a Banach space with an unconditional finite-dimensional Schauder decomposition $(E_n)$. We consider the general problem of characterizing conditions under which one can construct an unconditional basis for $X$ by forming an unconditional basis for each $E_n.$ For example, we show that if $\sup \dim E_n<\infty$ and $X$ has Gordon-Lewis local unconditional structure then $X$ has an unconditional basis of this type. We also give an example of a non-Hilbertian space $X$ with the property that whenever $Y$ is a closed subspace of $X$ with a UFDD $(E_n)$ such that $\sup\dim E_n<\infty$ then $Y$ has an unconditional basis, showing that a recent result of Komorowski and Tomczak-Jaegermann cannot be improved.


title: Isomorphic classification of atomic weak L^p spaces

abstract: Let $\msp$ be a measure space and let $1 < p < \infty$. The {\em weak $L^p$}\/ space $\wlp$ consists of all measurable functions $f$ such that \[ \|f\| = \sup_{t>0}t^{\frac{1}{p}}f^*(t) < \infty,\] where $f^*$ is the decreasing rearrangement of $|f|$. It is a Banach space under a norm which is equivalent to the expression above. In this paper, we pursue the problem of classifying weak $L^p$ spaces isomorphically when $\msp$ is purely atomic. It is also shown that if $\msp$ is a countably generated $\sigma$-finite measure space, then $\wlp$ (if infinite dimensional) must be isomorphic to either $\ell^\infty$ or $\seq$. The results of this article were presented at the conference in Columbia, Missouri in May, 1994.


title: The Askey-Wilson polynomials and q-Sturm-Lioville problems

abstract: We find the adjoint of the Askey-Wilson divided difference operator with respect to the inner procuct on L^2(-1,1,(1-x^2)^-1/2 dx) defined as a Cauchy principle value and show that the Askey-Wilson polynomials are solutions of a q-Sturm-Liouville problem. From these facts we deduce various properties of the polynomials in a simple and straightforward way. We also provide an operator theoretic description of the Askey-Wilson operator.


title: Fractional integration for Laguerre expansions

abstract: The aim of this note is to provide a fractional integration theorem in the framework of Laguerre expansions. The method of proof consists of establishing an asymptotic estimate for the involved kernel and then applying a method of Hedberg \cite{pro}. We combine this result with sufficient $(p,p)$ multiplier criteria of Stempak and Trebels \cite{ST}. The resulting sufficient $(p,q)$ multiplier criteria are comparable with necessary ones of Gasper and Trebels \cite{laguerre}.


title: On a restriction problem of de Leeuw type for Laguerre multipliers

abstract: In 1965 K. de Leeuw \cite{deleeuw} proved among other things in the Fourier transform setting: {\it If a continuous function $m(\xi _1, \ldots ,\xi _n)$ on ${\bf R}^n$ generates a bounded transformation on $L^p({\bf R}^n),\; 1\le p \le \infty ,$ then its trace $\tilde{m}(\xi _1, \ldots ,\xi _m)=m(\xi _1, \ldots ,\xi _m,0,\ldots ,0), \; m<n,$ generates a bounded transformation on $L^p({\bf R}^m)$. } In this paper, the analogous problem is discussed in the setting of Laguerre expansions of different orders.


title: On the convergence of the zeta function for certain prehomogeneous vector spaces

abstract: Let (G,V) be an irreducible prehomogeneous vector space defined over a number field k, P in k[V] a relative invariant polynomial, and X a rational character of G such that P(gx)=X(g)P(x). Let V_k^{ss}={x \in V_k such that P(x) is not equal to 0}. For x in V_k^{ss}, let G_x be the stabilizer of x, and G_x^0 the connected component of 1 of G_x. We define L_0 to be the set of x in V_k^{ss} such that G_x^0 does not have a non-trivial rational character. We study the zeta function for (G,V).


title: Almost free algebras

abstract: The essentially non-free spectrum is the class of uncountable cardinals kappa in which there is an essentially non-free algebra of cardinality kappa which is almost free. In L, the essentially non-free spectrum of a variety is entirely determined by whether or not the construction principle holds. In ZFC may be more complicated. For some varieties, such as groups, abelian groups or any variety of modules over a non-left perfect ring, the essentially non-free spectrum contains not only aleph_1 but aleph_n for all n>0. The reason for this being true in ZFC (rather than under some special set theoretic hypotheses) is that these varieties satisfy stronger versions of the construction principle. We conjecture that the hierarchy of construction principles is strict, i.e., that for each n>0 there is a variety which satisfies the n-construction principle but not the n+1-construction principle. In this paper we will show that the 1-construction principle does not imply the 2-construction principle. We prove that, assuming the consistency of some large cardinal hypothesis, it is consistent that a variety has an essentially non-free almost free algebra of cardinality aleph_n if and only if it satisfies the n-construction principle.


title: Martin's Axiom and Delta^2_1 well-ordering of the reals

abstract: Assuming an inaccessible cardinal kappa, there is a generic extension in which MA + 2^{aleph_0} = kappa holds and the reals have a Delta^2_1 well-ordering.


title: More forcing notions imply diamond

abstract: We prove that the Sacks forcing collapses the continuum onto the dominating number d, answering the question of Carlson and Laver. Next we prove that if a proper forcing of the size at most continuum collapses omega_2 then it forces diamond_{omega_1} .


title: Dual billiards, twist maps, and impact oscillators

abstract: In this paper techniques of twist map theory are applied to the annulus maps arising from dual billiards on a strictly convex closed curve G in the plane. It is shown that there do not exist invariant circles near G when there is a point on G where the radius of curvature vanishes or is discontinuous. In addition, when the radius of curvature is not $C^1$ there are examples with orbits that converge to a point of G. If the derivative of the radius of curvature is bounded, such orbits cannot exist. The final section of the paper concerns an impact oscillator whose dynamics are the same as a dual billiards map. The appendix is a remark on the connection of the inverse problems for invariant circles in billiards and dual billiards.


title: Some remarks on periodic billiard orbits in rational polygons

abstract: A polygon is called rational if the angle between each pair of sides is a rational multiple of $\pi.$ The main theorem we will prove is Theorem 1: For rational polygons, periodic points of the billiard flow are dense in the phase space of the billiard flow. This is a strengthening of Masur's theorem, who has shown that any rational polygon has ``many'' periodic billiard trajectories; more precisely, the set of directions of the periodic trajectories are dense in the set of velocity directions $\S^1.$ We will also prove some refinements of Theorem 1: the ``well distribution'' of periodic orbits in the polygon and the residuality of the points $q \in Q$ with a dense set of periodic directions.


title: OTTER Experiments in a System of Combinatory Logic

abstract: This paper describes some experiments involving the automated theorem-proving program OTTER in the system TRC of illative combinatory logic. We show how OTTER can be steered to find a contradiction in an inconsistent variant of TRC, and present some experimentally discovered identities in TRC.


title: Projective Stationary Sets and Strong Reflection Principle

abstract: We study projective stationary sets. The Projective Stationary Reflection principle is the statement that every projective stationary set contains an increasing continuous $\in$--chain of length $\omega_1$. We show that if Martin's Maximum holds, then the Projective Stationary Reflection Principle holds. Also it is equivalent to the Strong Reflection Principle. We show that the saturation of the nonstationary ideal on $\omega_1$ is equivalent to a certain kind of reflection.


title: Small forcings and Cohen reals

abstract: We prove it consistent relative to ZFC that all nontrivial forcings of size $\aleph _1$ add a Cohen real.


title: Infinite homogeneous bipartite graphs with unequal sides

abstract: We call a bipartite graph {\it homogeneous} if every finite partial automorphism which respects left and right can be extended to a total automorphism. A $(\kappa,{\lambda} )$ bipartite graph is a bipartite graph with left side of size $\kappa$ and right side of size ${\lambda}$. We show, using a theorem of Hrushovski on finite graphs, that there is a homogeneous $({\aleph_0},2^{\aleph_0} )$ bipartite graph of girth 4 (thus answering negatively a question by Kupitz and Perles), and that depending on the underlying set theory all homogeneous $({\aleph_0},\aleph_1)$ bipartite graphs may be isomorphic, or there may be $2^{\aleph_1}$ many isomorphism types of $(\aleph_0,\aleph_1)$ homogeneous graphs.


title: Homogeneous families and their automorphism groups

abstract: A homogeneous family of subsets over a given set is one with a very ``rich'' automorphism group. We prove the existence of a bi-universal element in the class of homogeneous families over a given infinite set and give an explicit construction of $2^\cont$ isomorphism types of homogeneous families over a countable set.


title: Universal bridge-free graphs

abstract: We prove that there is no countable universal $B_n$-free graph for all $n$ and that there is no countable universal graph in the class of graphs omitting all cycles of length at most $2k$ for $k\ge 2$.


title: Universal abelian groups

abstract: We examine the existence of universal elements in classes of infinite abelian groups. The main method is using group invariants which are defined relative to club guessing sequences. We prove, for example: Theorem: For $n\ge 2$, there is a purely universal separable $p$-group in $\aleph_n$ if, and only if, $\cont\le \aleph_n$.


title: Laurent coefficients and Ext of finite graded modules

abstract: Let $R=\bigoplus_{n\ges0}R_n$ be a graded commutative ring generated over a field $K=R_0$ by homogeneous elements $x_1,\dots,x_e$ of positive degrees $d_1,\dots,d_e$. The Hilbert-Serre Theorem shows that for each finite graded $R$--module $M=\bigoplus_{n\in\BZ}M_n$ the {\it Hilbert series\/} $\sum_{n\in\BZ}(\rank_K M_n)t^n$ is the Laurent expansion around $0$ of a rational function $$ H_M(t)=\frac{q_M(t)}{\prod_{i=1}^e(1-t^{d_i})} $$ with $q_M(t)\in\BZ[t,\ti]$. We demonstrate that Laurent expansions $\left[M\right]_z$ of $H_M(t)$ around other points $z$ of the extended complex plane $\overline\BC$ also carry important structural information.


title: A User's Guide to the Mapping Class Group: Once Punctured Surfaces

abstract: This document is a practical guide to computations using an automatic structure for the mapping class group of a once-punctured, oriented surface $S$. We describe a quadratic time algorithm for the word problem in this group, which can be implemented efficiently with pencil and paper. The input of the algorithm is a word, consisting of ``chord diagrams'' of ideal triangulations and elementary moves, which represents an element of the mapping class group. The output is a word called a ``normal form'' that uniquely represents the same group element.


title: Forced Lattice Vibrations -- A Videotext

abstract: We begin with a description of recent numerical and analytical results that are closely related to the results of this paper.


title: A Comparison of Continuously Controlled and Controlled K-theory

abstract: We define an unreduced version of the e-controlled lower $K$-theoretic groups of Ranicki and Yamasaki, and Quinn. We show that the reduced versions of our groups coincide (in the inverse limit and its first derived, $\lim^1$) with those of Ranicki and Yamasaki. We also relate the controlled groups to the continuously controlled groups of Anderson and Munkholm, and to the Quinn homology groups of Quinn.


title: Counting pairs of lattice paths by intersections

abstract: On an $r\times (n-r)$ lattice rectangle, we first consider walks that begin at the SW corner, proceed with unit steps in either of the directions E or N, and terminate at the NE corner of the rectangle. For each integer $k$ we ask for $N_k^{n,r}$, the number of {\em ordered\/} pairs of these walks that intersect in exactly $k$ points. The number of points in the intersection of two such walks is defined as the cardinality of the intersection of their two sets of vertices, excluding the initial and terminal vertices. We find two explicit formulas for the numbers $N_k^{n,r}$. Next we note that $N_1^{n,r}= 2 N_0^{n,r}$, i.e., that {\em exactly twice as many pairs of walks have a single intersection as have no intersection\/}. Such a relationship clearly merits a bijective proof, and we supply one. We discuss a number of related results for different assumptions on the two walks. We find the probability that two independent walkers on a given lattice rectangle do not meet. In this situation, the walkers start at the two points $(a,b+x+1)$ and (a+x+1,b)$ in the first quadrant, and walk West or South at each step, except that when a walker reaches the $x$-axis (resp. the $y$-axis) then all future steps are constrained to be South (resp. West) until the origin is reached. We find that if the probability $p(i,j)$ that a step from $(i,j)$ will go West depends only on $i+j$, then the probabilty that the two walkers do not meet until they reach the origin is the same as the probability that a single (unconstrained) walker who starts at $(a, b+x+1)$ and and takes $a+b+x$ steps, finishes at one of the points $(0,1), (-1,2), \ldots, (-x,1+x)$.


title: Inverting sets and the packing problem

abstract: Given a set $V$, a subset $S$, and a permutation $\pi$ of $V$, we say that $\pi$ permutes $S$ if $\pi (S) \cap S = \emptyset$. Given a collection $\cS = \{V; S_1,\ldots , S_m\}$, where $S_i \subseteq V ~~(i=1,\ldots ,m)$, we say that $\cS$ is invertible if there is a permutation $\pi$ of $V$ such that $\pi (S_i) \subseteq V-S_i$. In this paper, we present necessary and sufficient conditions for the invertibility of a collection and construct a polynomial algorithm which determines whether a given collection is invertible. For an arbitrary collection, we give a lower bound for the maximum number of sets that can be inverted. Finally, we consider the problem of constructing a collection of sets such that no sub-collection of size three is invertible. Our constructions of such collections come from solutions to the packing problem with unbounded block sizes. We prove several new lower and upper bounds for the packing problem and present a new explicit construction of packing.


title: Invertible families of sets of bounded degree

abstract: Let H = (H,V) be a hypergraph with edge set H and vertex set V. Then hypergraph H is invertible iff there exists a permutation pi of V such that for all E belongs to H(edges) intersection of(pi(E) and E)=0. H is invertibility critical if H is not invertible but every hypergraph obtained by removing an edge from H is invertible. The degree of H is d if |{E belongs to H(edges)|x belongs to E}| =< d for each x belongs to V Let i(d) be the maximum number of edges of an invertibility critical hypergraph of degree d. Theorem: i(d) =< (d-1) {2d-1 choose d} + 1. The proof of this result leads to the following covering problem on graphs: Let G be a graph. A family H is subset of (2^{V(G)} is an edge cover of G iff for every edge e of G, there is an E belongs to H(edge set) which includes e. H(edge set) is a minimal edge cover of G iff for H' subset of H, H' is not an edge cover of G. Let b(d) (c(d)) be the maximum cardinality of a minimal edge cover H(edge set) of a complete bipartite graph (complete graph) where H(edge set) has degree d. Theorem: c(d)=< i(d)=<b(d)=< c(d+1) and 3. 2^{d-1} - 2 =< b(d)=< (d-1) {2d-1choose d} +1. The proof of this result uses Sperner theory. The bounds b(d) also arise as bounds on the maximum number of elements in the union of minimal covers of families of sets.


title: Graph generated union-closed families of sets

abstract: Let G be a graph with vertices V and edges E. Let F be the union-closed family of sets generated by E. Then F is the family of subsets of V without isolated points. Theorem: There is an edge e belongs to E such that |{U belongs to F | e belongs to U}| =< 1/2|F|. This is equivalent to the following assertion: If H is a union-closed family generated by a family of sets of maximum degree two, then there is an $x$ such that |{U belongs to H | x belongs to U}| > 1/2|H|. This is a special case of the union-closed sets conjecture. To put this result in perspective, a brief overview of research on the union-closed sets conjecture is given. A proof of a strong version of the theorem on graph-generated families of sets is presented. This proof depends on an analysis of the local properties of F and an application of Kleitman's lemma. Much of the proof applies to arbitrary union-closed families and can be used to obtain bounds on |{U belongs to F | e belongs to U}|/|F|.


title: A geometric identity for Pappus' Theorem

abstract: An expression in the exterior algebra of a Peano space yielding Pappus' Theorem was originally given by Doubilet, Rota, and Stein. Motivated by an identity of Rota, we give an identity in a Grassmann-Cayley algebra of step 3, involving joins and meets alone, which expresses the Theorem of Pappus.


title: Restricted routing and wide diameter of the cycle prefix network

abstract: The cycle prefix network is a Cayley coset digraph based on sequences over an alphabet which has been proposed as a vertex symmetric communication network. This network has been shown to have many remarkable communication properties such as a large number of vertices for a given degree and diameter, simple shortest path routing, Hamiltonicity, optimal connectivity, and others. These considerations for designing symmetric and directed interconnection networks are well justified in practice and have been widely recognized in the research community. Among the important properties of a good network, efficient routing is probably one of the most important. In this paper, we further study routing schemes in the cycle prefix network. We confirm an observation first made from computer experiments regarding the diameter change when certain links are removed in the original network, and we completely determine the wide diameter of the network. The wide diameter of a network is now perceived to be even more important than the diameter. We show by construction that the wide diameter of the cycle prefix network is very close to the ordinary diameter. This means that routing in parallel in this network costs little extra time compared to ordinary single path routing.


title: The lattice of closure relations of a poset

abstract: In this paper we show that the set of closure relations on a finite poset P forms a supersolvable lattice, as suggested by Rota. Furthermore this lattice is dually isomorphic to the lattice of closed sets in a convex geometry (in the sense of Edelman and Jamison). We also characterize the modular elements of this lattice and compute its characteristic polynomial.


title: Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion

abstract: The correctness of most randomized distributed algorithms is expressed by a statement of the form ``some predicate of the executions holds with high probability, regardless of the order in which actions are scheduled''. In this paper, we present a general methodology to prove correctness statements of such randomized algorithms. Specifically, we show how to prove such statements by a series of refinements, which terminate in a statement independent of the schedule. To demonstrate the subtlety of the issues involved in this type of analysis, we focus on Rabin's randomized distributed algorithm for mutual exclusion [Rabin 82]. Surprisingly, it turns out that the algorithm does not maintain one of the requirements of the problem under a certain schedule. In particular, we give a schedule under which a set of processes can suffer lockout for arbitrary long periods.


title: Number of faults a system can withstand without repairs

abstract: We consider the following scheduling problem. A system is composed of $n$ processors drawn from a pool of $N$. The processors can become faulty while in operation and faulty processors never recover. A report is issued whenever a fault occurs. This report states only the existence of a fault, but does not indicate its location. Based on this report, the scheduler can reconfigure the system and choose another set of $n$ processors. The system operates satisfactorily as long as at most $f$ of the $n$ selected processors are faulty. We exhibit a scheduling strategy allowing the system to operate satisfactorily until approximately $(N/n)f$ faults are reported in the worst case. Our precise bound is tight.


title: Proving time bounds for randomized distributed algorithms

abstract: A method of analyzing time bounds for randomized distributed algorithms is presented, in the context of a new and general framework for describing and reasoning about randomized algorithms. The method consists of proving auxiliary statements of the form U (t)->(p) U', which means that whenever the algorithm begins in a state in set U, with probability p, it will reach a state in set U' within time t. The power of the method is illustrated by its use in proving a constant upper bound on the expected time for some process to reach its critical region, in Lehmann and Rabin's Dining Philosophers algorithm.


title: Spanning trees short or small

abstract: We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number $k$ of nodes are required to be connected in the solution. A prototypical example is the $k$MST problem in which we require a tree of minimum weight spanning at least $k$ nodes in an edge-weighted graph. We show that the $k$MST problem is NP-hard even for points in the Euclidean plane. We provide approximation algorithms with performance ratio $2\sqrt{k}$ for the general edge-weighted case and $O(k^{1/4})$ for the case of points in the plane. Polynomial-time exact solutions are also presented for the class of decomposable graphs which includes trees, series-parallel graphs, and bounded bandwidth graphs, and for points on the boundary of a convex region in the Euclidean plane. We also investigate the problem of finding short trees, and more generally, that of finding networks with minimum diameter. A simple technique is used to provide a polynomial-time solution for finding $k$-trees of minimum diameter. We identify easy and hard problems arising in finding short networks using a framework due to T. C. Hu.


title: On the minimum latency problem

abstract: We are given a set of points $p_1,\ldots , p_n$ and a symmetric distance matrix $(d_{ij})$ giving the distance between $p_i$ and $p_j$. We wish to construct a tour that minimizes $\sum_{i=1}^n \ell(i)$, where $\ell(i)$ is the {\em latency} of $p_i$, defined to be the distance traveled before first visiting $p_i$. This problem is also known in the literature as the {\em deliveryman problem} or the {\em traveling repairman problem}. It arises in a number of applications including disk-head scheduling, and turns out to be surprisingly different from the traveling salesman problem in character. We give exact and approximate solutions to a number of cases, including a constant-factor approximation algorithm whenever the distance matrix satisfies the triangle inequality.


title: An on-line algorithm for improving performance in navigation

abstract: Recent papers have shown optimally-competitive on-line strategies for a robot traveling from a point $s$ to a point $t$ in certain unknown geometric environments. We consider the question: Having gained some partial information about the scene on its first trip from $s$ to $t$, can the robot improve its performance on subsequent trips it might make? This is a type of on-line problem where a strategy must exploit {\em partial information \/} about the future (e.g., about obstacles that lie ahead). For scenes with axis-parallel rectangular obstacles where the Euclidean distance between $s$ and $t$ is $n$, we present a deterministic algorithm whose {\em average\/} trip length after $k$ trips, $k \leq n$, is $O(\rootnbyk)$ times the length of the shortest $s$-$t$ path in the scene. We also show that this is the best a deterministic strategy can do. This algorithm can be thought of as performing an optimal tradeoff between search effort and the goodness of the path found. We improve this algorithm so that for {\em every\/} $i \leq n$, the robot's $i$th trip length is $O(\rootnbyi)$ times the shortest $s$-$t$ path length. A key idea of the paper is that a {\em tree\/} structure can be defined in the scene, where the nodes are portions of certain obstacles and the edges are ``short'' paths from a node to its children. The core of our algorithms is an on-line strategy for traversing this tree optimally.


title: The complexity of approximating PSPACE-Complete problems for hierarchical specifications

abstract: We extend the concept of polynomial time approximation algorithms to apply to problems for hierarchically specified graphs, many of which are PSPACE-complete. Assuming P != PSPACE, the existence or nonexistence of such efficient approximation algorithms is characterized, for several standard graph theoretic and combinatorial problems. We present polynomial time approximation algorithms for several standard PSPACE-hard problems considered in the literature. In contrast, we show that unless P = PSPACE, there is no polynomial time epsilon-approximation for any epsilon>0, for several other problems, when the instances are specified hierarchically. We present polynomial time approximation algorithms for the following problems when the graphs are specified hierarchically: {minimum vertex cover}, {maximum 3SAT}, {weighted max cut}, {minimum maximal matching}, {bounded degree maximum independent set} In contrast, we show that unless P = PSPACE, there is no polynomial time epsilon-approximation for any epsilon>0, for the following problems when the instances are specified hierarchically: {the number of true gates in a monotone acyclic circuit when all input values are specified} and {the optimal value of the objective function of a linear program} It is also shown that unless P = PSPACE, a performance guarantee of less than 2 cannot be obtained in polynomial time for the following problems when the instances are specified hierarchically: {high degree subgraph}, {k-vertex connected subgraph}, and {k-edge connected subgraph}


title: Geometry based heuristics for unit disk graphs

abstract: Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring and minimum dominating set. We also present an on-line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and to intersection graphs of higher dimensional regular objects.


title: Numerical computation of real or complex elliptic integrals

abstract: Algorithms for numerical computation of symmetric elliptic integrals of all three kinds are improved in several ways and extended to complex values of the variables (with some restrictions in the case of the integral of the third kind). Numerical check values, consistency checks, and relations to Legendre's integrals and Bulirsch's integrals are included.


title: Painlev\'e equations for semi-classical recurrence coefficients

abstract: The title says it all.


title: The last of the hypergeometric continued fractions

abstract: A contiguous relation for complementry pairs of very well poised balanced ${}_{10}\phi_9$ basic hypergeometric functions is used to derive an explict expression for the associated continued fraction. This generalizes the continued fraction results associated with both Ramanujan's Entry 40 and Askey-Wilson polynomials which can be recovered as limits. Associated with our continued fraction results there are systems of biorthogonal rational functions that have yet to be derived.


title: On Jacobi and continuous Hahn polynomials

abstract: Jacobi polynomials are mapped onto the continuous Hahn polynomials by the Fourier transform and the orthogonality relations for the continuous Hahn polynomials then follow from the orthogonality relations for the Jacobi polynomials and the Parseval formula. In a special case this relation dates back to work by Bateman in 1933 and we follow a part of the historical development for these polynomials. Some applications of this relation are given.


title: Yet another basic analogue of Graf's addition formula

abstract: An identity involving basic Bessel functions and Al-Salam--Chihara polynomials is proved for which we recover Graf's addition formula for the Bessel function as the base $q$ tends to $1$. The corresponding product formula is derived. Some known identities for Jackson's $q$-Bessel functions are obtained as limiting cases. As special cases we prove identities for $q$-Charlier polynomials.


title: Quasi-projections in Teichm\"uller space

abstract: We consider a geometric property of the closest-points projection to a geodesic in Teichm\"uller space: the projection is called contracting if arbitrarily large balls away from the geodesic project to sets of bounded diameter. (This property always holds in negatively curved spaces.) It is shown here to hold if and only if the geodesic is precompact, i.e. its image in the moduli space is contained in a compact set. Some applications are given, e.g. to stability properties of certain quasi-geodesics in Teichm\"uller space, and to estimates of translation distance for pseudo-Anosov maps.


title: Cardinal invariants concerning functions whose sum is almost continuous

abstract: A function f from reals to reals (f:R->R) is almost continuous (in the sense of Stallings) iff every open set in the plane which contains the graph of f contains the graph of a continuous function. Natkaniec showed that for any family F of continuum many real functions there exists g:R->R such that f+g is almost continuous for every f in F. Let AA be the smallest cardinality of a family F of real functions for which there is no g:R->R with the property that f+g is almost continuous for every f in F. Thus Natkaniec showed that AA is strictly greater than the continuum. He asked if anything more could be said. We show that the cofinality of AA is greater than the continuum, c. Moreover, we show that it is pretty much all that can be said about AA in ZFC, by showing that AA can be equal to any regular cardinal between c^+ and 2^c (with 2^c arbitrarily large). We also show that AA = AD where AD is defined similarly to AA but for the class of Darboux functions. This solves another problem of Maliszewski and Natkaniec.


title: Explicit Formulas for the Waldspurger and Bessel Models

abstract: In this paper we will study certain models of irreducible admissible representations of the split special orthogonal group $SO(2n+1)$ over a nonarchimedean local field. If $n=1$, these models were considered by Waldspurger. If $n=2$, they were considered by Novodvorsky and Piatetski-Shapiro \cite{NP}, who called them {\it Bessel models}. They arise from a variety of Rankin-Selberg integrals nad the resultos of this paper will naturally have applications to the study of L-functions. They also arise in the study of the theta correspondence between $SO(2n+1)$ and the double cover of $Sp(2n)$, and they will therefore be of importance in generalizing the work of Waldspurger. As a global application we consider the Eisenstein series on $SO(2n+1)$ formed with a cuspidal automorphic representation $\pi$ on $GL(n)$, and we show that its Bessel period (6.2) is essentially a product of L-series. This generalizes work of B\"ocherer and Mizumoto.


title: Nowhere Weak Differentiability of the Pettis Integral

abstract: For an arbitrary infinite-dimensional Banach space $\X$, we construct examples of strongly-measurable $\X$-valued Pettis integrable functions whose indefinite Pettis integrals are nowhere weakly differentiable; thus, for these functions the Lebesgue Differentiation Theorem fails rather spectacularly. We also relate the degree of nondifferentiability of the indefinite Pettis integral to the cotype of $\X$, from which it follows that our examples are reasonably sharp. This is an expanded version of a previously posted paper with the same name.


title: Complemented copies of $\ell^1$ and Pelczynski's property (V*) in Bochner function spaces

abstract: Let $X$ be a Banach space and $(f_n)_n$ be a bounded sequence in $L^1(X)$. We prove a complemented version of the celebrated Talagrand's dichotomy i.e we show that if $(e_n)_n$ denotes the unit vector basis of $c_0$, there exists a sequence $g_n \in \text{conv}(f_n,f_{n+1},\dots)$ such that for almost every $\omega$, either the sequence $(g_n(\omega) \otimes e_n)$ is weakly Cauchy in $X \widehat{\otimes}_\pi c_0$ or it is equivalent to the unit vector basis of $\ell^1$. We then get a criterion for a bounded sequence to contain a subsequence equivalent to a complemented copy of $\ell^1$ in $L^1(X)$. As an application, we show that for a Banach space $X$, the space $L^1(X)$ has Pe\l czy\'nski's property $(V^*)$ if and only if $X$ does.


title: Pelczynski's property (V) on spaces of vector valued functions

abstract: Let $E$ be a separable Banach space and $\Omega$ be a compact Hausdorff space. It is shown that the space $C(\Omega,E)$ has property (V) if and only if $E$ does. Similar result is also given for Bochner spaces $L^p(\mu,E)$ if $1<p<\infty$ and $\mu$ is a finite Borel measure on $\Omega$.


title: Graph-Based Logic and Sketches 1: The General Framework

abstract: Traditional treatments of formal logic provide: 1. A syntax for formulas. 2. An inference relation between sets of formulas. 3. A rule for assigning meaning to formulas (semantics) that is sound with respect to the inference relation. First order logic, the logic and semantics of programming languages, and the languages that have been formulated for various kinds of categories are all commonly described in this way. The formulas in those logics are strings of symbols that are ultimately modeled on the sentences mathematicians speak and write when proving theorems. Mathematicians with a categorial orientation frequently state and prove theorems using graphs and diagrams. The theory of sketches provides a formal way to describe mathematical structures and impose requirements (such as equations) on them using graphs, diagrams and similar structures. The graphs, diagrams and other data of a sketch are formal objects that correspond to the graphs and diagrams used by such mathematicians in much the same way as the formulas of traditional logic correspond to the sentences mathematicians use in proofs. Sketch theory has a well-known and well-developed functorial semantics corresponding to item 3 in the description of logic above. The content of this paper is to propose a structure in sketch theory that corresponds to items 1 and 2 in that description.


title: Matrix Vieta Theorem

abstract: We consider generalizations of the Vieta formula (relating the coefficients of an algebraic equation to the roots) to the case of equations whose coefficients are order-$k$ matrices. Specifically, we prove that if $X_1,\dots ,X_n$ are solutions of an algebraic matrix equation $X^n+A_1X^{n-1}+\dots +A_n=0,$ independent in the sense that they determine the coefficients $A_1,\dots ,A_n$, then the trace of $A_1$ is the sum of the traces of the $X_i$, and the determinant of $A_n$ is, up to a sign, the product of the determinants of the $X_i$. We generalize this to arbitrary rings with appropriate structures. This result is related to and motivated by some constructions in non-commutative geometry.


title: Three-dimensional alpha shapes

abstract: Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the ``shape'' of the set. For that purpose, this paper introduces the formal notion of the family of $\alpha$-shapes of a finite point set in $\Real^3$. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter $\alpha \in \Real$ controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size $n$ in time $O(n^2)$, worst case. A robust implementation of the algorithm is discussed and several applications in the area of scientific computing are mentioned.


title: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

abstract: This paper describes a general-purpose programming technique, called the Simulation of Simplicity, which can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task to provide a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than those that do not use it. We believe that this technique will become a standard tool in writing geometric software.


title: Optimal pooling designs with error detection

abstract: Consider a collection of objects, some of which may be `bad', and a test which determines whether or not a given sub-collection contains no bad objects. The non-adaptive pooling (or group testing) problem involves identifying the bad objects using the least number of tests applied in parallel. The `hypergeometric' case occurs when an upper bound on the number of bad objects is known {\em a priori}. Here, practical considerations lead us to impose the additional requirement of {\em a posteriori} confirmation that the bound is satisfied. A generalization of the problem in which occasional errors in the test outcomes can occur is also considered. Optimal solutions to the general problem are shown to be equivalent to maximum-size collections of subsets of a finite set satisfying a union condition which generalizes that considered by Erd\"os \etal \cite{erd}. Lower bounds on the number of tests required are derived when the number of bad objects is believed to be either 1 or 2. Steiner systems are shown to be optimal solutions in some cases.


title: A simple linear-time algorithm for finding path-decompositions of small width

abstract: We described a simple algorithm running in linear time for each fixed constant $k$, that either establishes that the pathwidth of a graph $G$ is greater than $k$, or finds a path-decomposition of $G$ of width at most $O(2^{k})$. This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.


title: Mean values of Dedekind sums

abstract: For a positive integer k and an arbitrary integer h, the Dedekind sum s(h,k) was first studied by Dedekind because of the prominent role it plays in the transformation theory of the Dedekind eta-function, which is a modular form of weight 1/2 for the full modular group SL_2(Z). There is an extensive literature about the Dedekind sums. Rademacher [8] has written an introductory book on the subject.


title: An isoperimetric inequality related to Thue's equation

abstract: This paper announces the discovery of an isoperimetric inequality for the area of plane regions defined by binary forms. This result has been applied subsequently in the enumeration of solutions to the Thue inequality and, given its fundamental nature, may find application in other areas as well.


title: The moment map for a multiplicity free action

abstract: Let $K$ be a compact connected Lie group acting unitarily on a finite-dimensional complex vector space $V$. One calls this a {\em multiplicity-free} action whenever the $K$-isotypic components of $\C[V]$ are $K$-irreducible. We have shown that this is the case if and only if the moment map $\tau:V\rightarrow\k^*$ for the action is finite-to-one on $K$-orbits. This is equivalent to a result concerning \gp s associated with Heisenberg groups that is motivated by the Orbit Method. Further details of this work will be published elsewhere.


title: Exceptional surgery on knots

abstract: Let $M$ be an irreducible, compact, connected, orientable 3-manifold whose boundary is a torus. We show that if $M$ is hyperbolic, then it admits at most six finite/cyclic fillings of maximal distance 5. Further, the distance of a finite/cyclic filling to a cyclic filling is at most 2. If $M$ has a non-boundary-parallel, incompressible torus and is not a generalized 1-iterated torus knot complement, then there are at most three finite/cyclic fillings of maximal distance 1. Further, if $M$ has a non-boundary-parallel, incompressible torus and is not a generalized 1- or 2-iterated torus knot complement and if $M$ admits a cyclic filling of odd order, then $M$ does not admit any other finite/cyclic filling. Relations between finite/cyclic fillings and other exceptional fillings are also discussed.


title: Zeta functions do not determine class numbers

abstract: We show that two number fields with the same zeta function, and even with isomorphic adele rings, do not necessarily have the same class number.


title: Singular continuous spectrum is generic

abstract: In a variety of contexts, we prove that singular continuous spectrum is generic in the sense that for certain natural complete metric spaces of operators, those with singular spectrum are a dense $G_\delta$.


title: On the geometric and topological rigidity of hyperbolic 3-manifolds

abstract: A homotopy equivalence between a hyperbolic 3-manifold and a closed irreducible 3-manifold is homotopic to a homeomorphsim provided the hyperbolic manifold satisfies a purely geometric condition. There are no known examples of hyperbolic 3-manifolds which do not satisfy this condition.


title: Configuration spaces and the space of rational curves on a toric variety

abstract: The space of holomorphic maps from $S^2$ to a complex algebraic variety $X$, i.e. the space of parametrized rational curves on $X$, arises in several areas of geometry. It is a well known problem to determine an integer $n(D)$ such that the inclusion of this space in the corresponding space of continuous maps induces isomorphisms of homotopy groups up to dimension $n(D)$, where $D$ denotes the homotopy class of the maps. The solution to this problem is known for an important but special class of varieties, the generalized flag manifolds: such an integer may be computed, and $n(D)\to\infty$ as $D\to\infty$. We consider the problem for another class of varieties, namely, toric varieties. For smooth toric varieties and certain singular ones, $n(D)$ may be computed, and $n(D)\to\infty$ as $D\to\infty$. For other singular toric varieties, however, it turns out that $n(D)$ cannot always be made arbitrarily large by a suitable choice of $D$.


title: The flag-transitive tilde and Petersen-type geometries are all known

abstract: We announce the classification of two related classes of flag-transitive geometries. There is an infinite family of such geometries, related to the nonsplit extensions $3^{[{n\atop 2}]_{_2}}\cdot \SP_{2n}(2)$, and twelve sporadic examples coming from the simple groups $M_{22}$, $M_{23}$, $M_{24}$, $He$, $Co_1$, $Co_2$, $J_4$, $BM$, $M$ and the nonsplit extensions $3\cdot M_{22}$, $3^{23}\cdot Co_2$, and $3^{4371}\cdot BM$.


title: Frontiers in complex dynamics

abstract: Rational maps on the Riemann sphere occupy a distinguished niche in the general theory of smooth dynamical systems. First, rational maps are complex-analytic, so a broad spectrum of techniques can contribute to their study (quasiconformal mappings, potential theory, algebraic geometry, etc.). The rational maps of a given degree form a finite-dimensional manifold, so exploration of this {\em parameter space} is especially tractable. Finally, some of the conjectures once proposed for {\em smooth} dynamical systems (and now known to be false) seem to have a definite chance of holding in the arena of rational maps. In this article we survey a small constellation of such conjectures centering around the density of {\em hyperbolic} rational maps --- those which are dynamically the best behaved. We discuss some of the evidence and logic underlying these conjectures, and sketch recent progress towards their resolution.


title: A general decomposition theory for random cascades

abstract: This announcement describes a probabilistic approach to cascades which, in addition to providing an entirely probabilistic proof of the Kahane-Peyri\`ere theorem for independent cascades, readily applies to general dependent cascades. Moreover, this unifies various seemingly disparate cascade decompositions, including Kahane's T-martingale decomposition and dimension disintegration.


title: Forcing of periodic orbits for interval maps and renormalization of piecewise affine maps

abstract: We prove that for continuous maps on the interval, the existence of an n-cycle, implies the existence of n-1 points which interwind the original ones and are permuted by the map. We then use this combinatorial result to show that piecewise affine maps (with no zero slope) cannot be infinitely renormalizable.


title: Symmetries of plane partitions and the permanent-determinant method

abstract: In the paper [J. Combin. Theory Ser. A 43 (1986), 103--113], Stanley gives formulas for the number of plane partitions in each of ten symmetry classes. This paper together with results by Andrews [J. Combin. Theory Ser. A 66 (1994), 28-39] and Stembridge [Adv. Math 111 (1995), 227-243] completes the project of proving all ten formulas. We enumerate cyclically symmetric, self-complementary plane partitions. We first convert plane partitions to tilings of a hexagon in the plane by rhombuses, or equivalently to matchings in a certain planar graph. We can then use the permanent-determinant method or a variant, the Hafnian-Pfaffian method, to obtain the answer as the determinant or Pfaffian of a matrix in each of the ten cases. We row-reduce the resulting matrix in the case under consideration to prove the formula. A similar row-reduction process can be carried out in many of the other cases, and we analyze three other symmetry classes of plane partitions for comparison.


title: Propagation of Gevrey Regularity for a Class of Hypoelliptic Equations

abstract: We prove results on the propagation of Gevrey and analytic wave front sets for a class of $C^\infty$ hypoelliptic equations with double characteristics.


title: Global (and Local) Analyticity for Second Order Operators Constructed from Rigid Vector Fields on Products of Tori

abstract: We prove global analytic hypoellipticity on a product of tori for partial differential operators which are constructed as rigid (variable coefficient) quadratic polynomials in real vector fields satisfying the H\"ormander condition and where $P$ satisfies a `maximal' estimate. We also prove an analyticity result that is local in some variables and global in others for operators whose prototype is $$ P= \left({\partial \over {\partial x_1}}\right)^2 + \left({\partial \over {\partial x_2}}\right)^2 + \left(a(x_1,x_2){\partial \over {\partial t}}\right)^2.$$ (with analytic $a(x), a(0)=0,$ naturally, but not identically zero). The results, because of the flexibility of the methods, generalize recent work of Cordaro and Himonas in \cite{Cordaro-Himonas 1994} and Himonas in \cite{Himonas 199X} which showed that certain operators known not to be locally analytic hypoelliptic (those of Baouendi and Goulaouic \cite{Baouendi-Goulaouic 1971}, Hanges and Himonas \cite{Hanges-Himonas 1991}, and Christ \cite{Christ 1991a}) were {\it globally} analytic hypoelliptic on products of tori.


title: Regular Cocycles and Biautomatic Structures

abstract: Let $E$ be a virtually central extension of the group $G$ by a finitely generated abelian group $A$. We show that $E$ carries a biautomatic structure if and only if $G$ has a biautomatic structure $L$ for which the cohomology class of the extension is represented by an $L$-regular cocycle. Moreover, a cohomology class is $L$-regular if some multiple of it is or if its restriction to some finite index subgroup is. We also show that the entire second cohomology of a Fuchsian group is regular, so any virtually central extension is biautomatic. In particular, if the fundamental group of a Seifert fibered 3-manifold is not virtually nilpotent then it is biautomatic. ECHLPT had shown automaticity in this case and in an unpublished 1992 preprint Gersten constructed a biautomatic structure for circle bundles over hyperbolic surfaces and asked if the same could be done for these Seifert fibered 3-manifolds.


title: The structure of branching in Anosov flows of 3-manifolds

abstract: In this article we study the topological structure of the lifts to the universal of the stable and unstable foliations of $3$-dimensional Anosov flows. In particular we consider the case when these foliations do not have Hausdorff leaf space. We completely determine the structure of the set of non separated leaves from a given leaf in one of these foliations. As a consequence of this suspensions are characterized, up to topological conjugacy, as the only $3$-dimensional Anosov flows without freely homotopic closed orbits. Furthermore the structure of branching is related to the topology of the manifold: if there are infinitely many leaves not separated from each other, then there is an incompressible torus transverse to the flow. Transitivity is not assumed for these results. Finally, if the manifold has negatively curved fundamental group we derive some important properties of the limit sets of leaves in the universal cover.


title: Souslin's Hypothesis and Convergence in Category

abstract: A sequence of functions f_n: X -> R from a Baire space X to the reals is said to converge in category iff every subsequence has a subsequence which converges on all but a meager set. We show that if there exists a Souslin Tree then there exists a nonatomic Baire space X such that every sequence which converge in category converges everywhere on a comeager set. This answers a question of Wagner and Wilczynski, Convergence of sequences of measurable functions, Acta Math Acad Sci Hung 36(1980), 125-128.


title: Measurability of functions with approximately continuous vertical sections and measurable horizontal sections

abstract: A function f:R -> R is approximately continuous iff it is continuous in the density topology, i.e., for any ordinary open set U the set E=f^{-1}(U) is measurable and has Lebesgue density one at each of its points. Denjoy proved that approximately continuous functions are Baire 1., i.e., pointwise For any f:R^2 -> R define f_x(y) = f^y(x) = f(x,y). A function f:R^2 -> R is separately continuous if f_x and f^y are continuous for every x,y in R. Lebesgue in his first paper proved that any separately continuous function is Baire 1. Sierpinski showed that there exists a nonmeasurable f:R^2 -> R which is separately Baire 1. In this paper we prove: Thm 1. Let f:R^2 -> R be such that f_x is approximately continuous and f^y is Baire 1 for every x,y in R. Then f is Baire 2. Thm 2. Suppose there exists a real-valued measurable cardinal. Then for any function f:R^2 -> R and countable ordinal i, if f_x is approximately continuous and f^y is Baire i for every x,y in R, then f is Baire i+1 as a function of two variables. Thm 3. (i) Suppose that R can be covered by omega_1 closed null sets. Then there exists a nonmeasurable function f:R^2 -> R such that f_x is approximately continuous and f^y is Baire 2 for every x,y in R. (ii) Suppose that R can be covered by omega_1 null sets. Then there exists a nonmeasurable function f:R^2 -> R such that f_x is approximately continuous and f^y is Baire 3 for every x,y in R. Thm 4. In the random real model for any function f:R^2 -> R if f_x is approximately continuous and f^y is measurable for every x,y in R, then f is measurable as a function of two variables.


title: Large ordinals

abstract: Let $j$ be an elementary embedding of $V_{\lambda}$ into $V_{\lambda}$ that is not the identity, and let $\kappa$ be the critical point of $j$. Let $\Cal A$ be the closure of $\{j\}$ under the operation $a (b)$ of application, and let $\Omega$ be the closure of $\{\kappa\}$ under the operation $\min \{\xi: a(\xi) \ge b(\alpha)\}$. We give a complete description of the set $\Omega$ under an assumption (Threshold Hypothesis) on cyclic left distributive algebras.


title: Semi-Cohen Versus Cohen Algebras

abstract: We show that there are semi-Cohen Boolean algebras which cannot be completely embedded into Cohen Boolean algebras. Using the ideas from this proof, we give a simpler argument for a theorem of S. Koppelberg and S. Shelah, stating that there are complete subalgebras of Cohen algebras which are not Cohen themselves.


title: Analogs of Gr\"obner Bases in Polynomial Rings over a Ring

abstract: In this paper we will define analogs of Gr\"obner bases for $R$-subalgebras and their ideals in a polynomial ring $R[x_1,\ldots,x_n]$ where $R$ is a noetherian integral domain with multiplicative identity and in which we can determine ideal membership and compute syzygies. The main goal is to present and verify algorithms for constructing these Gr\"obner basis counterparts. As an application, we will produce a method for computing generators for the first syzygy module of a subset of an $R$-subalgebra of $R[x_1,\ldots,x_n]$ where each coordinate of each syzygy must be an element of the subalgebra.


title: Isometries of Hilbert space valued function spaces

abstract: Let $X$ be a (real or complex) rearrangement-in\-va\-riant function space on $\Om$ (where $\Om = [0,1]$ or $\Om \subseteq \bbN$) whose norm is not proportional to the $L_2$-norm. Let $H$ be a separable Hilbert space. We characterize surjective isometries of $X(H).$ We prove that if $T$ is such an isometry then there exist Borel maps $a:\Om\to\bbK$ and $\sigma:\Om\lra\Om$ and a strongly measurable operator map $S$ of $\Om$ into $\calB(H)$ so that for almost all $\om$ $S(\om)$ is a surjective isometry of $H$ and for any $f\in X(H)$ $$Tf(\om)=a(\om)S(\om)(f(\sigma(\om))) \text{ a.e.}$$ As a consequence we obtain a new proof of characterization of surjective isometries in complex rearrangement-invariant function spaces.


title: The Structure and Enumeration of Link Projections

abstract: We define a decomposition of link projections whose pieces we call atoroidal graphs. We describe a surgery operation on these graphs and show that all atoroidal graphs can be generated by performing surgery repeatedly on a family of well known link projections. This gives a method of enumerating atoroidal graphs and hence link projections by recomposing the pieces of the decomposition.


title: The Dimension of the Space of Cusp Forms of Weight One

abstract: A new upper bound is given for the dimension of the space of holomorphic cusp forms of weight one and prime level $q$: $$ \hbox{dim}\, S_1(q) << q^{11/12} \log^4{q} $$ with an absolute implied constant.


title: On Calculations of Zeros of Various L-functions

abstract: As we have shown several years ago [Y2], zeros of $L(s, \Delta )$ and $L^(2)(s, \Delta )$ can be calculated quite efficiently by a certain experimental method. Here $\Delta$ denotes the cusp form of weight 12 with respect to SL$(2, Z)$ and $L(s, \Delta )$ (resp. $L^(2)(s, \Delta )$) denotes the standard (resp. symmetric square) $L$-function attached to $\Delta$. The purpose of this paper is to show that this method can be applied to a wide class of $L$-functions so that we can obtain precise numerical values of their zeros.


title: Conformal Characters and Theta Series

abstract: We describe the construction of vector valued modular forms transforming under a given congruence representation of the modular group SL$(\bold Z)$ in terms of theta series. We apply this general setup to obtain closed and easily computable formulas for conformal characters of rational models of $W$-algebras.


title: Tiling a rectangle with the fewest squares

abstract: We show that a square-tiling of a $p\times q$ rectangle, where $p$ and $q$ are relatively prime integers, has at least $\log_2p$ squares. If $q>p$ we construct a square-tiling with less than $q/p+C\log p$ squares of integer size, for some universal constant $C$.


title: A note on tiling with integer-sided rectangles

abstract: We show how to determine if a given simple rectilinear polygon can be tiled with rectangles, each having an integer side.


title: Eigenfunctions on the Finite Poincar\'e Plane

abstract: Let $F$ be a finite field of odd number of elements. Let $F(\sqrt{\delta})$ be its quadratic extension. $F(\sqrt{\delta})-F$ is the so-called finite Poincare plane. This paper relates the bases of eigenfunctions constructed by Evans and by Kuang. The finite Poincare plane can be viewed as a Ramanujan graph. This paper also provides evidence for Terras' conjecture regarding the asymptotic distribution of the eigenvalus of the adjacency matrices.


title: New large graphs with given degree and diameter

abstract: In this paper we give graphs with the largest known order for a given degree $\Delta$ and diameter $D$. The graphs are constructed from Moore bipartite graphs by replacement of some vertices by adequate structures. The paper also contains the latest version of the $(\Delta, D)$ table for graphs.


title: Lower bounds for identifying subset members with subset queries

abstract: An instance of a group testing problem is a set of objects $\cO$ and an unknown subset $P$ of $\cO$. The task is to determine $P$ by using queries of the type ``does $P$ intersect $Q$'', where $Q$ is a subset of $\cO$. This problem occurs in areas such as fault detection, multiaccess communications, optimal search, blood testing and chromosome mapping. Consider the two stage algorithm for solving a group testing problem. In the first stage a predetermined set of queries are asked in parallel and in the second stage, $P$ is determined by testing individual objects. Let $n=\cardof{\cO}$. Suppose that $P$ is generated by independently adding each $x\in \cO$ to $P$ with probability $p/n$. Let $q_1$ ($q_2$) be the number of queries asked in the first (second) stage of this algorithm. We show that if $q_1=o(\log(n)\log(n)/\log\log(n))$, then $\Exp(q_2) = n^{1-o(1)}$, while there exist algorithms with $q_1 = O(\log(n)\log(n)/\log\log(n))$ and $\Exp(q_2) = o(1)$. The proof involves a relaxation technique which can be used with arbitrary distributions. The best previously known bound is $q_1+\Exp(q_2) = \Omega(p\log(n))$. For general group testing algorithms, our results imply that if the average number of queries over the course of $n^\gamma$ ($\gamma>0$) independent experiments is $O(n^{1-\epsilon})$, then with high probability $\Omega(\log(n)\log(n)/\log\log(n))$ non-singleton subsets are queried. This settles a conjecture of Bill Bruno and David Torney and has important consequences for the use of group testing in screening DNA libraries and other applications where it is more cost effective to use non-adaptive algorithms and/or too expensive to prepare a subset $Q$ for its first test.


title: Generalized degrees and densities for families of sets

abstract: Let F be a family of subsets of {1,2,...,n}. The width-degree of an element x in at least one member of F is the width of the family {U in F | x in U}. If F has maximum width-degree at most k, then F is locally k-wide. Bounds on the size of locally k-wide families of sets are established. If F is locally k-wide and centered (every U in F has an element which does not belong to any member of F incomparable to U), then |F| <= (k+1)(n-k/2); this bound is best possible. Nearly exact bounds, linear in n and k, on the size of locally k-wide families of arcs or segments are determined. If F is any locally k-wide family of sets, then |F| is linearly bounded in n. The proof of this result involves an analysis of the combinatorics of antichains. Let P be a poset and L a semilattice (or an intersection-closed family of sets). The P-size of L is |L^P|. For u in L, the P-density of u is the ratio |[u)^P|/|L^P|. The density of u is given by the [1]-density of u. Let p be the number of filters of P. L has the P-density property iff there is a join-irreducible a in L such that the P-density of a is at most 1/p Which non-trivial semilattices have the P-density property? For P=[1], it has been conjectured that the answer is: "all" (the union-closed sets conjecture). Certain subdirect products of lower-semimodular lattices and, for P=[n], of geometric lattices have the P-density property in a strong sense. This generalizes some previously known results. A fixed lattice has the [n]-density property if n is large enough. The density of a generator U of a union-closed family of sets L containing the empty set is estimated. The estimate depends only on the local properties of L at U. If L is generated by sets of size at most two, then there is a generator U of L with estimated density at most 1/2.


title: Notes on the connectivity of Cayley coset digraphs

abstract: Hamidoune's connectivity results for hierarchical Cayley digraphs are extended to Cayley coset digraphs and thus to arbitrary vertex transitive digraphs. It is shown that if a Cayley coset digraph can be hierarchically decomposed in a certain way, then it is optimally vertex connected. The results are obtained by extending the methods used by Hamidoune. They are used to show that cycle-prefix graphs are optimally vertex connected. This implies that cycle-prefix graphs have good fault tolerance properties.


title: The complexity of broadcasting in bounded-degree networks

abstract: Broadcasting concerns the dissemination of a message originating at one node of a network to all other nodes. This task is accomplished by placing a series of calls over the communication lines of the network between neighboring nodes, where each call requires a unit of time and a call can involve only two nodes. We show that for bounded-degree networks determining the minimum broadcast time from an originating node remains NP-complete.


title: Algorithms for learning and teaching sets of vertices in graphs

abstract: The learning complexity of special sets of vertices in graphs is studied in the model(s) of exact learning by (extended) equivalence and membership queries. Polynomial-time learning algorithms are described for vertex covers, independent sets, and dominating sets. The complexity of learning vertex sets of fixed size is also investigated, and it is shown that the k-element vertex covers in a graph can be learned in a number of rounds of interaction that is independent of the size of the graph. Apart from the elegance of these algorithmic problems, the chief motivation is the surprising recently established connection between the important unsolved problem of the learning complexity of CNF (or DNF) formulas and the learning complexity of dominating sets. The complexity of teaching sets of vertices in graphs is also considered.


title: The quadratic formula made hard: A less radical approach to solving equations

abstract: It appears that, along with many of my friends and colleagues, I had been brainwashed by the great and tragic lives of Abel and Galois to believe that no general formulas are possible for roots of equations higher than quartic. This seemed to be confirmed by the brilliant and arduous solution of the general quintic by Hermite. Yet, below we find a formula giving a root to any algebraic equation of degree 2-5 and any reduced equation (see below) of higher degree. This algorithm, which must have been familiar to Lagrange, resulted when I was working on a paper on the asymptotics of hypergeometric functions where Gauss' multiplication formula for the gamma function is used to reduce certain infinite series, and by a happy accident my copy of Whittaker and Watson opened at p. 133.


title: 3F2(1) hypergeometric function and quadratic R-matrix algebra

abstract: We construct a class of representations of the quadratic $R$-matrix algebra given by the reflection equation with the spectral parameter, $$ R{\,}(u-v)\,T^{(1)}(u)\,R{\,}(u+v)\,T^{(2)}(v)= T^{(2)}(v)\,R{\,}(u+v)\,T^{(1)}(u)\,R{\,}(u-v), $$ in terms of certain ordinary difference operators. These operators turn out to act as parameter shifting operators on the ${}_3F{}_2(1)$ hypergeometric function and its limit cases and on classical orthogonal polynomials. The relationship with the factorisation method will be discussed.


title: Contiguous relations, basic hypergeometric functions, and orthogonal polynomials : III. associated continuous dual q-Hahn polynomials

abstract: Explicit solutions for the three-term recurrence satisfied by associated continuous dual $q$-Hahn polynomials are obtained. A minimal solution is identified and an explicit expression for the related continued fraction is derived. The absolutely continuous component of the spectral measure is obtained. Eleven limit cases are discussed in some detail. These include associated big $q$-Laguerre , associated Wall, associated Al-Salam-Chihara, associated Al-Salam-Carlitz I, and associated continuous $q$-Hermite polynomials.


title: Special functions associated with root systems: recent progress

abstract: In this paper I present a brief survey of the active area of Special Functions associated with Root Systems. The article is intended for a general mathematical audience. It will not suppose prerequisites on either special functions or root systems. It will also skip many technical details. Some early work in this area (root systems BC_2 and A_2) was done by the author [17] and Sprinkhuizen [32]. During the last ten years important breakthroughs were made by Heckman and Opdam [11], [27], [28], [12], Macdonald [23], [24], Dunkl [8] and Cherednik [3], [4], [5].


title: Extensions and results from a method for evaluating fractional integrals

abstract: We present a method derived from Laplace transform theory that enables the evaluation of fractional integrals. This method is adapted and extended in a variety of ways to demonstrate its utility in deriving alternative representations for other classes of integrals. We also use the method in conjunction with several different techniques to derive many results that have not appeared in tables of integrals.


title: On a general q-Fourier transformation with nonsymmetric kernels

abstract: Wiener used the Poisson kernel for the Hermite polynomials to deal with the classical Fourier transform. Askey, Atakishiyev and Suslov used this approach to obtain a q-Fourier transform by using the continuous q-Hermite polynomials. Rahman and Suslov extended this result by taking the Askey--Wilson polynomials, considered to be the most general continuous classical orthogonal polynomials. The theory of q-Fourier transformation is further extended here by considering a nonsymmetric version of the Poisson kernel with Askey--Wilson polynomials. This approach enables us to obtain some new results, for example, the complex and real orthogonalities of these kernels.


title: A non-commutative discrete hypergroup associated with q-disk polynomials

abstract: The aim of this paper is to give an example of a non-commutative discrete hypergroup associated with $q$-disk polynomials. These are polynomials $R_{l,m}^{(\a)}$ in two non-commuting variables which are expressed through little $q$-Jacobi polynomials and that appear, for the value $\a=n-2$, as zonal spherical functions on a quantum analogue of the homogeneous space $U(n)/U(n-1)$. This fact was first proved in [NYM] (see also [Fl]). In a previous paper [Fl] we proved an addition formula for these $q$-disk polynomials. It is this addition formula that will allow us to prove positivity of linearization coefficients in a manner similar to [Koo1], and to construct from it a DJS-hypergroup following [Koo4].


title: Addition formula for q-disk polynomials

abstract: The purpose of this paper is to present an addition formula for so-called $q$-disk polynomials, using some quantum group theory. This result is a $q$-analogue of a result which was proved around 1970 by ${\breve{\text S}}$apiro [S] and Koornwinder [Koo1,2] independently. They considered the homogeneous space $U(n)/U(n-1)$, were $U(n)$ denotes the group of unitary transformations of the vector space $\C^n$, and identified the corresponding zonal spherical functions as disk polynomials, in the terminology of [Koo2]. These are orthogonal polynomials in two variables whose orthogonality measure is supported by the closed unit disk in the complex plane, and which can be expressed in terms of Jacobi polynomials $P_n^{(\a,\b)} (x)$ for certain integer values of the parameters $\a$ and $\b$. The associated spher ical funtions were shown to be also expressible in terms of disk polynomials, and from this an addition formula was proved for (positive) integer values of $\a$ and $\b$. By an easy argument this identity was then extended to all complex values of $\a$ (and from this Koornwinder could even derive an addition formula for general Jacobi polynomials). And in fact the line of arguing and the results in this paper will be very similar to (part of) the ones in [Koo2].


title: Representation-theoretic proof of the inner product and symmetry identities for MacDonald's polynomials

abstract: This paper is a continuation of our papers [EK1, EK2]. In [EK2] we showed that for the root system A_n-1 one can obtain Macdonald's polynomials - a new interesting class of symmetric functions recently defined by I. Macdonald {M1] - as weighted traces of intertwining operators between certain finite-dimensional representations of U_q sl_n. The main goal of the present paper is to use this construction to give a representation-theoretic proof of Macdonald's inner product and symmetry identities for the root system A_n-1. Macdonald's inner product identities (see [M2]) have been proved by combinatorial methods my Macdonald ([Macdonald, private communication]).


title: Stable vector bundles on algebraic surfaces

abstract: We prove an existence result for stable vector bundles with arbitrary rank on an algebraic surface, and determine the birational structure of certain moduli space of stable bundles on a rational ruled surface.


title: The essentially free spectrum of a variety

abstract: We partially prove a conjecture from [MkSh:366] which says that the spectrum of almost free, essentially free, non-free algebras in a variety is either empty or consists of the class of all successor cardinals.


title: McColm conjecture

abstract: Gregory McColm conjectured that positive elementary inductions are bounded in a class K of finite structures if every (FO + LFP) formula is equivalent to a first-order formula in K. Here (FO + LFP) is the extension of first-order logic with the least fixed point operator. We disprove the conjecture. Our main results are two model-theoretic constructions, one deterministic and the other randomized, each of which refutes McColm's conjecture.


title: On finite rigid structures

abstract: The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no L^omega_{infty, omega} formula with counting quantifiers defines a linear order.


title: Measures with infinite Lyapunov exponents for the periodic Lorentz gas

abstract: In \cite{Ch91a} it was shown that the billiard ball map for the periodic Lorentz gas has infinite topological entropy. In this article we study the set of points with infinite Lyapunov exponents. Using the cell structure developed in \cite{BSC90,Ku} we construct an ergodic invariant probability measure with infinite topological entropy supported on this set. Since the topological entropy is infinite this is a measure of maximal entropy. From the construction it is clear that there many such measures can coexist on a single component of topological transitivity. We also construct an ergodic invariant probability measure with finite entropy which is supported on this set showing that infinite exponents do not necessarily lead to infinite entropy.


title: Internal addresses in the Mandelbrot set and Galois groups of polynomials

abstract: We describe an interesting interplay between symbolic dynamics, the structure of the Mandelbrot set, permutations of periodic points achieved by analytic continuation, and Galois groups of certain polynomials. Internal addresses are a convenient and efficient way of describing the combinatorial structure of the Mandelbrot set, and of giving geometric meaning to the ubiquitous kneading sequences in human-readable form (Sections 3 and 4). A simple extension, \emph{angled internal addresses}, distinguishes combinatorial classes of the Mandelbrot set and in particular distinguishes hyperbolic components in a concise and dynamically meaningful way. This combinatorial description of the Mandelbrot set makes it possible to derive existence theorems for certain kneading sequences and internal addresses in the Mandelbrot set (Section~6) and to give an explicit description of the associated parameters. These in turn help to establish some algebraic results about permutations of periodic points and to determine Galois groups of certain polynomials (Section~7). Through internal addresses, various areas of mathematics are thus related in this manuscript, including symbolic dynamics and permutations, combinatorics of the Mandelbrot set, and Galois groups.


title: Self-complementary plane partitions by Proctor's minuscule method

abstract: A method of Proctor [European J. Combin. 5 (1984), no. 4, 331-350] realizes the set of arbitrary plane partitions in a box and the set of symmetric plane partitions as bases of linear representations of Lie groups. We extend this method by realizing transposition and complementation of plane partitions as natural linear transformations of the representations, thereby enumerating symmetric plane partitions, self-complementary plane partitions, and transpose-complement plane partitions in a new way.


title: Leaper graphs

abstract: An $\{r,s\}$-leaper is a generalized knight that can jump from $(x,y)$ to $(x\pm r,y\pm s)$ or $(x\pm s,y\pm r)$ on a rectangular grid. The graph of an $\{r,s\}$-leaper on an $m\times n$ board is the set of $mn$~vertices $(x,y)$ for $0\leq x<m$ and $0\leq y<n$, with an edge between vertices that are one $\{r,s\}$-leaper move apart. We call $x$ the {\it rank} and $y$ the {\it file} of board position $(x,y)$. George~P. Jelliss raised several interesting questions about these graphs, and established some of their fundamental properties. The purpose of this paper is to characterize when the graphs are connected, for arbitrary~$r$ and~$s$, and to determine the smallest boards with Hamiltonian circuits when $s=r+1$ or $r=1$.


title: The Lu Qi-Keng Conjecture Fails Generically

abstract: The bounded domains of holomorphy in~$\mathbf{C}^n$ whose Bergman kernel functions are zero-free form a nowhere dense subset (with respect to a variant of the Hausdorff distance) of all bounded domains of holomorphy.


title: On the reflection principle in C^n

abstract: We propose a reflection principle for holomorphic objects in ${\Bbb C}^n$. Our construction generalizes the classical principle of H.Lewy, S.Pinchuk and S.Webster.


title: When Schrier transversals grow wild

abstract: Schreier formula for the rank of a subgroup of finite index of a finitely generated free group $F$ is generalized to an arbitrary (even infinitely generated) subgroup $H$ through the Schreier transversals of $H$ in $F$. The rank formula may also be expressed in terms of the cogrowth of $H$. We introduce the rank-growth function $rk_H(i)$ of a subgroup $H$ of a finitely generated free group $F$. $rk_H(i)$ is defined to be the rank of the subgroup of $H$ generated by elements of length less than or equal to $i$ (with respect to the generators of $F$), and it equals the rank of the fundamental group of the subgraph of the cosets graph of $H$, which consists of the paths starting at $1$ that are of length $\leq i$. When $H$ is supnormal, i.e. contains a non-trivial normal subgroup of $F$, we show that its rank-growth is equivalent to the cogrowth of $H$. A special case of this is the known result that a supnormal subgroup of $F$ is of finite index if and only if it is finitely generated. In particular, when $H$ is normal then the growth of the group $G=F/H$ is equivalent to the rank-growth of $H$. A Schreier transversal forms a spanning tree of the cosets graph of $H$, and thus its topological structure is of a contractible spanning subcomplex of a simplicial complex. The $d$-dimensional simplicial complexes that contain contractible spanning subcomplexes have the homotopy type of a bouquet of $r$ $d$-spheres. When these complexes are also $n$-regular then $r$ can be computed by generalizing the rank formula (which applies to Schreier transversals) to higher dimensions.


title: The normalized cyclomatic quotient associated with presentations of finitely generated groups

abstract: Given the Cayley graph of a finitely generated group $G$, with respect to a presentation $G^{\alpha}$ with $n$ generators, the quotient of the rank of the fundamental group of subgraphs of the Cayley graph by the cardinality of the set of vertices of the subgraphs gives rise to the definition of the normalized cyclomatic quotient $\Xi (G^{\alpha})$. The asymptotic behavior of this quotient is similar to the asymptotic behavior of the quotient of the cardinality of the boundary of the subgraph by the cardinality of the subgraph. Using Følner's criterion for amenability one gets that $\Xi (G^{\alpha})$ vanishes for infinite groups if and only if they are amenable. When $G$ is finite then $\Xi (G^{\alpha})=1/|G|$, where $|G|$'> is the cardinality of $G$, and when $G$ is non-amenable then $1-n\leq\Xi (G^{\alpha})\le 0$, with $\Xi (G^{\alpha})=1-n$ if and only if $G$ is free of rank $n$. Thus we see that on special cases $\Xi (G^{\alpha})$ takes the values of the Euler characteristic of $G$. Most of the paper is concerned with formulae for the value of $\Xi (G^{\alpha})$ with respect to that of subgroups and factor groups, and with respect to the decomposition of the group into direct product and free product. Some of the formulae and bounds we get for $\Xi (G^{\alpha})$ are similar to those given for the spectral radius of symmetric random walks on the graph of $G^{\alpha}$, but this is not always the case. In the last section of the paper we define and touch very briefly the balanced cyclomatic quotient, which is defined on concentric balls in the graph and is related to the growth of $G$.


title: Rational Maps Whose Fatou Components Are Jordan Domains

abstract: We prove: If $f(z)$ is a critically finite rational map which has exactly two critical points and which is not conjugate to a polynomial, then the boundary of every Fatou component of $f$ is a Jordan curve. If $f(z)$ is a hyperbolic critically finite rational map all of whose postcritical points are periodic, then there exists a cycle of Fatou components whose boundaries are Jordan curves. We give examples of critically finite hyperbolic rational maps $f$ with the property that on the closure of a Fatou component $\Omega$ satisfying $f(\Omega)=\Omega$, $f|_{\bdry \Omega}$ is not topologically conjugate to the dynamics of any polynomial on its Julia set.


title: $R$--groups and elliptic representations for similitude groups

abstract: The tempered spectrum of the similitude groups of non-degenerate symplectic, hermitian, or split orthogonal forms defined over $p$\snug-adic groups of characteristic zero is studied. The components of representations induced from discrete series of proper parabolic subgroups are classified in terms of $R$\snug-groups. Multiplicity one is proved. The tempered elliptic spectrum is identified, and the relation between elliptic characters appearing in a given induced representation is determined. Those irreducible tempered representations which are not elliptic and not fully induced from elliptic tempered representations are described.


title: Automorphic $L$\snug-functions, intertwining operators, and the irreducible tempered representations of $p$\snug-adic groups

abstract: We give an expository account of the theory of intertwining operators for connected reductive $p$--adic groups, and their connection with automorphic $L$--functions. Our purpose is to illustrate the relation between harmonic analysis and arithmetic. In particular, we describe how the theory of Plancherel measures allows us to compute certain local Langlands $L$--functions. In order to be more self contained, we give a brief introduction to the Langlands program. The theory of $R$--groups and elliptic representations is treated here as well. Finally, we give an example which illustrates how the theory of twisted endoscopy plays a crucial role in determining the poles of both the intertwining operators and the local Langlands $L$--functions in question. A version of this manuscript, in revised form, will appear as a chapter in the proceedings of the conference ``Teoria de Representaciones de Groupos Algebraicos Sobre Cuerpos Locales y Applicationes'' (C. Bushnell, P. Kutzko, J. Pantoja, J. Soto Andrade eds.).


title: Possible pcf algebras

abstract: There exists a family $\{B_{\alpha}\}_{\alpha<\omega_1}$ of sets of countable ordinals such that o $\max B_{\alpha}=\alpha$, o if $\alpha\in B_{\beta}$ then $B_{\alpha}\subseteq B_{\beta}$, o if $\lambda\leq \alpha$ and $\lambda$ is a limit ordinal then $B_{\alpha}\cap\lambda$ is not in the ideal generated by the $B_{\beta}$, $\beta<\alpha$, and by the bounded subsets of $\lambda$, o there is a partition $\{A_n\}_{n=0}^{\infty}$ of $\omega_1$ such that for every $\alpha$ and every $n,$ $B_{\alpha}\cap A_n$ is finite.


title: Some results on nonstationry ideal 2

abstract: This is a continuation of "Some results on nonstationry ideal". The upper bound on precipitousness of NS_lambda^+ for a regular lambda given in this paper is proved to be exact.It is shown that saturatedness of NS_kappa^aleph_0 over inaccessible kappa requires at least o(kappa)=kappa^++.The upper bounds on the strength of NS_kappa precipitous for inaccessible kappa are reduced quite close to the lower bounds.


title: Links of prime ideals and their Rees algebras

abstract: In a previous paper we exhibited the somewhat surprising property that most direct links of prime ideals in Gorenstein rings are equimultiple ideals with reduction number $1$. This led to the construction of large families of Cohen--Macaulay Rees algebras. The first goal of this paper is to extend this result to arbitrary Cohen--Macaulay rings. The means of the proof are changed since one cannot depend so heavily on linkage theory. We then study the structure of the Rees algebra of these links, more specifically we describe their canonical module in sufficient detail to be able to characterize self--linked prime ideals. In the last section multiplicity estimates for classes of such ideals are established.


title: On Convergence of Conditional Expectation Operators

abstract: Given an operator $T:U_X(\Sigma)\to Y$ or ${T:U(\Sigma)\to Y$, one may consider the net of conditional expectation operators $(T_\pi)$ directed by refinement of the partitions $\pi$. It has been shown previously that $(T_\pi)$ does not always converge to $T$. This paper gives several conditions under which this convergence does occur, including complete characterizations when $X={\bold R}$ or when $X\sp *$ has the Radon-Nikod\'ym property.


title: An elementary approach to the Daugavet equation

abstract: Let $T\dopu C(S)\to C(S)$ be a bounded linear operator. We present a necessary and sufficient condition for the so-called Daugavet equation $$ \|\Id+T\| = 1+\|T\| $$ to hold, and we apply it to weakly compact operators and to operators factoring through $c_{0}$. Thus we obtain very simple proofs of results by Foias, Singer, Pelczynski, Holub and others.


title: Extreme contractions in ${\cal L}(\ell^p_2, \ell^q_2)$ and the mazur intersection property in $\ell^p_2 \otimes_{\p} \ell^q_2$

abstract: In this paper, we show that the projective tensor product of a two-dimen\-sional $\ell^p$ space with a two-dimensional $\ell^q$ space never has the Mazur Intersection Property for a large range of values of $p$ and $q$. For this purpose, we characterise the extreme contractions from $\ell^p_2$ to $\ell^q_2$ and obtain their closure.


title: The Hardy Operator and Boyd Indices

abstract: We give necessary and sufficient conditions for the Hardy operator to be bounded on a rearrangement invariant quasi-Banach space in terms of its Boyd indices.


title: Boyd Indices of Orlicz-Lorentz Space

abstract: Orlicz-Lorentz spaces provide a common generalization of Orlicz spaces and Lorentz spaces. In this paper, we investigate their Boyd indices. Bounds on the Boyd indices in terms of the Matuszewska-Orlicz indices of the defining functions are given. Also, we give an example to show that the Boyd indices and Zippin indices of an Orlicz-Lorentz space need not be equal, answering a question of Maligranda. Finally, we show how the Boyd indices are related to whether an Orlicz-Lorentz space is p-convex or q-concave.


title: Extremal properties of contraction semigroups on $c_o$

abstract: For any complex Banach space $X$, let $J$ denote the duality mapping of $X$. For any unit vector $x$ in $X$ and any ($C_0$) contraction semigroup $(T_t)_{t>0}$ on $X$, Baillon and Guerre-Delabriere proved that if $X$ is a smooth reflexive Banach space and if there is $x^* \in J(x)$ such that $|\langle T(t) \, x,J(x)\rangle| \to 1 $ as $t \to \infty$, then there is a unit vector $y\in X$ which is an eigenvector of the generator $A$ of $(T_t)_{t>0}$ associated with a purely imaginary eigenvalue. They asked whether this result is still true if $X$ is replaced by $c_o$. In this article, we show the answer is negative.


title: Extension of Operators from Weak$^*$-closed Subspaces of $\ell_1$

abstract: It is proved that every operator from a weak$^*$-closed subspace of $\ell_1$ into a space $C(K)$ of continuous functions on a compact Hausdorff space $K$ can be extended to an operator from $\ell_1$ to $C(K)$.


title: Best constants for uncentered maximal functions

abstract: We precisely evaluate the operator norm of the uncentered Hardy-Littlewood maximal function on $L^p(\Bbb R^1)$. We also compute the operator norm of the uncentered Hardy-Littlewood maximal function over rectangles on $L^p(\Bbb R^n)$, and we show that the operator norm of the uncentered Hardy-Littlewood maximal function over balls on $L^p(\Bbb R^n)$ grows exponentially with the dimension as $n \to \infty$.


title: The Mazur Intersection Property and Farthest Points

abstract: K.\ S.\ Lau had shown that a reflexive Banach space has the Mazur Intersection Property (MIP) if and only if every closed bounded convex set is the closed convex hull of its farthest points. In this work, we show that in general this latter property is equivalent to a property stronger than the MIP. As corollaries, we recapture the result of Lau and characterize the w*-MIP in dual of RNP spaces.


title: Mean Values of the Logarithmic Derivative of the zeta Function and the GUE Hypothesis

abstract: The GUE Hypothesis, which concerns the distribution of zeros of the Riemann zeta-function, is used to evaluate some integrals involving the logarithmic derivative of the zeta-function. Some connections are shown between the GUE Hypothesis and other conjectures.


title: On the Asymptotic Behavior of Counting Functions Associated to Degenerating Hyperbolic Riemann Surfaces

abstract: We develop an asymptotic expansion of the spectral measures on a degenerating family of hyperbolic Riemann surfaces of finite volume. As an application of our results, we study the asymptotic behavior of weighted counting functions, which, if $M$ is compact, is defined for $w \geq 0$ and $T > 0$ by $$N_{M,w}(T) = \sum\limits_{\lambda_n \leq T}(T-\lambda_n)^w $$ where $\{\lambda_n\}$ is the set of eigenvalues of the Laplacian which acts on the space of smooth functions on $M$. If $M$ is non-compact, then the weighted counting function is defined via the inverse Laplace transform. Now let $M_{\ell}$ denote a degenerating family of compact or non-compact hyperbolic Riemann surfaces of finite volume which converges to the non-compact hyperbolic surface $M_{0}$. As an example of our results, we have the following theorem: There is an explicitly defined function $G_{\ell,w}(T)$ which depends solely on $\ell$, $w$, and $T$ such that for $w > 3/2$ and $T>0$, we have $$N_{M_{\ell},w}(T) = G_{\ell,w}(T) +N_{M_{0},w}(T) +o(1)$$ for $\ell \to 0$. We also consider the setting when $w < 3/2$, and we obtain a new proof of the continuity of small eigenvalues on degenerating hyperbolic Riemann surfaces of finite volume.