Mon, 09 May 2011
12:00
L3

CANCELLED

Sara Pasquetti
(QMUL)
Tue, 08 Jun 2010

14:30 - 15:30
L3

Rigidity of direction-length frameworks

Bill Jackson
(QMUL)
Abstract

Consider a configuration of points in $d$-dimensional Euclidean space

together with a set of constraints

which fix the direction or the distance between some pairs of points.

Basic questions are whether the constraints imply that the configuration

is unique or locally unique up to congruence, and whether it is bounded. I

will describe some solutions

and partial solutions to these questions.

Tue, 19 Jan 2010

14:30 - 15:30
L3

Shadows and intersections: stability and new proofs

Peter Keevash
(QMUL)
Abstract
We give a short new proof of a version of the Kruskal-Katona theorem due to Lov\'asz. Our method can be extended to a stability result, describing the approximate structure of configurations that are close to being extremal, which answers a question of Mubayi. This in turn leads to another combinatorial proof of a stability theorem for intersecting families, which was originally obtained by Friedgut using spectral techniques and then sharpened by Keevash and Mubayi by means of a purely combinatorial result of Frankl. We also give an algebraic perspective on these problems, giving yet another proof of intersection stability that relies on expansion of a certain Cayley graph of the symmetric group, and an algebraic generalisation of Lov\'asz’s theorem that answers a question of Frankl and Tokushige.
Tue, 26 May 2009

14:30 - 15:30
L3

Hamilton cycles in random geometric graphs

Mark Walters
(QMUL)
Abstract

The Gilbert model of a random geometric graph is the following: place points at random in a (two-dimensional) square box and join two if they are within distance $r$ of each other. For any standard graph property (e.g.  connectedness) we can ask whether the graph is likely to have this property.  If the property is monotone we can view the model as a process where we place our points and then increase $r$ until the property appears.  In this talk we consider the property that the graph has a Hamilton cycle.  It is obvious that a necessary condition for the existence of a Hamilton cycle is that the graph be 2-connected. We prove that, for asymptotically almost all collections of points, this is a sufficient condition: that is, the smallest $r$ for which the graph has a Hamilton cycle is exactly the smallest $r$ for which the graph is 2-connected.  This work is joint work with Jozsef Balogh and B\'ela Bollob\'as

Tue, 17 Feb 2009

14:30 - 15:30
L3

The edge correlation of random forests

Dudley Stark
(QMUL)
Abstract

The conjecture was made by Pemantle that a forest chosen uniformly at random from all forests in any finite graph G has the edge-negative association property. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices and derive related results for random trees.

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.

Subscribe to QMUL