Tue, 24 Nov 2009

14:30 - 15:30
L3

Dense $H$-free graphs are almost $(\chi(H)-1)$-partite

Peter Allen
(Warwick)
Abstract
Zarankiewicz showed that no $K_{r+1}$-free graph with minimum degree exceeding $(r-1)n/r$ can exist. This was generalised by Erdös and Stone, who showed that $K_{r+1}$ may be replaced by any graph $H$ with chromatic number $r+1$ at the cost of a $o(n)$ term added to the minimum degree.

Andr\'asfai, Erdös and S\'os proved a stability result for Zarankiewicz' theorem: $K_{r+1}$-free graphs with minimum degree exceeding $(3r-4)n/(3r-1)$ are forced to be $r$-partite. Recently, Alon and Sudakov used the Szemer\'edi Regularity Lemma to obtain a corresponding stability result for the Erdös-Stone theorem; however this result was not best possible. I will describe a simpler proof (avoiding the Regularity Lemma) of a stronger result which is conjectured to be best possible.
Tue, 01 Dec 2009
12:00
L3

On the classification of extremal black holes

James Lucietti
(Imperial)
Abstract

Extremal black holes are of interest as they are expected have simpler quantum descriptions than their non-extremal counterparts.  Any extremal black hole solution admits a well defined notion of a near horizon geometry which solves the same field equations. I will describe recent progress on the general understanding of such near horizon geometries in four and higher dimensions. This will include the proof of near-horizon symmetry enhancement and the explicit classification of near-horizon geometries (in a variety of settings). I will also discuss how one can use such results to prove classification/uniqueness theorems for asymptotically flat extremal vacuum black holes in four and five dimensions.

Tue, 17 Nov 2009
12:00
L3

Algebraically special solutions in more than four dimensions

Harvey Reall
(DAMTP Cambridge)
Abstract

Algebraic classification of the Weyl tensor is an important tool for solving the Einstein equation. I shall review the classification for spacetimes of dimension greater than four, and recent progress in using it to construct new exact solutions. The higher-dimensional generalization of the Goldberg-Sachs theorem will be discussed.

Tue, 17 Nov 2009

14:30 - 15:30
L3

Higher Order Tournaments

Imre Leader
(Cambridge)
Abstract
Given $n$ points in general position in the plane, how many of the triangles formed by them can contain the origin? This problem was solved 25 years ago by Boros and Furedi, who used a beautiful translation of the problem to a non-geometric setting. The talk will start with background, including this result, and will then go on to consider what happens in higher dimensions in the geometric and non-geometric cases.
Tue, 10 Nov 2009

14:50 - 15:40
L3

Random graphs with few disjoint cycles

Colin McDiarmid
(Oxford)
Abstract
HTML clipboard /*-->*/ /*-->*/

Fix a positive integer $k$, and consider the class of all graphs which do not have $k+1$  vertex-disjoint cycles.  A classical result of Erdos and P\'{o}sa says that each such graph $G$ contains a blocker of size at most $f(k)$.  Here a {\em blocker} is a set $B$ of vertices such that $G-B$ has no cycles.

 

We give a minor extension of this result, and deduce that almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of size $k$.  This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $R_n$ taken uniformly at random from the class: we see for example that the probability that $R_n$ is connected tends to a specified limit as $n \to \infty$.

 

There are corresponding results when we consider unlabelled graphs with few disjoint cycles. We consider also variants of the problem involving for example disjoint long cycles.

 

This is joint work with Valentas Kurauskas and Mihyun Kang.

Tue, 10 Nov 2009

14:00 - 14:50
L3

Oblivious Routing in the $L_p$ norm

Harald Raecke
(Warwick)
Abstract
HTML clipboard /*-->*/ /*-->*/

Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph $G=(V,E)$ is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.

 

We show the existence of an oblivious routing scheme with competitive ratio $O(\log n)$ and a lower bound of $\Omega(\log n/\logl\og n)$ for this model when the aggregation function agg is an $L_p$-norm.

 

Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics and the work on minimum congestion oblivious. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the $L_p$-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the $L_1$-norm while the result on congestion minmizing oblivious routing solves it for $L_\infty$. We give a single proof that shows the existence of a good tree-based oblivious routing for any $L_p$-norm.

Mon, 09 Nov 2009

12:00 - 13:00
L3

On the classification of Brane Tilings

Amihay Hanany
(Imperial College)
Abstract
Brane Tilings give a large class of SCFT's in 3+1 and 2+1 dimensions. In this talk I will discuss several attempt to classify all such models. Statistical properties of these models can be derived using some techniques in number theory.
Tue, 03 Nov 2009

14:30 - 15:30
L3

A general class of self-dual percolation models

Oliver Riordan
(Oxford)
Abstract
One of the main aims in the theory of percolation is to find the `critical probability' above which long range connections emerge from random local connections with a given pattern and certain individual probabilities. The quintessential example is Kesten's result from 1980 that if the edges of the square lattice are selected independently with probability $p$, then long range connections appear if and only if $p>1/2$.  The starting point is a certain self-duality property, observed already in the early 60s; the difficulty is not in this observation, but in proving that self-duality does imply criticality in this setting.

Since Kesten's result, more complicated duality properties have been used to determine a variety of other critical probabilities. Recently, Scullard and Ziff have described a very general class of self-dual percolation models; we show that for the entire class (in fact, a larger class), self-duality does imply criticality.

Subscribe to L3