Past Combinatorial Theory Seminar

6 November 2007
15:30
Tobias Muller
Abstract
A graph property is a first order property if it can be written as a logic sentence with variables ranging over the vertices of the graph. A sequence of random graphs (G_n)_n satisfies the zero-one law if the probability that G_n satisfies P tends to either zero or one for every first order property P. This is for instance the case for G(n,p) if p is fixed. I will survey some of the most important results on the G(n,p)-model and then proceed to discuss some work in progress on other graph models.
  • Combinatorial Theory Seminar
6 November 2007
13:30
Oliver Riordan
Abstract
One of the main tools in studying sparse random graphs with independence between different edges is local comparison with branching processes. Recently, this method has been used to determine the asymptotic behaviour of the diameter (largest graph distance between two points that are in the same component) of various sparse random graph models, giving results for $G(n,c/n)$ as special cases. Nick Wormald and I have applied this method to $G(n,c/n)$ itself, obtaining a much stronger result, with a best-possible error term. We also obtain results as $c$ varies with $n$, including results almost all the way down to the phase transition.
  • Combinatorial Theory Seminar
30 October 2007
15:30
Pierre Charbit
Abstract
The Rado Graph R is a graph on a countably infinite number of vertices that can be characterized by the following property: for every pair of finite, disjoint subsets of vertices X and Y, there exists a vertex that is adjacent to every vertex in X and none in Y. It is often called the Random Graph for the following reason: for any 0<p<1 if one considers a graph on a countably infinite number of vertices such that an edge between two vertices exists with probability p, then almost surely this graph is isomorphic to R. Guided by this classical example and motivated by models of the web graph, A. Bonato and J.Jenssen introduced a construction that leads to infinite locally random graphs, which are graphs such that the neighborhood of every vertex is isomorphic to R. In this talk we will discuss several properties of this construction. (Joint work with Alexander D. Scott)
  • Combinatorial Theory Seminar
30 October 2007
13:30
Matthias Reitzner
Abstract
Let $K \subset {\mathbb R}^d$ be a convex set. Choose $n$ random points in $K$, and denote by $P_n$ their convex hull. We call $P_n$ a random polytope. Investigations concerning the expected value of functionals of $P_n$, like volume, surface area, and number of vertices, started in 1864 with a problem raised by Sylvester and now are a classical part of stochastic and convex geometry. The last years have seen several new developments about distributional aspects of functionals of random polytopes. In this talk we concentrate on these recent results such as central limit theorems and tail inequalities, as the number of random points tends to infinity.
  • Combinatorial Theory Seminar
23 October 2007
16:30
Laszlo Szekely
Abstract
The Lovasz Local Lemma is known to have an extension for cases where the dependency graph requirement is relaxed to negative dependency graph (Erdos-Spencer 1991). The difficulty is to find relevant negative dependency graphs that are not dependency graphs. We provide two generic constructions for negative dependency graphs, in the space of random matchings of complete and complete bipartite graphs. As application, we prove existence results for hypergraph packing and Turan type extremal problems. We strengthen the classic probabilistic proof of Erdos for the existence of graphs with large girth and chromatic number by prescribing the degree sequence, which has to satisfy some mild conditions. A more surprising application is that tight asymptotic lower bounds can be obtained for asymptotic enumeration problems using the Lovasz Local Lemma. This is joint work with Lincoln Lu.
  • Combinatorial Theory Seminar
16 October 2007
16:30
Nicolas Broutin
Abstract
Digital trees is a general structure to manipulate sequences of characters. We propose a novel approach to the structure of digital trees. It shades some new light on the profile of digital trees, and provides a unified explanation of the relationships between different kinds of digital trees. The idea relies on the distinction of nodes based on their type, i.e., the set of their children. Only two types happen to matter when studying the number of nodes lying at a specified level: the nodes with a full set of children which constitutes the core, and the nodes with a single child producing spaghetti-like trees hanging down the core. We will explain the distinction and its applications on a number of examples related to data structures such as the TST of Bentley and Sedgewick. This is joint work with Luc Devroye.
  • Combinatorial Theory Seminar
16 October 2007
14:30
Abstract
A central task in conservation biology is measuring, predicting, and preserving biological diversity as species face extinction. Dating back to 1992, phylogenetic diversity is a prominent notion for measuring the biodiversity of a collection of species. This talk gives a flavour of some the combinatorial and algorithmic problems and recent solutions associated with computing this measure. This is joint work with Magnus Bordewich (Durham University, UK) and Andreas Spillner (University of East Anglia, UK).
  • Combinatorial Theory Seminar

Pages