Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

Tue, 24/01/2012
14:30 		Mihyun Kang (TU Graz) Combinatorial Theory Seminar Add to calendar L3
The phase transition in random graph processes through the lens of PDE and singularity analysis
The phase transition deals with sudden global changes and is observed in many fundamental random discrete structures arising from statistical physics, mathematics and theoretical computer science, for example, Potts models, random graphs and random $ k $-SAT. The phase transition in random graphs refers to the phenomenon that there is a critical edge density, to which adding a small amount results in a drastic change of the size and structure of the largest component. In the Erdős–Rényi random graph process, which begins with an empty graph on $ n $ vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches $ n/2 $ and a giant component emerges. Since this seminal work of Erdős and Rényi, various random graph processes have been introduced and studied. In this talk we will discuss new approaches to study the size and structure of components near the critical point of random graph processes: key techniques are the classical ordinary differential equations method, a quasi-linear partial differential equation that tracks key statistics of the process, and singularity analysis.
Tue, 31/01/2012
14:30 		Lutz Warnke Combinatorial Theory Seminar Add to calendar L3
The early evolution of Achlioptas processes
In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. Although the evolution of such `local' modifications of the Erdös-Rényi random graph processes has received considerable attention during the last decade, so far only rather `simple' rules are well-understood. Indeed, the main focus has been on bounded size rules (where all component sizes larger than some constant B are treated the same way), and for more complex rules hardly any rigorous results are known. In this talk we will discuss a new approach that applies to many involved Achlioptas processes: it allows us to prove that certain key statistics are tightly concentrated during the early evolution of e.g. the sum and product rule. Joint work with Oliver Riordan.
Tue, 07/02/2012
14:30 		Imre Leader (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Positive projections
If $ A $ is a set of $ n $ positive integers, how small can the set $ \{ x/(x,y) : x,y \in A \} $ be? Here, as usual, $ (x,y) $ denotes the highest common factor of $ x $ and $ y $. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set $ A $ of $ n $ points in the integer grid $ {\bf Z}^d $, how small can $ (A-A)^+ $, the projection of the difference set of $ A $ onto the positive orthant, be? Freiman and Lev gave an example to show that (in any dimension) the size can be as small as $ n^{2/3} $ (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least $ n^{2/3} $, and they asked if this holds in any dimension. After some background material, the talk will focus on recent developments. Joint work with Béla Bollobás.
Tue, 14/02/2012
14:30 		Tobias Mueller, Amsterdam Combinatorial Theory Seminar Add to calendar L3
Line arrangements and geometric representations of graphs
A dot product representation of a graph assigns to each vertex $ s $ a vector $ v(s) $ in $ {\bf R}^k $ in such a way that $ v(s)^T v(t) $ is greater than $ 1 $ if and only $ st $ is an edge. Similarly, in a distance representation $ |v(s)-v(t)| $ is less than $ 1 $ if and only if $ st $ is an edge. I will discuss the solution of some open problems by Spinrad, Breu and Kirkpatrick and others on these and related geometric representations of graphs. The proofs make use of a connection to oriented pseudoline arrangements. (Joint work with Colin McDiarmid and Ross Kang)
Tue, 21/02/2012
14:30 		Mark Walters Combinatorial Theory Seminar Add to calendar L3
Lion and Man: Can both win?
Rado introduced the following `lion and man' game in the 1930's: two players (the lion and the man) are in the closed unit disc and they can run at the same speed. The lion would like to catch the man and the man would like to avoid being captured.This game has a chequered history with several false `winning strategies' before Besicovitch finally gave a genuine winning strategy.We ask the surprising question: can both players win?
Tue, 28/02/2012
14:30 		Penny Haxell (Waterloo) Combinatorial Theory Seminar Add to calendar L3
On packing and covering in hypergraphs
We discuss some recent developments on the following long-standing problem known as Ryser's conjecture. Let $ H $ be an $ r $-partite $ r $-uniform hypergraph. A matching in $ H $ is a set of disjoint edges, and we denote by $ \nu(H) $ the maximum size of a matching in $ H $. A cover of $ H $ is a set of vertices that intersects every edge of $ H $. It is clear that there exists a cover of $ H $ of size at most $ r\nu(H) $, but it is conjectured that there is always a cover of size at most $ (r-1)\nu(H) $.
Tue, 06/03/2012
14:30 		Nikolaos Fountoulakis (Birmingham) Combinatorial Theory Seminar Add to calendar L3
Random graphs on spaces of negative curvature
Random geometric graphs have been well studied over the last 50 years or so. These are graphs that are formed between points randomly allocated on a Euclidean space and any two of them are joined if they are close enough. However, all this theory has been developed when the underlying space is equipped with the Euclidean metric. But, what if the underlying space is curved? The aim of this talk is to initiate the study of such random graphs and lead to the development of their theory. Our focus will be on the case where the underlying space is a hyperbolic space. We will discuss some typical structural features of these random graphs as well as some applications, related to their potential as a model for networks that emerge in social life or in biological sciences.

For any corrections/updates to these listings, please contact seminars [-at-] maths [dot] ox [dot] ac [dot] uk.

Syndicate content