Mon, 23 May 2011

12:00 - 13:00
L3

Trivertices and SU(2)'s

Amihay Hanany
(Imperial College)
Abstract
Given a graph with lines and 3-valent vertices, one can construct, using a simple dictionary, a Lagrangian that has N=2 supersymmetry in 3+1 dimensions. This is a construction which generalizes the notion of a quiver. The vacuum moduli space of such a theory is well known to give moment map equations for a HyperKahler manifold. We will discuss the class of hyperkahler manifolds which arise due to such a construction and present their special properties. The Hilbert Series of these spaces can be computed and turns out to be a function of the number of external legs and loops in the graph but not on its detailed structure. The corresponding SCFT consequence of this property indicates a crucial universality of many Lagrangians, all of which have the same dynamics. The talk is based on http://arXiv.org/pdf/1012.2119.
Mon, 16 May 2011

12:00 - 13:30
L3

Stability conditions on local P^2

Tom Bridgeland
(Oxford)
Abstract
This talk will be about spaces of stability conditions. I will start by recalling Mike Douglas' original work on Pi-stability for D-branes, and go on to explain a couple of of the main open questions in the subject. The second half of the talk will focus on an illustrative example, namely the case of the local projective plane.
Mon, 09 May 2011
12:00
L3

CANCELLED

Sara Pasquetti
(QMUL)
Tue, 14 Jun 2011

14:30 - 15:30
L3

Ramsey Classes of Graphs and Beyond

Jaroslav Nesetril
(Prague)
Abstract

It is known that generic and universal structures and Ramsey classes are related. We explain this connection and complement it by some new examples. Particularly we disscuss universal and Ramsey classes defined by existence and non-existence of homomorphisms.

Tue, 07 Jun 2011

14:30 - 15:30
L3

Average-case performance of three-dimensional assignment heuristics

Gregory Sorkin
(LSE)
Abstract

The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to π^2/6.  In dimensions 3 and higher, the "planar" assignment problem is NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do?  In d dimensions, the expected cost is of order at least n^{2-d} and at most ln n times larger, but the upper bound is non-constructive.  For 3 dimensions, we show a heuristic capable of producing a solution within a factor n^ε of the lower bound, for any constant ε, in time of order roughly n^{1/ε}.  In dimensions 4 and higher, the question is wide open: we don't know any reasonable average-case assignment heuristic.

Tue, 31 May 2011

14:30 - 15:30
L3

Component structure of the vacant set induced by a random walk on a random graph

Colin Cooper
(King's College London)
Abstract

We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices or vacant set. In both cases, the size of the vacant set $N(t)$ can be obtained explicitly as a function of $t$. Let $\Gamma(t)$ be the subgraph induced by the vacant set. We show that, for random graphs $G_{n,p}$ above the connectivity threshold, and for random regular graphs $G_r$, for constant $r\geq 3$, there is a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for $t\leq (1-\epsilon)t^*$ we have a unique giant plus components of  size $O(\log n)$ and for $t\geq (1+\epsilon)t^*$ we have only components of  size $O(\log n)$.

In the case of $G_r$ we describe the likely degree sequence, size of the giant component and structure of the small ($O(\log n)$) size components.

Tue, 24 May 2011

14:30 - 15:30
L3

The degree distribution of random planar graphs

Angelika Steger
(ETH Zurich)
Abstract

A random planar graph $P_n$ is a graph drawn uniformly at random from the class of all (labelled) planar graphs on $n$ vertices. In this talk we show that with probability $1-o(1)$ the number of vertices of degree $k$ in $P_n$ is very close to a quantity $d_k n$ that we determine explicitly. Here $k=k(n) \le c \log n$. In the talk our main emphasis will be on the techniques for proving such results. (Joint work with Kosta Panagiotou.)

Tue, 10 May 2011

14:30 - 15:30
L3

Edge colouring multigraphs

Penny Haxell
(Waterloo)
Abstract

We highlight a technique for studying edge colourings of multigraphs, due to Tashkinov. This method is a sophisticated generalisation of the method of alternating paths, and builds upon earlier work by Kierstead and Goldberg. In particular we show how to apply it to a number of edge colouring problems, including the question of whether the class of multigraphs that attain equality in Vizing's classical bound can be characterised.

This talk represents joint work with Jessica McDonald.

Tue, 03 May 2011

14:30 - 15:30
L3

Hajos’ Conjecture is almost always true

Bruce Reed
(McGill)
Abstract

In 1961 Hajos conjectured that if a graph contains no subdivsion of a clique of order t then its chromatic number is less than t. In 1981, Erdos and Fajtlowicz showed that the conjecture is almost always false. We show it is almost always true. This is joint work with Keevash, Mohar, and McDiarmid.

Subscribe to L3