Past

The transportation problem (TP) is a classic problem in operations research. The problem was posed for the first time by Hitchcock in 1941 [Hitchcock, 1941] and independently by Koopmans in 1947 [Koopmans, 1948], and appears in any standard introductory course on operations research.

The mxn TP has m supply points and n demand points. Each supply Point i holds a quantity r_i, and each demand point j wants a quantity c_j, with the sum of femands equal to the sum of supplies. A solution to the problem can be written as a mxn matrix X with entries decision x_{ij} having value equal to the amount transported from supply point i to demand point j. The objective is to minimize total transportation costs when unit transporation costs between each supply and each demand point are given.

The set of feasible solutions of TP, is called the transportation polytope.

The 1-skeleton (edge graph) of this polytope is defined as the graph with vertices the vertices of the polytope and edges its 1-dimensional faces.

In 1957 W.M. Hirsch stated his famous conjecture cf. [Dantzig, 1963]) saying that any d-dimensional polytope with n facets has diameter at most n-d. So far the best bound for any polytope is O(n^{\log d+1}) [Kalai and Kleitman, 1992]. Any strongly polynomial bound is still lacking. Such bounds have been proved for some special classes of polytopes (for examples, see [Schrijver, 1995]). Among those are some special classes of transportation polytopes [Balinski, 1974],[Bolker, 1972] and the polytope of the dual of TP [Balinski, 1974].

The first strongly polynomial bound on the diameter of the transportation polytope was given by Dyer and Frieze [DyerFrieze, 1994]. Actually, they prove a bound on the diameter of any polytope {x|Ax=b} where A is a totally unimodular matrix. The proof is complicated and indirect, using the probabilistic method. Moreover, the bound is huge O(m^{16}n^3ln(mn))3) assuming m less than or equal to n.

We will give a simple proof that the diameter of the transportation polytope is less than 8(m+n-2). The proof is constructive: it gives an algorithm that describes how to go from any vertex to any other vertex on the transportation polytope in less than 8(m+n-2) steps along the edges.

According to the Hirsch Conjecture the bound on the TP polytope should be

m+n-1. Thus we are within a multiplicative factor 8 of the Hirsch bound.

Recently C. Hurkens refined our analysis and diminished the bound by a factor 2, arriving at 4(m+n-2). I will indicate the way he achieved this as well.

Static vacuum data and their conformal classes play an important role in the discussion of the smoothness of gravitational fields at null infinity. We study the question under which conditions such data admit non-trivial conformal rescalings which lead again to such data. Some of the restrictions implied by this requirement are discussed and it is shown that there exists a 3-parameter family of static vacuum data which are not conformally flat and which admit non-trivial rescalings.

Many biological time series appear nonlinear or chaotic, and from biomechanical principles we can explain these empirical observations. For this reason, methods from nonlinear time series analysis have become important tools to characterise these systems. Nonetheless, a very large proportion of these signals appear to contain significant noise. This randomness cannot be explained within the assumptions of pure deterministic nonlinearity, and, as such, is often treated as a nuisance to be ignored or otherwise mitigated. However, recent work points to this noise component containing valuable information. Random dynamical systems offer a unified framework within which to understand the interplay between deterministic and stochastic dynamical sources. This talk will discuss recent attempts to exploit this synthesis of stochastic and deterministic dynamics in biological signals. It will include a case study from speech science.

I will review the construction of algebraic de Rham cohomology, relative de Rham cohomology, and the Gauss-Manin connection. I will then show how we can find a basis for the cohomology and the matrix for the connection with respect to this basis for certain families of curves sitting in weighted projective spaces.

Joint work with Martin Dyer (Leeds) and Leslie Goldberg (Liverpool).

A spin system may be modelled as a graph, in which edges (bonds) indicate interactions between adjacent vertices (sites). A configuration of the system is an assignment of colours (spins) to the vertices of the graph. The interactions between adjacent spins define a certain distribution, the Boltzmann distribution, on configurations. To sample from this distribution it is usually necessary to simulate one of a number of Markov chains on the space of all configurations. Theoretical analyses of the mixing time of these Markov chains usually assume that spins are updated at single vertices chosen uniformly at random. Actual simulations, in contrast, may make (random) updates according to a deterministic, usually highly structured pattern. We'll explore the relationships between systematic scan and random single-site updates, and also between classical uniqueness conditions from statistical physics and more recent techniques in mixing time analysis.

Both Kazhdan and Haagerup properties turn out to be related to actions

of

groups on median spaces and on spaces with measured walls.

These relationships allows to study the connection between Kazhdan

property (T) and the fixed point property

for affine actions on $L^p$ spaces, on one hand.

On the other hand, they allow to discuss conjugacy classes of subgroups

with property (T) in Mapping Class Groups. The latter result

is due to the existence of a natural structure of measured walls

on the asymptotic cone of a Mapping Class Group.

The talk is on joint work with I. Chatterji and F. Haglund

(first part), and J. Behrstock and M. Sapir (second part).

In the past the theory of rough paths has proven to be an elegant tool for deriving support theorems and large deviation principles. In this talk I will explain how this approach can be used in the analysis of stochastic flows generated by Kunita SDE's. As driving processes I will consider general Banach space valued Wiener processes

I will push Schanuel's conjecture in four directions: defining a dimension

theory (pregeometry), blurred exponential functions, exponential maps of

more general groups, and converses. The goal is to explain how Zilber's

conjecture on complex exponentiation is true at least in a "geometric"

sense, and how this can be proved without solving the difficult number

theoretic conjectures. If time permits, I will explain some connections

with diophantine geometry.

The evaluation of oscillatory integrals is often considered to be a computationally challenging problem. However, in many cases, the exact opposite is true. Oscillatory integrals are cheaper to evaluate than non-oscillatory ones, even more so in higher dimensions. The simplest strategy that illustrates the general approach is to truncate an asymptotic expansion, where available. We show that an optimal strategy leads to the construction of certain unconventional Gaussian quadrature rules, that converge at twice the rate of asymptotic expansions. We examine a range of one-dimensional and higher dimensional, singular and highly oscillatory integrals.

We survey the classification of structures interpretable in o-minimal theories in terms of thorn-minimal types. We show that a necessary and sufficient condition for such a structure to interpret a real closed field is that it has a non-locally modular unstable type. We also show that assuming Zilber's Trichotomy for strongly minimal sets interpretable in o-minimal theories, such a structure interprets a pure algebraically closed field iff it has a global stable non-locally modular type. Finally, if time allows, we will discuss reasons to believe in Zilber's Trichotomy in the present context

A graph property is a first order property if it can be written as a logic sentence with variables ranging over the vertices of the graph.

A sequence of random graphs (G_n)_n satisfies the zero-one law if the probability that G_n satisfies P tends to either zero or one for every first order property P. This is for instance the case for G(n,p) if p is fixed. I will survey some of the most important results on the G(n,p)-model and then proceed to discuss some work in progress on other graph models.

One of the main tools in studying sparse random graphs with independence between different edges is local comparison with branching processes. Recently, this method has been used to determine the asymptotic behaviour of the diameter (largest graph distance between two points that are in the same component) of various sparse random graph models, giving results for $G(n,c/n)$ as special cases. Nick Wormald and I have applied this method to $G(n,c/n)$ itself, obtaining a much stronger result, with a best-possible error term. We also obtain results as $c$ varies with $n$, including results almost all the way down to the phase transition.

On parabolic and elliptic equations with VMO coefficients.

Abstract: An L_p-theory of divergence and non-divergence form elliptic and parabolic equations is presented.

The main coefficients are supposed to belong to the class VMO_x, which, in particular, contains all functions independent of x.

Weak uniqueness of the martingale problem associated with such equations is obtained

The Skorokhod reflection problem, originally introduced as a means for constructing solutions to stochastic differential equations in bounded regions, has found applications in many areas of Probability, for example in queueing-like stochastic dynamical systems; its uses range from methods for proving limit theorems to representations of local times of diffusions and control. In this talk, I will present several applications, e.g. to Levy stochastic networks and to queueing-like systems driven by local times of Levy processes, and give an order-theoretic approach to the problem by extending the domain of functions involved from the real line to a fairly arbitrary partially ordered set. I will also discuss how Palm probabilities can be used in connection with the Skorokhod problem to obtain information about stationary solutions of certain systems.

I consider the Metropolis Markov Chain based on the nearest neighbor random walk on the positive half of the Mean Field Ising Model, i.e., on those vectors from $\{−1, 1\}^N$ which contain more $1$ than $−1$. Using randomly-chosen paths I prove a lower bound for the Spectral Gap of this chain which is of order $N^-2$ and which does not depend on the inverse temperature $\beta$. In conjunction with decomposition results such as those in Jerrum, Son, Tetali and Vigoda (2004) this result may be useful for bounding the spectral gaps of more complex Markov chains on the Mean Field Ising Model which may be decomposed into Metropolis chains. As an example, I apply the result to two Multilevel Markov Chain Monte Carlo algorithms, Swapping and Simulated Tempering. Improving a result by Madras and Zheng (2002), I show that the spectral gaps of both algorithms on the (full) Mean Field Ising Model are bounded from below by the reciprocal of a polynomial in the lattice size $N$ and in the inverse temperature $\beta$.

We shall begin with simple Weyl type asymptotic formulae for the spectrum of Dirichlet Laplacians and eventually prove a new result which I have recently obtained, jointly with J. Dolbeault and M. Loss. Following Eden and Foias, we derive a matrix version of a generalised Sobolev inequality in one dimension. This allows us to improve on the known estimates of best constants in Lieb-Thirring inequalities for the sum of the negative eigenvalues for multi-dimensional Schrödinger operators.

Bio: Ari Laptev received his PhD in Mathematics from Leningrad University (LU) in 1978, under the supervision of Michael Solomyak. He is well known for his contributions to the Spectral Theory of Differential Operators. Between 1972 - 77 and 1977- 82 he was employed as a junior researcher and as Assistant Professor at the Mathematics & Mechanics Department of LU. In 1981- 82 he held a post-doc position at the University of Stockholm and in 1982 he lost his position at LU due to his marriage to a British subject. Up until his emigration to England in 1987 he was working as a builder, constructing houses in small villages in the Novgorod district of Russia. In 1987 he was employed in Sweden, first as a lecturer at Linköping University and then from 1992 at the Royal Institute of Technology (KTH). In 1999 he became a professor at KTH and also Vice Chairman of its Mathematics Department. In 1992 he was granted Swedish citizenship. Ari Laptev was the President of the Swedish Mathematical Society from 2001 to 2003 and the President of the Organizing Committee of the Fourth European Congress of Mathematics in Stockholm in 2004. From January 2007 he has been employed by Imperial College London. Ari Laptev has supervised twelve PhD students. From January 2007 until the end of 2010 he is President of the European Mathematical Society.

Let N(A) be the number of integer solutions of x^2 + y^2

We present algorithms for dense LU and QR factorizations that minimize the cost of communication. One of today's challenging technology trends is the increased communication cost. This trend predicts that arithmetic will continue to improve exponentially faster than bandwidth, and bandwidth exponentially faster than latency. The new algorithms for dense QR and LU factorizations greatly reduce the amount of time spent communicating, relative to conventional algorithms.

This is joint work with James Demmel, Mark Hoemmen, Julien Langou, and Hua Xiang.