July 23,
Abstract: A quadrature
formula for a given measure is a discrete measure having the same
first moments. I will survey classical
results in the theory of the (truncated)
moment problem, concentrating on the Gaussian
and related quadratures. One
application of these results is to find the
optimal tail bound for a random
variable given only the knowledge of its
first moments. I will then shift to
discuss Chebyshev-type
quadratures - quadratures
with all equal weights. I will
explain the problem of finding quantitative
bounds for the size of such
quadratures and discuss known and new results. Throughout,
I will mention open
problems.
The talk is mostly of a survey
nature and no prior knowledge on quadratures is
required.
July 16,
Tobias Mueller,
abstract: Let $X_1,\dots, X_n$ be independent, uniformly random points from
$[0,1]^2$. We prove that if we add edges between these points one by one by
order of increasing edge length then, with probability tending to 1 as the
number of points $n$ tends to $\infty$, the resulting
graph gets its first Hamilton cycle at exactly the same time it loses its last
vertex of degree less than two. This answers an open question of Penrose and
provides an analogue for the random geometric graph of a celebrated result of Ajtai, Koml{\'o}s and Szemer{\'e}di and independently
of Bollob\'as on the usual random graph. We are also
able to deduce very precise information on the limiting probability that the
random geometric graph is Hamiltonian analogous to a result of Koml{\'o}s
and Szemer{\'e}di on the
usual random graph. The proof generalizes to uniform random points on the
$d$-dimensional hypercube where the edge-lengths are measured using the $l_p$-norm for some $1<p\leq\infty$.
Time permitting, I will also give some other results
on
-------------------------------------------------------------
Abstract: A subset of the real line
has measure 0 if and only if some
Lipschitz function is not differentiable
anywhere in this set. But in higher
dimensions, whilst the "if" part is
still true, there exist exceptional
sets of measure 0 such that every Lipschitz function is differentiable on
a dense subset of the set. I will
show that such sets can even be compact
and of Hausdorff
dimension 1. I will explain why this is a step towards a
solution of a long-standing open problem in
geometric measure theory.
-----------------------------------------------------------
July 2, 2009
Abstract: In this talk we will show that the unit cube is a strict local minimizer for the Mahler volume product $vol_n(K)vol_n(K^*)$ in the class of origin symmetric convex bodies endowed with the Banach-Mazur distance (joint work with F. Nazarov, F. Petrov and D. Ryabogin).
------------------------------------------
Nathan Keller, Hebrew University, Noise Sensitivity of Functions on the Discrete Cube - Quantitative Results
Abstract: A Boolean function f:{0,1}^n -> {0,1} is called "noise sensitive" if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [BKS] showed that if the influences of all the coordinates on f are small then it must be noise sensitive (the formal condition is that the sum of squares of the influences is o(1).)
[BKS] showed a quantitative relation between the sum of squares of the influences and the noise sensitivity only when the sum of squares is bounded by n^{-c} for a constant c. We show a relation that is independent of n, and prove that it is tight. Our results hold also for a general product measure \mu_p on the discrete cube, as long as \log 1/p << \log n.
Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions.
In order to achieve it, we present a considerably shorter proof of Talagrand's lemma, which easily generalizes in various directions, including non-monotone functions.
Joint work with Guy Kindler.
------------------------------
Nicolas
Curien, ENS Paris and University Paris-Sud, Scaling limit of large
random planar maps and the brownian map
Abstract: Scaling limit of large random planar maps and the brownian map. A planar map is an embedding of a graph in the two-dimensional sphere. In the spirit of Donsker's theorem which says that nice random walks suitably rescaled converge toward brownian motion, we will discuss convergence of rescaled planar maps toward an random surface called brownian map. The sense of the convergence, and the limiting objects will be defined in the talk. Some properties of brownian maps will be exposed. For example, brownian maps are random metric spaces a.s. homoemorphic the sphere but with Hausdorff dimension equal to 4.
-----------------------
Wednesday, June 3, 2009, 11:00-13:00, Room 229 (Pekeris),
Martin Zerner,
Abstract: We consider the Green's function G_V(x,y) of -Laplacian+V on the lattice Z^d, where the potential V consists of i.i.d. nonnegative random variables V(z), z in Z^d. It is well-known that for any non-zero y in Z^d both G_V(0,ny) and its expected value E[G_V(0,ny)] tend exponentially fast to 0 as n tends to infinity. The exponential rates of decay of these two quantities are denoted by A_V(y) and
B_V(y) and are called the quenched and the annealed Lyapunov exponent, respectively.
In joint work with Elena Kosygina and Thomas S. Mountford we consider
A_{gamma*V}(y) and B_{gamma*V}(y), where gamma>0 is a scalar. Under the assumption that the potential has a finite first moment E[V(0)] we present a probabilistic and relatively elementary proof that both Lyapunov exponents scale like c*sqrt(gamma) as gamma tends to 0. Here the constant c is the same for the quenched as for the annealed exponent and is known explicitly. This improves results obtained previously by Wei-Min Wang.
----------------------------------------------------------------------------------------
Atilla Yilmaz, Weizmann, A
recent result on the equality of the quenched and averaged large deviation rate
functions for random walk in a random environment
Abstract: Consider large deviations for nearest-neighbor random walk in a uniformly elliptic i.i.d. environment. It is easy to see that the quenched and averaged rate functions are not identically equal. When the dimension is at least four and Sznitman's transience condition (T) is satisfied, I recently proved that these rate functions are finite and equal on a closed set whose interior contains every nonzero velocity at which the rate functions vanish. In this talk, I will present the proof of this result (except that I might skip some technical parts.)
--------------------------------------------------
Abstract: The Gowers uniformity norms U_k measure a certain kind of psuedo randomness. For example, a function f on a finite (large) dimensional vector space V over a finite field F has small U_2 norm if and only if all its Fourier coefficients are small - i.e it has no significant correlation with linear phase functions. The content of the inverse conjecture for the Gowers norms is that a similar relation exists between the U_k norms and polynomials of degree smaller than k; namely a function f has small U_k norm if and only if it has no significant correlation with a polynomial phase function of degree smaller than k. This conjecture plays an important role in counting solutions to systems of linear equations in subsets of vector spaces, and in polynomiality testing.
I will describe a proof of this conjecture in the case where char(F) is greater equal k, using tools from ergodic theory. In the low characteristic case, we show that if f has small U_k norm then it has no significant correlation with a polynomial phase function of bounded degree c(k).
I will define all relevant notions. Joint works with V. Bergelson and T. Tao.
----------------------------------------------------
Alexander Its,
Abstarct: Painlev\'e functions have been playing increasingly important role in random matrix theory since the early nineties works on the 2d quantum gravity of Br\'ezin and Kazakov, Duglas and Shenker, and Gross and Migdal and the works (also early nineties) of Mehta and Mahoux, and Tracy and Widom on the level spacing distributions. Indeed, the appearance of Painlev\'e fucntions in the field can be traced to 1970s-1980s works of Barouch, McCoy, Tracy, and Wu, and of Jimbo, Miwa, Mori and Sato on the quantum correlation functions. In this talk we will try to review these, and also some of the more recent results concerning Painlev\'e transcendents and random matrices. We will present a unified point view on the subject based on the Riemann-Hilbert method. The emphasis will be made on the various double scaling limits related to the universal properties of random matrices for which Painlev\'e functions provide an adequate ``special function environment''.
----------------------------------------------------
Sebastian Müller, Weizmann, From
Branching Markov chains to infinite-type Galton-Watson
processes, some
qualitative characteristics
Abstract: A branching Markov chain (BMC) is a system of particles in discrete
time. The BMC starts with one particle in an arbitrary starting position $x$.
At each time particles split up in offspring particles independently according
to some probability distributions that may depend on the locations of the
particles. The new particles then move independently according to a Markov
chain. An irreducible Markov chain is either recurrent or transient: either all
or none states are visited infinitely often. It turns out that this dichotomy
breaks down for BMC and that one can classify BMCs in
three different types. Let $\alpha(x)$ be the
probability that, starting the BMC in $x$, the state $x$ is hit infinitely
often by some particles. There are three possible regimes: transient
$(\alpha(x) = 0 \forall x)$,
weakly recurrent $(0 < \alpha(x) < 1 \forall
x)$ and strongly recurrent $(\alpha(x) = 1 \forall
x)$. We give equivalent criteria for transience of BMC and discuss some consequences
concerning generating functions and embedded branching processes.
It is well known that a Galton-Watson process dies
out almost surely if the mean number of offspring $m$ is less or equal $1$ and
survives with positive probability if $m>1.$ The
same is true for finite-type Galton-Watson processes
where the threshold between extinction and survival is the Perron-Frobenius
eigenvalue of the first moment matrix. The behaviour of infinite-type Galton-Watson
processes is more subtle; here four different notions of survival may occur.
Note that a BMC is a special type of infinite-type Galton-Watson
processes. We will discuss these different types and give a criterion for local
extinction and local survival in general and for global extinction and global
survival in some examples.
-----------------------------------------------------------------
Jean-Dominique
Deuschel, Berlin, Invariance principle for the
random conductance model with unbounded conductances
abstract: We study a continuous time random walk $X$ in an environment of i.i.d.
random conductances $\mu_e \in [1,\infty)$. We obtain heat
kernel bounds and prove a quenched invariance principle for $X$.
This holds even when $\bE \mu_e = \infty$.
Joint work with M. T. Barlow
Keywords: Random conductance model, heat kernel, invariance principle, corrector.
-------------------------------------------------------------------
March 5, 2009,
Abstract: Consider the classical balls-and-bins setup: n balls are thrown independently and uniformly into n bins. The most loaded bin then has log n/log log n balls with high probability. What happens when instead of throwing balls completely by random, there is an allocation algorithm which is given k uniformly and independently selected bins to choose from for the location of each ball? A well known result of Azar, Broder, Karlin & Upfal states that one can then achieve a maximal load of log_k log n, simply by putting the ball in the less loaded of the k bins. In order to implement this simple algorithm, one needs to keep track of the status of the entire array of n bins, which naively requires n log n bits of memory (and can be done non-naively with just 2n bits).
The
problem of what can be achieved under memory restrictions was raised by
A key ingredient in the proofs of the lower bounds is a large deviation inequality, which relates the sum of a sequence of bounded dependent random variables with the sum of their conditional expectations. This inequality may prove useful in other combinatorial or algorithmic problems.
Joint work with Noga Alon and Eyal Lubetzky.
--------------------------------------------------------------
WEDNESDAY, March 4, 2009,
Abstarct: The spectral gap of a doubly stochastic matrix is the reciprocal of the best constant in its associated Poincare inequality. This inequality can be formulated in purely metric terms, where the metric is a Hilbertian metric. This immediately allows us to define the spectral gap of a matrix with respect to other, non-Euclidean, geometries: a standard procedure which is used a lot in embedding theory, most strikingly as a method to prove non-embeddability in the coarse category. Motivated by a
combinatorial approach to the construction of bounded degree graph families which do not admit a coarse embedding into any uniformly convex nomed space (such spaces were first constructed by Lafforgue), we will naturally arrive at questions related to the behavior of non-linear spectral gaps under graph operations such as powering and zig-zag products. We will also discuss the issue of constructing base graphs for these iterative constructions, which lead to new analytic and geometric challenges.
Joint
work with
------------------------------------------------------------------
Rom Pinchasi, Technion, Using Duality and Euler's formula in the plane
Abstract: We will present the principle of duality between points and lines in the plane in connection with Euler's formula. We will then present two examples of using these simple principles in giving surprisingly elegant solutions to long standing open problems.
--------------------------------------------------------------------
February
12, 2009
Alice Guionnet, Ecole Normal Superieure de Lyon, Topological expansion for random matrices Abstarct:
Integrals of
random matrices are known to be related to
the enumeration of graphs sorted by their genera since
the work of 't Hooft and Brezin, Itzykson, Parisi and
Zuber in the seventies. We shall review this idea and
recent progresses in mathematics in this direction.
------------------------
Abstract: We shall discuss the distribution of extreme eigenvalues for several classes of random matrices with independent entries. In particular,we shall discuss the results of Soshnikov and some of their recent extensions, and the combinatorial questions that appear in the proofs. Based on joint work with Ohad Feldheim.
-----------------------
Nayantara
Bhatnagar,
Consider the uniform distribution over k-colorings of the complete tree of height h and branching factor D. As h tends to infinity, for what values of k is the color at the root conditioned on a fixed coloring of the leaves uniformly distributed over all k colors? It is straightforward to show the existence of colorings of the leaves which ``freeze'' the entire tree when k \le D+1. What happens for a typical coloring of the leaves? When the leaves have a non-vanishing influence on the color of the root in expectation over random colorings of the leaves, reconstruction is said to hold.
When k < D/ ln(D), it is known that reconstruction is possible while for k > D it is easy to show that reconstruction is not possible. We prove that for k > D/ ln(D), with high probability over the colorings of the leaves the influence at the root decays exponentially fast with the depth of the tree and reconstruction does not hold.
-----------------------------------------------------------------------------------------------------
Eyal Lubetzky,
Microsoft Research, Cutoff phenomena for random walks on random regular
graphs
Abstract:
The cutoff phenomenon describes a sharp transition in the convergence of a family of ergodic finite Markov chains to equilibrium. Many natural families of chains are believed to exhibit cutoff, and yet establishing this fact is often extremely challenging. An important such family of chains is the random walk on G(n,d), a random d-regular graph on n vertices. It is well known that the spectral gap of this class of chains for d fixed is constant, implying a mixing-time of O(\log n). According to a conjecture of Peres, the simple random walk on G(n,d) for any fixed d should then exhibit cutoff whp. As a special case of this, Durrett conjectured that the mixing time of the lazy random walk on a random 3-regular graph is whp (6+o(1))\log_2(n).
In this work we confirm the above conjectures, and establish cutoff in total-variation, its location and its optimal window, both for simple and for non-backtracking random walks on G(n,d). Namely, for any fixed d, the simple random walk on G(n,d) whp has cutoff at [d/(d-2)]\log_{d-1}(n) with window order \sqrt{\log n}. Surprisingly, the non-backtracking random walk on G(n,d) whp has cutoff already at \log_{d-1}(n) with constant window order. We further extend these results to G(n,d) for any d=n^{o(1)} (beyond which the mixing time is O(1)), provide efficient algorithms for testing cutoff, as well as give explicit constructions where cutoff occurs.
Joint work with Allan Sly.
------------------------------------------------------------------------------
Abstract:
We consider a Poisson point process in the plane. Its Voronoi
diagram is
the partition of the plane defined by matching to every point of the
Poisson process those points of the plane which are closer to it than to
any other point of the Poisson process. Like all planar maps, the
Poisson-Voronoi diagram can be (properly) colored
with 4 colors. But how
many colors are required to do it in a translation-equivariant
way? (roughly speaking,
we ask for a coloring algorithm which does not depend on a starting point. In
dimension 1, 2 colors are enough for non-equivariant colorings,
but 3 are
needed for equivariant ones).
Our main result is that this can be done with 6 colors. The construction is
a variant of the 6 coloring algorithm for finite planar maps, and its analysis
requires probabilistic estimates showing that the coloring produced is
"almost independent" at large distances.
Other results and the cases of dimensions one and three will also be discussed.
This is joint work with Omer Angel,
---------------------------------------------------
Ilya Goldsheid, Queen Mary University of London, Lyapunov exponents of products of non-identically
distributed random matrices.
----------------------------------------------------
Ariel
Yadin, Weizmann, Loop-erased random walk on planar
graphs
Abstract:
This
talk focuses on loop-erased random walk, or LERW. LERW is a random self-avoiding curve obtained
by erasing the loop in the trajectory of a random walk in chronological order. Lawler, Schramm, and Werner proved that LERW
on the Euclidean plane converges to SLE(2) as the mesh
goes to 0. SLE, or Schramm-Loewner Evolution, is a fascinating random process
discovered by Oded Schramm in 1999. SLE
arises as the scaling limit of many models in mathematical physics. It has many wonderful properties, perhaps the
most important is ``conformal invariance".
Lawler,
Schramm, and Werner's proof for the scaling limit of LERW essentially uses the
symmetry of the lattice structure. The
question arises whether a similar result holds even under perturbed lattices;
for example, if only a small portion of edges are removed from the original
lattice.
We
extend Lawler, Schramm and Werner's result:
For any planar Markov chain (that is a Markov chain embedded into the
complex plane so that edges do not cross one another), if the scaling limit of
the Markov chain is planar Brownian motion, then the scaling limit of the loop
erasure of the Markov chain is SLE(2).
One main example, is loop-erased random walk on the super-critical
percolation cluster; that is, the infinite component after super-critical
percolation on $Z^2$. Berger and Biskup showed that the random walk on the super-critical
percolation cluster converges to Brownian motion. Thus, our result implies that the loop-erased
random walk on the super-critical percolation cluster converges to SLE(2).
Joint work with Amir Yehudayoff.
---------------------------------------------------
Uri Shapira, Hebrew University, A
solution to an open problem of Cassels
Abstract: We prove existence of
real numbers x,y, possessing
the following property:
For any real a,b, liminf n ||nx - a|| ||ny - b|| = 0, where
||c|| denotes the distance of c to the nearest integer.
This answers a 50 years old
question of Cassels.
The most interesting part of the
result is that there are algebraic numbers with the above property!!!
In the lecture we shall make
friends with two nice spaces: The space of lattices and the space of grids. We
shall investigate dynamical questions in these spaces and derive the above
results from the dynamical information.
-----------------------------------------------------------------------------
Allan Sly, University of California, Berkeley, Mixing on Random Graphs
Abstract: Understanding Gibbs measures on trees and their spatial mixing thresholds (uniqueness, strong spatial mixing, reconstruction) can give insight into the behavior of Gibbs measures on general graphs, in particular random graphs which are locally tree-like. We discuss mixing of the Glauber dynamics of the Ising model and random colourings and their relationship to spatial mixing thresholds.
Based on
joint work with
----------------------------------
Abstract: We show that for convex domains in Euclidean space, Cheeger's isoperimetric inequality, spectral gap of the Neumann Laplacian, exponential concentration of Lipschitz functions, and any arbitrarily slow (but fixed) tail-decay of these functions, are all equivalent (to within universal constants, independent of the dimension). This substantially extends previous results of Maz'ya, Cheeger, Gromov--Milman, Buser and Ledoux. As an application, we conclude a sharp quantitative stability result for the spectral gap of convex domains under convex perturbations which preserve volume (up to
constants) and under maps which are ``on-average'' Lipschitz. We also provide a new characterization of the Cheeger constant for convex domains, as one over the expectation of the distance from the ``worst'' Borel set having half the volume of the domain. In addition, we easily recover (and extend) many previously known lower bounds, due to Payne--Weinberger, Li--Yau, Kannan--Lov\'asz--Simonovits, Bobkov and Sodin, on the Cheeger constant of convex domains. The proof involves estimates on the diffusion semi-group following Bakry--Ledoux and a result from Riemannian Geometry on the concavity of the isoperimetric profile. Our results extend to the more general setting of Riemannian manifolds with density which satisfy the $CD(0,\infty)$ curvature-dimension condition of Bakry-\'Emery.
----------------------------------------------------
This talk will give an overview of some recent results on inapproximability of NP-complete problems and their connections to discrete Fourier analysis and isoperimetric problems.
----------------------------------------------------
July 10, 2008
Gerard
Ben-Arous, Courant Institute, TBA
-----------------------------------------------------
Abstract: In 1985 Bourgain gave a discrete metric characterization of
when a normed space admits an equivalent uniformly convex norm: this
happens if and only if the space does not contain arbitrarily large
complete binary trees with low distortion. Bourgain's theorem was the
first successful step in a research program that was inspired by a
theorem of Ribe from 1976, which suggested that certain linear
properties of normed spaces are actually metric properties in
disguise. In this talk we will revisit Bourgain's solution in a
quantitative way: we will obtain a metric characterization of the
degree to which a norm is uniformly convex. It turns out that this
question exhibits unexpected subtleties and surprising differences
from the linear theory of normed spaces and from the theory of metric
type and cotype. Nevertheless, we will be able to show that a normed
space has an equivalent norm with modulus of uniform convexity of
power type p if and only if a concrete metric inequality called Markov
p-Convexity is satisfied. This inequality controls the rate at which certain
Markov chains diverge in a metric space, and it is useful for problems in metric
geometry which do not necessarily involve linear spaces. We will
discuss some of these applications, as well as some unexpected counterexamples.
Joint work
with
---------------------------------------------------------------
We
consider one-dimensional Brownian motion conditioned (in a suitable
sense) to have a
local time at every point and at every moment bounded by some fixed constant. Our
main result shows that a phenomenon of entropic repulsion occurs: that is, this
process is ballistic and has an asymptotic velocity approximately 4.5860... as high as required by the conditioning (the exact value of
this constant involves the first zero of a Bessel function). I will also
describe other conditionings of Brownian motion in which this principle of
entropic repulsion manifests itself.
Joint work with
-------------------------------------------------------------------
Considering the Sherrington-Kirkpatrick Model of spin glasses, Comets and Neveau showed (among other things) that if there is no external field, the energy density satisfies a quenched CLT in the limit as the volume tends to infinity using Martingale Convergence Theorems. Rececently, Chatterjee gave an independent proof of this result using Stein's Method, and also applied this technique to prove limit laws for a number of other observables, such as local fields.
However, considering the flucatuations of the energy density in a non-zero external field, neither of these methods apply. Thus, the general case was left open and it was not clear how to proceed.
In this talk we resolve this problem, applying a combination of the cavity method and Stein's method, a powerful quantitative tool for proving CLT's (in the high temperature region).
Based on joint work w/ Sourav Chatterjee.
-------------------------------------------------------------------
Bond percolation on a graph G with parameter p in [0,1] is the random subgraph G_p of G obtained by independently deleting each edge with probability 1-p and retaining it with probability p. For many graphs, the size of the largest component of G_p exhibits a phase transition: it changes sharply from logarithmic to linear as p increases. When G is the complete graph, this model is known as the Erdos-Renyi random graph: at the phase transition, i.e. p=1/n, the largest component satisfies a power-law of order 2/3.
For which d-regular graphs does percolation with p=1/(d-1) exhibit similar "mean-field" behavior? We show that this occurs for graphs where the probability of a non-backtracking random walk to return to its initial location behaves as it does on the complete graph. In particular, the celebrated Lubotzky-Phillips-Sarnak expander graphs and Cartesian products of 2 or 3 complete graphs exhibit mean-field behavior at p=1/(d-1); surprisingly, a product of 4 complete graphs does not.
--------------------------------------------------------------------------
Bernhard
Haak, Universite Bordeaux, On Carleson
measure criteria in linear systems theory
----------------------------------------------------------------------------
Gidi
Amir,
We study an exclusion process on Z where
each particle is assigned a class (number in Z) and each particle tries to swap
places with its right neighbor with rate 1 if that neighbor has a higher class
number. (Alternatively, each edge of Z is "sorted" with rate 1)
With the right starting conditions, the position of each particle (normalized
by the time) converges to a constant speed. The speed of each particle is
uniform in [-1,1],
but there are strong dependencies between the behavior of different
particles. We study this exclusion process and the distribution of its related
speed process. In particular we show the existence of infinite
"convoys" – particles (with different classes) all converging
to the same speed. We also give some new symmetries
for the multi-type tasep. Some of our results apply
also to the partially asymmetric case as well.
This is joint work-in-progress with Omer
Angel and Benedek Valko
from the
All definitions will be given in the
lecture.
No prior knowledge of exclusion processes is
assumed.
---------------------------------------------------------------------------------------
Jonathon Peterson,
Abstract: In 1975 Kesten,
Kozlov, and Spitzer analyzed the annealed
(averaged) limiting
distributions for one-dimensional transient random
walks in random
environments (RWRE). In particular they showed that the
annealed limiting
distributions are related to the stable distritions.
In
this talk, I will
analyze the quenched (conditioned on the environment)
limiting distributions.
Somewhat surprisingly, the quenched behavior can
be very different from the annealed behavior. In
particular, for certain
laws on environments there are no quenched limiting
distributions.
-----------------------------------------------------------------------
NOTE special TIME:
Wednesday,
Yuval
Peres, Microsoft Research, Compression exponents of amenable groups and escape rates of random walks
Abstract: Let G be a countable amenable
group, equipped with a finite set of generators and a corresponding word metric
$d(x,y)$. The Hilbert-space compression exponent $a_*$
of G is the supremum of all $a>0$ such that there
exists a Lipschitz map $f$ from G to Hilbert space
and a constant $c>0$ so that for all $x,y$ in G,
the norm $||f(x)-f(y)||$ is at least $cd(x,y)^a.$ Let $b$ denote the escape rate exponent for simple
random walk (X_t) on the Cayley
graph of G, that is, suppose that $Ed(X_0,X_t)$ grows like $t^b$.
We prove that $2ba_*$ is at most $1$, and equality holds in many cases. In particular, for the wreath product of the
integer lattice $Z$ with itself, it was known that $b=3/4$, and we show that
$a_*=2/3$. A key open question is
whether the identity $2ba_*=1$ holds for all finitely-generated amenable G. (It is not even known whether $a_*$ is always
at least $1/2$). Our proof uses K. Ball's notion of Markov type for metric
spaces. We also obtain extensions to $L^p$
compression via p-stable random walks. (Joint work with
-----------------------------------------------------------------------------------------
February 28, 2008,
Ilya Goldsheid, University of London, RWRE on a strip, products of random
transformations, and Lyapunov exponents
Abstract. The study of asymptotic properties
of random walks (RW) in random environments (RE) on a strip of width $m$ can be
naturally reduced to that of products of random transformations of the set of
$m\times m$ stochastic matrices. In my talk, I shall explain several recent
(and relatively recent) results obtained via this approach. They extend to the
strip case some of the classical theorems of Kesten-Kozlov-Spitser
(1975), as well as the Sinai $(\log t)^2$ asymptotic behaviour (1982) which were proved for simple
one-dimensional RWRE.
-------------------------------------------------------------------
February 7, 2008,
--------------------------------------------------------------------
NOTE special TIME and VENUE:
Wednesday, January 30, 2008,
16:00-18:00, Lecture room 5 at
Erwin Bolthausen,
University of Zurich, A fixed-point
proof of central limit theorems for certain convolution equations
---------------------------------------------------------------------
NOTE special TIME and VENUE:
Wednesday, January 23, 2008,
16:00-18:00, Lecture room 5 at
Jay Rosen, City
University of New York, Existence
of a critical point for the infinite divisibility of squared Gaussian vectors
Abstract: Let (G_1,\ldots,
G_n) be a mean zero Gaussian vector in R^n with covariance
matrix \Gamma. Necessary and sufficient conditions for the infinite
divisibility of
(G^2_1,\ldots,
G^2_n) in terms of \Gamma have been
known for some time. More recent results of Eisenbaum
and Kaspi give necessary and sufficient
conditions in terms of \Gamma for
((G_1+r)^2,\ldots,
(G_n+r)^2) to be the infinitely divisible for all
real r. This is related to the local
times of an associated Markov process. We show that for certain \Gamma there
exists a critical r_0>0 such that
((G_1+r)^2,\ldots,
(G_n+r)^2) is infinitely divisible for all |r|\leq r_0 but not for |r|>r_0. Joint
work with Michael Marcus.
--------------------------------------------------------------------
January 17 + 24, 2008
The following question could have appeard in a calculus undergraduate textbook. Consider
continuous real-valued functions defined on a set of reals
X. Is it true that:
(*) Whenever the functions f_n converge pointwise to 0,
there are positive reals epsilon_n converging to 0,
such that for each x
in X, |f_n(x)|<epsilon_n
for almost all n?
The answer is "Yes" if X is
countable, and "No" if X is the entire real line. For which X is the
answer positive?
The concept (*) is motivated by studies in
Harmonic analysis, involving sets of uniqueness for trigonometric series. (We
will not give details about that.)
Another concept, due to Arhangelskii,
comes from the question whether a product of Fr'echet
spaces is Fr'echet, and involves a natural
amalgamation of a sequence of convergent sequences of functions. Recently, Bukovsky-Hales and independently Sakai proved that this
concept coincides with (*) above, which makes our question doubly interesting.
We will try to give a complete proof of a
result that took us very long to believe:
(*) holds if, and
only if, each Borel image of X in the Baire space is bounded (with respect to eventual
dominance).
This implies a solution of a variety of
problems posed in the literature. In fact, we are not aware of any problem concerning
these concepts which remains open in light of this result. It also has an
application to a question on approximating discontinuous functions by
continuous ones, and a question whose positive solution would lead to a
solution of a rather old problem of Vinokurov.
Two GFAP meetings will be dedicated to this
work, so that all required definitions will be given, as well as the details of
the main proofs.
This is a very recent joint work with Lyubomyr Zdomskyy.
------------------------------------------------------------------------------------
NOTE special TIME and VENUE:
Wednesday, January 16, 2008,
16:00-18:00, Lecture room 5 at
Atilla Yilmaz, New
York University, Large deviations for
random walk in a random environment
Random walk in a random environment is a
discrete time Markov chain on $\mathbb{Z}^d$ with random transition probabilities $\pi(x,x+y)$. The collection $\omega = (\pi(x,x+y))_{x,y}$ is the called
the environment. If $(X_n)_n$
denotes the path of the``particle", $(T_{X_n}\omega)_n$ is a Markov chain on the space of
environments $\Omega$. Here, $T$ denotes the spatial shift on $\Omega$ and the
chain is called the ``environment Markov chain". This approach, known as
taking the point of view of the particle, is standard in the study of random
media.
In this talk, I will ask the following vague
question: ``Conditioned on the particle having asymptotic velocity equal to a
given atypical vector, how does the environment Markov chain behave?". My answer to various rigorous formulations of this
question will involve equality of quenched and averaged rates in some cases, Doob transforms, level-2 large deviation principles, and minimizers of certain variational
formulae.
------------------------------------------------------------------------
January 10, 2008,
NOTE special TIME
December
27, 2007,
One of the main questions that arise when
studying random and quasi-random structures is which properties P are such that
any object that satisfies P ``behaves'' like a truly random one. In the context
of graphs, Chung, Graham, and Wilson call a graph p-quasi-random if it
satisfies a long list of properties that hold in G(n,p) with high probability, like edge distribution,
spectral gap, cut size, and more.
Our main result here is that the following
holds for *any* fixed graph H: if a graph G has the property that the
distribution of induced copies of H in a graph G is close (in a well defined
way) to the distribution we would expect to have in G(n,p), then G is either p-quasi-random or q-quasi-random,
for some q=q(p,H). In other words, having the correct
distribution of induced copies of any single graph H,
is enough to guarantee that a graph has all the properties of a random one.
The talk will be self contained and will not
assume any prior knowledge.
Joint work with Raphy
Yuster
NOTE special TIME and VENUE:
Wednesday, December 26, 2007, 16:00-18:00, Lecture room 1.
Oded
Schramm, Microsoft Research, Testing graphs for planarity
Abstract: Suppose that you can sample
vertices in a big graph and ask about their neighbors. Your task is to decide
with as few questions as possible if the graph satisfies some property. Given
an a priori bound on the vertex degrees and given a positive s, we show that
with a bounded number of queries you can distinguish between planar graphs and
graphs that are s-far from being planar (in an appropriate sense). The testing
procedure is randomized and has some chance of failing, but the probability of
an incorrect answer can be made arbitrarily small, regardless of the graph
being tested. A similar result holds for all minor-closed properties. This is
joint work with
NOTE
slight change in TIME
December
13, 2007,
Robert Krauthgmaer , Weizmann Institute, On embedding edit distance into L_1
The edit distance (aka
Levenshtein distance) between two strings is the
number of character insertions, deletions and substitutions required to
transform one string to the other. A very powerful paradigm for solving computational
problems on the metric space induced by the edit distance is to embed this
metric into L_1, using a low-distortion map (if possible).
I will first
present a low-distortion embedding of edit distance on permutations (aka the Ulam metric) [based on
joint work (i) with Moses Charikar, and (ii) with Parikshit
Gopalan and T.S. Jayram].
I will then discuss lower bounds on the distortion required to embed edit
distance on 0-1 strings [joint work with Yuval Rabani]
and, more briefly, on permutations [joint work with Alex Andoni].
A simple random walk (SRW) on a graph is a
Markov chain whose state space is the vertex set and the next state
distribution is uniform among the neighbors of the current state. A graph is called recurrent if a SRW on it
returns to the starting vertex with probability 1, and called transient
otherwise. The path of a walk on a graph is simply the set of edges this walk
has traversed.
Our main result is that the path of a SRW on
any graph is a recurrent graph. The proof uses the electrical network
interpretation of random walks.
We will give a sketch of the proof,
including the necessary background, and discuss related questions and
conjectures.
Based on joint
works with
We
consider the problem of embedding vectors from an arbitrary
Euclidean space into a low dimensional Euclidean space, while
preserving up to a small distortion, a subset of the distances. In
particular, preserving only the distance of each vector to a small
number of its nearest neighbors. We show that even when the subset
of distances we wish to preserve is very small, the problem does
not become easier than when one requires to preserve all
the
distances.
Joint work with
Concentration of measure is a fundamental phenomenon in
high-dimensional geometry with far-reaching applications in fields
such as probability theory, functional analysis, computer science,
statistics, and machine learning.
Concentration bounds for non-product, non-Haar measures are fairly
recent: the first such result was obtained for contracting Markov
chains by Marton in 1996. Since then, several other such results have
been proved; with few exceptions, these rely on coupling techniques.
Though coupling is of unquestionable utility as a theoretical tool,
it appears to have some limitations. Coupling has yet to be used to
obtain bounds for more general Markov-type processes: hidden (or
partially observed) Markov chains, Markov trees, etc. As an
alternative to coupling, we apply the elementary Markov contraction
lemma in a novel way, to obtain simple, useful, and apparently
new concentration results for the various Markov-type processes. Our
technique is generic and holds the potential to yield numerous
results in this vein.
This talk is intended for a broad mathematical audience:
background, definitions, and motivation will be provided.
Christophe Garban, Universite Paris-Sud & ENS Paris, The
Fourier Spectrum of critical
percolation
The indicator function for the existence of
a percolation crossing in an n by n square can be seen as a function on the
discrete cube $\{-1,1\}^E$, where $E$ is the set of edges. As such, it admits a
``Fourier'' expansion. In a joint work with Gabor Pete and Oded Schramm, we
obtain sharp estimates for the ``weight'' of the Fourier coefficients at
different frequencies. This good undertsanding of the
spectrum has nice consequences for the model of dynamical percolation. For
instance, we can prove in the case of the triangular lattice that the dimension
of exceptional times is 31/36, and in the Z^2 case, we
can prove the existence of such exceptional times.
Pierre Nolin, Ecole Normale Supérieure
& Université Paris-Sud,
Some properties of near-critical
percolation
In two dimensions, a precise description of percolation at the critical
point was made possible by Schramm’s SLE processes, studied by Lawler,
Schramm and Werner, and by Smirnov’s proof of conformal invariance.
Combined with Kesten’s scaling results, this
description then provides a good picture of near-critical percolation, for
instance the critical exponents describing the main characteristic functions
(such as the density of the infinite cluster or the characteristic length).
We will discuss the off-critical regime, in particular the possible
scaling limits. Even if they are not conformal invariant, it seems natural to
try to relate them to SLE(6): we will show that they
actually share the same exponents and dimension properties. However, they also
are “locally” asymmetric, on every scale, so that their laws turn
out to be singular with respect to that of SLE(6).
This is joint work with Wendelin Werner.
For previous years see:
http://www.cs.biu.ac.il/~tsaban/gfap.html
and
http://www.wisdom.weizmann.ac.il/mathusers/gideon/seminar.html