Mon, 16 Feb 2009

12:00 - 13:00
L3

Yukawa Couplings from Monad Bundles

Andre Lukas
(Oxford)
Abstract
We present a straightforward, algebraic method for calculating the Yukawa couplings of a large class of non-standard embedding heterotic compactifications on Calabi-Yau threefolds. Our methodology covers, although is not restricted to, the positive monads over complete intersection Calabi-Yau manifolds. The algorithm involves the manipulation of polynomials and can be straightforwardly implemented on a computer. We present explicit examples and show how models with one Higgs multiplet and a rank-one mass matrix can be engineered.
Wed, 21 Jan 2009
16:00
L3

TBA

TBA
Tue, 10 Mar 2009

14:30 - 15:30
L3

Cycles in directed graphs

Peter Keevash
(QMUL)
Abstract

There are many theorems concerning cycles in graphs for which it is natural to seek analogous results for directed graphs. I will survey

recent progress on certain questions of this type. New results include

(i) a solution to a question of Thomassen on an analogue of Dirac’s theorem

for oriented graphs,

(ii) a theorem on packing cyclic triangles in tournaments that “almost” answers a question of Cuckler and Yuster, and

(iii) a bound for the smallest feedback arc set in a digraph with no short directed cycles, which is optimal up to a constant factor and extends a result of Chudnovsky, Seymour and Sullivan.

These are joint work respectively with (i) Kuhn and Osthus, (ii) Sudakov, and (iii) Fox and Sudakov.

Tue, 24 Feb 2009

14:30 - 15:30
L3

Synchronization and homomorphisms

Peter Cameron
(QMUL)
Abstract

A graph homomorphism is a mapping of vertices which takes edges to edges. The endomorphisms of a graph (homomorphisms to itself) form a submonoid of he full transformation monoid on the vertex set. In the other direction, there is a construction of a graph from a transformation monoid, which will be described in the talk. Composing these maps gives closure operators on graphs and on monoids which have some interesting properties. There are also connections with finite automata and permutation groups.

Tue, 10 Feb 2009

14:30 - 15:30
L3

The scaling limit of critical random graphs

Christina Goldschmidt
(Oxford)
Abstract

Consider the Erdos-Renyi random graph $G(n,p)$ inside the critical window, so that $p = n^{-1} + \lambda n^{-4/3}$ for some real \lambda. In

this regime, the largest components are of size $n^{2/3}$ and have finite surpluses (where the surplus of a component is the number of edges more than a tree that it has). Using a bijective correspondence between graphs and certain "marked random walks", we are able to give a (surprisingly simple) metric space description of the scaling limit of the ordered sequence of components, where edges in the original graph are re-scaled by $n^{-1/3}$. A limit component, given its size and surplus, is obtained by taking a continuum random tree (which is not a Brownian continuum random tree, but one whose distribution has been exponentially tilted) and making certain natural vertex identifications, which correspond to the surplus edges. This gives a metric space in which distances are calculated using paths in the original tree and the "shortcuts" induced by the vertex identifications. The limit of the whole critical random graph is then a collection of such

metric spaces. The convergence holds in a sufficiently strong sense (an appropriate version of the Gromov-Hausdorff distance) that we are able to deduce the convergence in distribution of the diameter of $G(n,p)$, re-scaled by $n^{-1/3}$, to a non-degenerate random variable, for $p$ in the critical window.

This is joint work (in progress!) with Louigi Addario-Berry (Universite de Montreal) and Nicolas Broutin (INRIA Rocquencourt).

Tue, 03 Feb 2009

14:30 - 15:30
L3

The t-dependence and t-improper chromatic numbers of random graphs

Ross Kang
(McGill)
Abstract

We consider a natural generalisation of the independence and chromatic numbers and study their behaviour in Erdos-Renyi random graphs. The t-dependence number of a graph G is the size of the largest subset of the vertices of G whose induced subgraph has maximum degree at most t. The t-improper chromatic number of G is the smallest number of parts needed in a partition of the vertex set of G such that each part induces a subgraph of maximum degree at most t. Clearly, when t = 0, these parameters are, respectively, the independence and chromatic numbers of G. For dense random graphs, we determine the asymptotic ehaviour of these parameters over the range of choices for the growth of t as a function of the number of vertices.

This is joint work with Nikolaos Fountoulakis and Colin McDiarmid.

Tue, 27 Jan 2009

14:30 - 15:30
L3

Random partial orders and random linear extensions

Graham Brightwell
(LSE)
Abstract

Random partial orders and random linear extensions

Several interesting models of random partial orders can be described via a

process that builds the partial order one step at a time, at each point

adding a new maximal element. This process therefore generates a linear

extension of the partial order in tandem with the partial order itself. A

natural condition to demand of such processes is that, if we condition on

the occurrence of some finite partial order after a given number of steps,

then each linear extension of that partial order is equally likely. This

condition is called "order-invariance".

The class of order-invariant processes includes processes generating a

random infinite partial order, as well as those that amount to taking a

random linear extension of a fixed infinite poset.

Our goal is to study order-invariant processes in general. In this talk, I

shall explain some of the problems that need to be resolved, and discuss

some of the combinatorial problems that arise.

(joint work with Malwina Luczak)

Tue, 20 Jan 2009

14:30 - 15:30
L3

Vertex Turan problems in the hypercube

John Talbot
(UCL)
Abstract
Let $Q_n=\{0,1\}^n$ be the $n$-dimensional hypercube. For $1\leq d \leq n$ and $F\subseteq Q_d$ we consider the question of how large $S\subseteq Q _n$ can be if every embedding $i:Q_d\to Q_n$ satisfies $i(F)\not\subseteq S$. We determine the asymptotic behaviour of the largest $F$-free subsets of $Q_n$ for a variety of $F$, in particular we generalise the sole non-trivial prior result in this area: $F=Q_2$ due to E.A. Kostochka. Many natural questions remain open. This is joint work with Robert Johnson.
Subscribe to L3