Geometric Functional Analysis & Probability Seminar

Organizers (2005/6-2007/8): Itai Benjamini, Gady Kozma, Gideon Schechtman, and Boaz Tsaban.

Remark. This page was maintained by Boaz during the academic years 2005/6-2007/8. It is kept here for documentational purposes only. For talks in later years, visit Gideon Schechtman's GFPA webpage.

Description: This is/was an interdisciplinary seminar which deals mainly with topics in geometric functional analysis and probability theory, but occasionally also with combinatorics and other fields of mathematics of wide mathematical interest and accessibility.

The talks in the seminar are often not about results of the speakers but rather expositions of interesting works done by others. To allow providing full definitions and at least some of the details of the proofs at a convenient pace, each talk usually lasts from two hours (one meeting) to two meetings.

The special emphasis on accessibility of the talks makes this seminar suitable for students and working mathematicians with interest in either functional analysis, probability, or combinatorics.

List of talks

The following list is sorted backwards.

20 June 2007: Emil Saucan (Technion), A metric curvature for weighted graphs and some of its applications.

We develop a discrete version of the classical Finsler-Haantjes metric curvature. This allows us to define discrete analogues of geodesic, sectional, mean and Gauss curvatures for weighted graphs. Furthermore, we endow each weighted graph with an intrinsic metric induced by the weights, yielding it as a geodesic metric space.

These methods combined allow us to approach a variety of problems, mainly to networks' geometrization. In particular, we examine the use of our discrete curvature in clustering problems, both for communication networks and in DNA microarray analysis.

Joint work with Eli Appleboim.

13 June 2007: Eric Babson (UC Davis), The fundamental group of a random two dimensional simplicial complex.

We study a model of random simplicial complexes introduced by Linial and Meshulam, who found the threshold for vanishing of homology with bounded coefficients. By analyzing small subcomplexes we can use Gromov's local to global principal for linear isoperipetric inequalities to find the (different) threshold for vanishing of the fundamental groups.

6 June 2007: Boris Solomyak (U Washington), Branching Random Walk with Exponentially Decreasing Steps, and Stochastically Self-Similar Measures.

We consider a Branching Random Walk on the real line whose step size decreases by a fixed factor, 0 30 May 2007: Nathanael Berestycki (U. British Columbia), Some questions about random walks on large finite graphs.

In this informal talk, I will consider random walks on finite graphs and study the speed at which they get away from their starting point, measured in terms of the graph distance. I will describe a variety of examples and show that in many interesting cases this may exhibit a phase transition. I will then speculate on the origin of this phase transition and state a few open problems. Partly joint with Rick Durrett.

16 May 2007: Ori Gurel-Gurevich (WIS), On K-wise Independent Distributions, Boolean Functions and Percolation.

Let f be a (usually monotone) boolean function whose behaviour is well understood when the input bits are identically independently distributed. What can be said about the behaviour of the function when the input bits are not completely independent, but only k-wise independent, i.e. every subset of k bits is independent? more precisely, how high should k be so that any k-wise independent distribution "fools" the function, i.e. causes it to behave nearly the same as when the bits are completely independent?

In this lecture we will explore this notion for various functions, using tools from error correcting codes, linear programming and the theory of the classical moments problem. Our prime example will be percolation (on Z^d or regular trees) for which we prove that the requirement of k-wise independence is weak: there is a k-wise independent distribution on the states of edges of these graphs such that there is almost surely an infinite open cluster even though the probability for each edge to be open is as low as we want and another such distribution such that there is almost surely no infinite open cluster even though the probability for each edge to be open is as high as we want.

Joint work with Itai Benjamini and Ron Peled.

9 May 2007: Nick Crawford (UCLA & Technion), Probabilistic representations of quantum spin systems.

In this talk we will introduce quantum spin systems and attempt to explain that in many cases of interest one may study them using various probabilistic representations. The first hour we will explain two expansions-the Feynam-Kac representation, through which one represents the system as a constrained Markov process and an extremely useful technique of ‘Poissonization’ of the Gibbs-Boltzman operator due to M. Aizenman and B. Nachtergaele, which gives a static Fortuin-Kastelyn percolation picture. We will contrast the to representations using two or three examples: the transverse Ising model, the Quantum Heisenberg Ferromagnet, and possibly the Quantum Heisenberg Anti-Ferromagnet as time permits. The second hour we will discuss one or two applications of the theory: one to a generalization of the Sherrington-Kirkpatrick model of spin glasses and another to get a sharp picture of the phase structure of the Quantum Ising Model in a Transverse Field on the Complete Graph, again as time permits. We will endeavor to make the talk as self contained as possible.

2 May 2007: Jonathan Breuer (HUJI), Singular continuous spectrum and Anderson localization.

Sparse trees are combinatorial trees with arbitrarily long one-dimensional stretches. They are obtained as finite dimensional interpolating objects between the (discrete) line and the Bethe lattice. In the context of such trees, we prove complete exponential localization for the Anderson model in any dimension. Moreover, we show that a free quantum particle on such trees may have singular continuous or even dense point spectrum. After defining the relevant notions, the talk will discuss the results described above and present an outline of the proofs. In particular, we shall explain the analogy between a free particle on a sparse tree and a one-dimensional particle in a potential of sparse bumps.

25 April 2007: Eyal Lubetzky (TAU), Non-linear index coding outperforming the linear optimum.

The following source coding problem was introduced by Birk and Kol: a sender holds a word x in {0,1}n, and wishes to broadcast a codeword to n receivers, R1,...,Rn. The receiver Ri is interested in xi, and has prior side information comprising some subset of the n bits. This corresponds to a directed graph G on n vertices, where i j is an edge iff Ri knows the bit xj. An index code for G is an encoding scheme which enables each Ri to always reconstruct xi, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram and Kol (FOCS 2006). They introduced a graph parameter, minrk2(G), which completely characterizes the length of an optimal linear index code for G. The authors of [BBJK06] showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal.

In this work, we disprove the main conjecture of [BBJK06] in the following strong sense: for any epsilon > 0 and sufficiently large n, there is an n-vertex graph G so that every linear index code for G requires codewords of length at least n1-epsilon, and yet a non-linear index code for G has a word length of nepsilon. This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson.

In addition, we study optimal index codes in various, less restricted, natural models, and prove several related properties of the graph parameter minrk(G). Joint work with Uri Stav.

18 April 2007: Gidi Amir (WIS), Hausdorff dimension of harmonic measures in the plane (after Jones and Wolff).

In this famous paper the authors show that for every plane set, the harmonic measure is supported (in an apropriate sense) on a set of hausdorff dimension 1. It is a strengthening of Makarov's result to non-simply-connected domains using a different and interesting technique.

28 March 2007: Students Probability Day, see

21 March 2007: Or Zuk (WIS), The entropy rate of Hidden Markov Processes.

The entropy rate of a stochastic process is a fundamental information-theoretic notion, measuring the 'amount of randomness' of the process. It can be thought of as the asymptotic exponential growth rate of the effective number of different sequences that can be generated by the process. The entropy rate of Hidden Markov Processes (HMPs) has been studied quite extensively in the last five years after a long hiatus, using ideas and techniques from probability, information theory, dynamical systems and statistical mechanics.

Despite great progress which have been made, no general explicit formula for HMPs entropy rate is known to date. In this talk I will discuss classic and recent results - Blackwell's measure on the simplex and his integral formula, a representation as a Lyapunov exponent of a random matrix product, analyticity in the process parameters, upper and lower bounds, asymptotic results and Taylor series expansions.

14 Feb 07: Dominik Freche (WIS), Some homogenization results by Rauch and Taylor.

We present some by now classical results by J. Rauch and M. Taylor (J. Func. Anal. 18, p.77-59 (1975)) concerned with boundary value problems for the Laplacian on domains with `holes' that tend to `vanish' or to `form clouds.' We describe all necessary theory along the way.

7 Feb 07: Shiri Artstein (TAU), Metric Entropy and Coverings.

The duality of entropy numbers conjecture concerns the quantifying, in terms of covering numbers (or entropy numbers), of the classical fact that if a linear operator between two Banach Spaces is compact then so is its dual. The most important case (which is the one appearing in applications to probability theory, ergodic theory, learning theory and other fields) is when one of the two spaces is a Hilbert space.

In 2003, jointly with V.D. Milman and S.J. Szarek, we proved the duality conjecture in this case. More recently, in a joint work together also with N. Tomczak-Jaegermann, we generalized this theorem to a wide class of spaces (which include for example all uniformly convex and all uniformly smooth spaces). This generalization involved a new notion of 'convexified packing' which is of independent interest.

In the talk I will discuss these notions and results, and present some ideas involved in the proofs, and the open problems which remain.

31 Jan 07: Ariel Yadin (WIS), DLA on a discrete cylinder.

Diffusion Limited Aggregation (DLA) is a growth model in the discrete plane Z^2. The process starts with a particle at the origin of Z^2. At each time step, a new particle starts a simple random walk on Z^2 from infinity (far away). When the particle first hits the outer boundary of the cluster, it sticks, and the next step starts, forming a growing family of clusters. This process was introduced in 1981 by Witten and Sander. Although it has received attention from the best analysts, there is only one notable rigorous result (by H. Kesten). The major open problem concerning DLA is to show that the aggregate "grows arms", i.e. grows faster than a ball. We consider the DLA process on a discrete cylinder G x N, for a finite graph G. Our main result is that this process ``grows arms'', provided that the base graph G has small enough mixing time.

I will introduce the DLA process on the discrete plane Z^2, and on discrete cylinders, state Kesten's result outline its proof. Then I will outline the proof of our main result. The talk assumes only undergraduate knowledge of probability and graph theory. All notions will be defined in the talk.

24 Jan 07: Zeev Dvir (WIS), Evolving sets and mixing.

I will talk about the paper Evolving sets and mixing by Yuval Peres and Ben Morris. The paper describes a probabilistic technique that yields the sharpest bounds obtained to date on mixing times in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities).

The proof of the mixing time bounds rely on the notion of 'Evolving sets' which is a related Markov chain on sets of states. In the talk I will define evolving sets and will show how they are used to obtained the bounds on mixing time. No previous knowledge is assumed.

17 Jan 07: Emanuel Milman (WIS), Almost sub-Gaussian marginals of convex bodies.

A well known fact concerning the distribution of volume inside convex bodies, is that any marginal of a convex body (i.e. projection of the uniform measure on the body onto some one dimensional direction) has exponentially decaying tails. We present a recent result of Boaz Klartag, with a clearer line of presentation given by Giannopolous, Pajor and Paouris, which shows that in fact one can always find a marginal which has an almost sub-Gaussian decaying tail. Modulu several recent results and time permitting, the talk will be self contained. To accomodate those who only wish to get a taste of Convex Geometry, we will also mention several fundamental Geometric results along the way, hopefully making the talk productive for both expert and novice Geometrists.

10 Jan 07: Leonid Kontorovich (CMU), A linear programming inequality with applications to concentration of measure.

We prove an elementary yet useful inequality bounding the maximal value of certain linear programs. This leads directly to a bound on the martingale difference for arbitrarily dependent random variables, providing a generalization of some recent concentration of measure results. The linear programming inequality may be of independent interest.
paper url:

3 Jan 07: Doron Shafrir (WIS), Axioms of Symmetry: Throwing random darts at the real line.

This talk presents a paper of Chris Freiling, on which David Mumford said: "Why his theorem is not universally known and considered on a par with the results of Goedel and Cohen, I do not know."

It contains intuitive arguments based on the symmetry in a thought experiment throwing darts at the real line. This basic from probability implies that the Continuum Hypothesis is false (this cannot be proved mathematically).

The Axiom of Choice is also discussed in the light of probabilistic arguments.

Note special place: Henceforth, all lectures of the GFAP seminar will be held in the Ziskind Main Lecture Room (Room 1).

27 Dec 06: Elchanan Mossel (Berkeley), Broadcasting on Trees: Beliefs, Evolution and Reconstruction.

Broadcasting processes on trees play a fundamental role in various inference problems including: Noisy computation, the reconstruction of evolutionary trees in biology, the analysis of message passing algorithms in machine learning such as Belief Propagation and Warning Propagation.

In the talk I will survey several theoretical and applied developments in this area obtained using and extending techniques from discrete probability, information theory and statistical physics.

20 Dec 06 (11:00--13:00): Itamar Procaccia (WIS), Fractal growth patterns and iterated conformal maps.

Fractal growth patterns like Diffusion Limited Aggregates (DLA), Dielectric Breakdown and Viscous Fingering patterns are paradygmatic examples of the spontaneous creation of harmonic fractals (where the underlying equation to be solved is the Laplace equation with boundary conditions on the boundary of the fractal). Harmonic problems are natural candidates for conformal analysis, but the complexity of the patterns required the development of a new approach. I will review a new approach of iterated conformal maps, which allowed the determination of the fractal dimension of DLA, the careful study of the harmonic measure of the growing patterns, and a discussion of the universality classes in related problems.
Note special time!

13 Dec 06: Roee Teper (TAU), Integrals for capacities.

We introduce an integral for capacities, based on the idea behind the Lebesgue integral. We discuss the concept of almost everywhere, emphasize the differences between several possible definitions, and establish the settings for formulating integral convergence theorems. The main result is a representation of the integral with respect to a capacity with a large core, as the infimum of integrals with respect to additive capacities. We conclude with a dominating convergence theorem and a nonadditive version of Egorov's theorem.

6 Dec 06: Ron Peled (UC Berkeley), Gravitational allocation to Poisson points.

Given a translation invariant point process in R^d of intensity 1, an allocation rule is a translation-equivariant mapping that allocates to each point in the process a set in R^d of unit volume, such that the sets allocated to different points are disjoint and their union covers almost all of R^d. Allocation rules can give a better understanding of the underlying point process and can also be used for obtaining extra head rules.
In this talk we will consider the standard Poisson point process in R^d, allocation rules for this process were constructed by Hoffman, Holroyd and Peres using the Gale-Shapley stable marriage algorithm. I We will describe a new allocation rule in dimensions 3 and higher, inspired by recent work of Nazarov, Sodin and Volberg, that is defined by flow along the integral curves of a gravitational force field induced by the Poisson points. The main result is that the allocation is 'efficient', in the sense that the diameter of the cell allocated to a given point is a random variable with exponentially decreasing tails. This is the first explicit allocation with this property.
The talk is based on joint work with Sourav Chatterjee, Yuval Peres and Dan Romik.

29 Nov 06: Ofer Zeitouni (Technion and Univ. Minnesota), Results and challenges in the study of random walks in random environments.

I will define the model of random walks in random environments, in the context of nearest neighbor walks on Z^d. I will then discuss several proof techniques: electrical networks and explicit computations (for the one dimensional case), regeneration techniques, homogenization, and multiscale analysis. I will descrie several open conjectures and some recent counter-examples.

22 Nov 06: Mark Rudelson (Univ. Missouri-Columbia), Invertibility and singular numbers of random matrices.

I'll give the general survey of the spectral properties of random matrices, including the recent developments.

15 Nov 06: Eitan Bachmat (BGU), Discrete spacetime and its applications.

A discrete spacetime is a random, finite, partially ordered set (poset), obtained from sampling a compact domain in a spacetime (Lorentzian) manifold N times, w.r.t the volume form. The partial order is the one induced from the causal (past-future) structure on the domain. These objects were first introduced by physicists in an attempt to quantize gravity. Despite being rather simple objects, they have received very little direct attention from mathematicians.
Recently, we have shown that these objects appear in many natural processes, among them scheduling of I/O in disk drives and airplane boarding.
In the talk we will present some basic results about the asymptotic behavior of discrete spacetimes and show how this is applied to the analysis of the related processes. In particular, we will present some results which may change the way airlines board passengers.

8 Nov 06: Laurent Georgen (ETHZ), Random walks in a random environment.

Diffusions in a random environment came as a natural way to generalize homogenization in a periodic medium and model disorder at a microscopic scale. We start by briefly describing the method of the "environment viewed from the particle", which played an important role even though to present knowledge it applies only in a few specific situations. Then we will explain the results that one can obtain in general by building up on recent progress made in the study of the discrete counterpart of the model, that is "random walks in a random environment". We sketch how certain regeneration times that divide the trajectories into independent pieces lead to a law of large numbers and to a central limit theorem in the case where the asymptotic speed of the diffusion does not vanish (ballistic behaviour). We then introduce several conditions that ensure ballistic behaviour and present a special class of perturbed Brownian motions whose ballistic behaviour was not known before.

1 Nov 06: Genadi Levin (HU), An introduction to the theory of the Mandelbrot set.

12 Sep 06: Alain Sol-Sznitman (ETHZ), On the disconnection of discrete cylinders.

4 July 06: Nadav Samet (Weizmann), Ramsey Theory of groupable covers.

Let B be a collection of covers of a topological space. A cover is B-groupable if there is a partition of it into finite sets, such that the collection of unions of these finite sets form by itself a cover from B. Certain classic selection principles can be reduced to a simpler form by using groupable covers.

These simplified selection principles can be characterized by the Baumgartner-Taylor partition relation, which is a generalized form of the ordinary Ramsey partition relation.

We show the connections between selection principles involving groupable covers and the corresponding partition relations.

Joint work with Marion Scheepers and Boaz Tsaban.

27 June 06: Nadav Samet (Weizmann), Ramsey Theory of open covers.

Ramsey theory is a study of the phenomenon that when a rich (in some sense) structure is divided into finitely many pieces, at least one of the pieces is rich (possibly in some other sense). The most celebrated instance of this theory is Ramsey's Theorem: When each edge of an infinite complete graph is colored by one out of finitely many colors, that graph contains an infinite complete monochromatic graph.

This theory can be generalized to the case where the vertices of the graph have some structure, e.g., they form a "rich" cover of a topological space. In this case, partition relations give rise to interesting properties studied beforehand in classical analysis.

We describe, by following a simple example, the methods for establishing such interconnections.

Joint work with Boaz Tsaban

20 June 06: Boris Solomyak, Self-similar tilings..

A self-similar tiling of the Euclidean space has the property that if you "inflate" the entire tiling by a certain expanding similarity map, the inflated tiles can be subdivided in a prescribed way to give you back the original tiling. In the first part of the talk I will survey the history of this subject and describe some well-known examples, such as the Penrose tiling, the pinwheel tiling and the chair tiling. In the second part I will speak about a theorem of Thurston and Kenyon (15-20 years old, but not too widely known) which gives a characterization of possible expansions for self-similar tilings of the plane, and maybe say something about its generalization to self-affine tilings in higher dimensions (work in progress with Rick Kenyon).

13 June 06: Igor Rivin, Irreducibility of random polynomials, matrices, and automorphisms.

I will talk about irreducibility of random integer polynomials and matrices, and applications to surface and free group automorphisms. The methods include limiting results for random walks on graphs (with values in groups), some algebraic geometry, and some basics of Galois theory.

6 June 06: Omer Angel (UBC), Divergence of Spatial Coallescants.

We consider spatial version of Kingman's Coallescant: particles perform random walks in continuous time on a graph and pairs at the same location coallesce at rate 1. If the process is started with N particles at one vertex, we show that at time 2 the process roughly fills a ball of radius log^*(N).

The process arises as a time reversal of family/evolutionary trees. I will also discuss generalization to other processes.

May 31 (Wednesday): Boaz Klartag (IAS), A central limit theorem for convex sets.

Suppose X is a random vector, that distributes uniformly in some n-dimensional convex set. It was conjectured that when the dimension n is very large, there exists a non-zero vector u, such that the distribution of the real random variable is close to the gaussian distribution. This conjecture appears explicitly in the works of Anttila, Ball and Perissinaki and of Brehm and Voigt, and may be essentially traced back to Gromov and others. A well-understood situation, is when X distributes uniformly over the n-dimensional cube. In this case, is approximately gaussian for, say, the vector u = (1,...,1) / sqrt(n), as follows from the classical central limit theorem.

We prove the conjecture for a general convex set. Moreover, when the expectation of X is zero, and the covariance of X is the identity matrix, we show that for "most" unit-vectors u, the random variable distributes approximately according to the gaussian law. We argue that convexity - and perhaps geometry in general - may replace the role of independence in certain aspects of the phenomenon represented by the central limit theorem.

16 May 06: Eyal Lubetzky (TAU), Graph powers, Delsarte, Hoffman and Ramsey.

The k-th p-power of a graph G is the graph on the vertex set V(G)^k, where two k-tuples are adjacent iff the number of their coordinates which are adjacent in G is not congruent to 0 modulo p. The clique number of powers of G is poly-logarithmic in the number of vertices, thus graphs with small independence numbers in their p-powers do not contain large homogenous subsets, and provide explicit lower bounds for Ramsey numbers.

I will demonstrate how precise bounds on the independence numbers of such powers can be derived from Delsarte's linear programming bound and from Hoffman's eigenvalue bound. Algebraic upper bounds determine the asymptotic behavior for different graphs, settling a conjecture on Xor graph powers up to a factor of 2.

Joint work with Noga Alon.

9 May 06: Ehud Friedgut (HU), Independent sets in graph products.

I'll talk about a paper which is now online. Rather than state a theorem in this abstract here's an example of a special case: Consider the graph with vertices {0,1,2}^n where two vectors are connected if they differ in every coordinate. An example of an independent set is the set of all vectors with "0" in the first coordinate. Another example is all vectors with at least two 0's in the first three coordinates. We prove that essentially any independent set in this graph is almost completely contained in a set which is determined by few coordinates. The "contained in" part is what makes the proof tricky, how does one recover a nicely structured set from an arbitrary subset?

I'll present a general theorem which characterizes independent sets in the product of any graph (the above example was the product of the triangle.) The proof uses algebraic and analytical techniques and is strongly related to discrete Fourier analysis. Everything will be self contained.

Joint work with Irit Dinur and Oded Regev.

26 Apr 06 (Wednesday), 15:00: Emanuel Milman, Covering Numbers, and the Duality of Entropy.

The covering number N(K,T) of a convex symmetric body K by another convex symmetric body T (both in R^n), is defined as the minimal number of translates of T needed to cover K. The entropy function of K w.r.t . T is defined as the function t -> log N(K, t T). These notions have many uses in probability, but this will not be our focus in this talk. We will give a self contained proof, combining several known results, of the following new observation: log N(K,T) <= C log(n) loglog(n) log N(T*,K* / (C log(n))) , where K*,T* are the polar or dual bodies to K,T, respectively, and C>1 is some universal constant. This answers, up to the log(n) terms, a duality conjecture of Pietsch from 1972. The main tools used will be the triangle inequality, convex separation, and combinatorial constructions.

15 Mar 06: Amitai Regev, Expected lengths and distribution functions for partitions of bounded length.

Following Baik and Rains, we consider certain Plancherel measures on partitions of bounded length, then calculate the asymptotics of the expected shape of the corresponding diagrams. We also calculate the distribution functions of the corresponding row-lengths. This might be considered as the restriction of the fundamental work of Baik, Deift and Johansson to partitions of bounded length. The above asymptotics are given by ratios of certain Selberg-type multi-integrals.

14 Feb 06: Assaf Rinot (TAU), The Milner-Sauer Conjecture.

We give a nice topological proof for a theorem of Milner and Pouzet, then improve the result by showing that under a much weaker hypothesis, the Milner-Sauer conjecture holds, and then discuss the consistency strength of this hypothesis.
If time permits, we mention our recent result that a slight weakening of the Milner-Sauer conjecture can already be proved purely in ZFC.

7 Feb 06: Assaf Rinot (TAU), Aspects of singular cofinality.

Fix a pre-closure operator over a set X (examples: usual closure in a topological space; generated subgroup in a group; linear span in a vector space; downward closure in a partially ordered set). What is the minimal cardinality of a subset of X whose closure is X? This cardinal number is denoted cf(X).
Let k=cf(X). It could be the case that k can be represented as a union of less than k cardinals all smaller than k (in this case, we say that k is _singular_). This case is of particular interest. We will discuss consequneces of this situation for most of the above-mentioned cases (groups, topological spaces, and partially ordered sets).
If time permits, we will report recent results of joint work with Moti Gitik concenring a 25 years old conjecture on partially ordered sets of singular cofinality.

31 Jan 06: Jakub Duda (WIS), Differentiability via homeomorphisms.

In the first part of this talk, we will introduce the theory of differentiability of curves via homeomorphisms and survey some known results. Given a class of real valued functions or paths (usually defined in terms of some differentiability properties), this theory seeks conditions (in most cases given in terms of some suitable variations) under which for a given function f defined on [a,b], there exists a homeomorphism h of [a,b] onto itself such that f\circ h is in the prescribed class. Characterizations for many classes of functions and paths are known. We will attempt to survey these kinds of results.
In the second part of the talk, we will present the characterization of real functions f from [a,b] to R for which there exists a homeomorphism h of [a,b] onto itself such that f\circ h is n-times differentiable (where n is an integer greater than or equal to 2). We will build upon earlier results of Laczkovich, Preiss, and Lebedev, who characterized the real-valued functions, which allow $n$-times continuously differentiable parametrizations.

24 Jan 06: Nir Avni (HU), An Introduction to Hyperbolic Geometry.

The pupose of this talk is to introduce (mostly without proofs) the hyperbolic plane and to describe some of its properties and (if time permits) applications. In particular, we will discuss the disc, half plane and hyperboloid models, hyperbolic n-space, geometrization of 2- and 3- manifolds, the boundary at infinity and Mostow rigidity. As an introductory talk, no background will be assumed.

17 Jan 06: Ori Gurel-Gurevich (WIS), Games in Banach Spaces.

Aronszajn-null sets are a notion of negligible sets for infinite dimensional Banach spaces generalizing Lebesgue measure zero sets on the real line and the Euclidean space.
We will present a new approach to Aronszajn null sets, suggested by Jakub Duda and Boaz Tsaban, using infinite games. We will give a brief overview of the background and importance of Aronszajn-null sets, describe the new definitions and results of Duda and Tsaban, and discuss the ensuing open problems.

17 Jan 06: Dan Romik (UC Berkeley), Random sorting networks, permutohedron random walks, exclusion processes and sphere geodesics.

We present several random models for the process of sorting a list of numbers by applying a sequence of nonredundant adjacent transpositions. One natural model, the Uniform Sorting Network, exhibits a surprising level of symmetry and a remarkable conjectured link to geometry. Another model, the Permutohedron Random Walk, can be solved completely by representing it as a coupled family of totally asymmetric exclusion processes.
Joint work with Alexander Holroyd, Omer Angel, Balint Virag, Scott Sheffield and Rick Kenyon.

3 Jan 06: Noam Berger (UCLA), Random walks in a random environment.

We will present a few models of random walks in random environments. In the first part of the talk we will discuss the reversible case, where the use of analytic methods yields a good understanding of the processes. We will focus on several results and a number of open problems. The second part of the talk will be dedicated to the non-reversible case where little is known. We will presnt the main open problems and some partial results.

28 Dec 05: Assaf Naor (MS Research), Recent progress on bi-Lipschitz embeddings.

We will survey recent results on bi-Lipschitz embeddings of metric spaces into normed spaces. We will not discuss methods for proving non-embeddabilty results, but rather put emphasis on describing various new positive results and embedding techniques, and present conjectures and challenges for future research.

20 Dec 05: Asaf Nachmias (UC Berkeley), The critical random graph, with martingales.

The random graph model, G(n,p), is obtained from the complete graph on n vertices by independently retaining each edge with probability p and erasing it with probability 1-p. This model was introduced by Erdos and Renyi, who discovered that for p=c/n, the largest connected component of G(n,p) undergoes a "double jump" as c grows; Its size is of order log(n) for c<1, of order n^{2/3} for c=1, and linear for c>1. A complete proof for the case c=1 was only given much later (see Luczak, Pittel and Wierman 1994, and Aldous 1997), however all previous proofs of this fact are quite involved. We present simple proofs of these facts. Our methods also yield a simple proof for a Theorem of Bollobas concerning the supercritical phase, and can be used to analyze other models, such as critical percolation on a random regular graph. Joint work with Yuval Peres.

13 Dec 05: Ariel Yadin (WEINST), Random Images of graphs (II).

We start with a technique introduced by Jeff Kahn, using entropy to bound the size of a random image of the graph G = Q_d, the d-dimensional discrete cube. Then we show how Kahn's result applies to the more general setting of vertex transitive graphs (with large enough degree). We also provide a method for proving lower bounds on the size of the range, when the degree is small enough. These results are joint work with Itai Benjamini and Amir Yehudayoff.

6 Dec 05: Ariel Yadin (WEINST), Random Images of graphs.

A graph-homomorphism is a mapping between two graphs, that preserves edges. Fix a graph G and a vertex v in G, and let Hom(G,Z) be the set of all homomorphisms from G to Z (the integers, viewed naturally as a graph) such that v is mapped to 0. We study images of random elements of Hom(G,Z). When G = [0,n], a random element of Hom(G,Z) is just a n-step random walk on Z.

29 Nov 05: Emanuel Milman (WEINST), A taste of Geometry with a probabilistic flavour: On a recent Theorem of Schechtman (II).

We will present the proof of Schechtman's Theorem described in the previous lecture.

22 Nov 05: Emanuel Milman (WEINST), A taste of Geometry with a probabilistic flavour: On a recent Theorem of Schechtman.

In many fields, ranging from Computer Science to Theoretical Mathematics, finding simple structures inside complex ones is of crucial importance. In Convex Geometry, one of the most fundamental results is Dvoretsky's Theorem, which roughly states that one can find in any n-dimensional convex body a central section of dimension log(n) which is close to a ball. Another example of dimension reduction is the Johnson-Lindestrauss Lemma, which states that given m points (in a Hilbert space), a projection onto a log(m) dimensional random subspace will preserve the distances between the original points (up to some factor and within some error). We will present a recent Theorem of Gideon Schechtman, which generalizes the above mentioned results (and several others).

15 Nov 05: Boris Solomyak (U Washington), Bernoulli convolutions and fractal geometry (II).

Self-similar sets and measures are some of the basic objects in fractal geometry. Their dimension properties are poorly understood when the construction involves an "overlap." Then one can try to determine what happens for a "typical" (almost every) parameter value in a parametrized family of sets or measures. I will describe the "transversality method" which led to advances in these problems in the last ten years. On the other hand, in the overlapping case there are "exceptions," when the typical behavior fails, often of arithmetic nature. I will explain how Pisot numbers, a remarkable class of algebraic integers, play a role here.

8 Nov 05: Boris Solomyak (U Washington), Bernoulli convolutions and fractal geometry.

Bernoulli convolutions are a family of self-similar measures on the line, which have been studied since the 1930's by Erdos and others, and which more recently (since the 1980's) reappeared in connection with dynamical systems and fractal geometry. I will describe their history with (some) proofs, which should be quite accessible, as well as more recent developments and open problems.

1 Nov 05: Itai Benjamini (WEINST), Some problems in geometric probability.

The list of talks given farther in the past is available here.

Recycled Carpentry