Past Combinatorial Theory Seminar

HTML clipboard /*-->*/ /*-->*/ We introduce a "Polya choice" urn model combining elements of the well known "power of two choices" model and the "rich get richer" model. From a set of $k$ urns, randomly choose $c$ distinct urns with probability proportional to the product of a power $\gamma>0$ of their occupancies, and increment one with the smallest occupancy. The model has an interesting phase transition. If $\gamma \leq 1$, the urn occupancies are asymptotically equal with probability 1. For $\gamma>1$, this still occurs with positive probability, but there is also positive probability that some urns get only finitely many balls while others get infinitely many.

HTML clipboard /*-->*/ /*-->*/

Fix a positive integer $k$, and consider the class of all graphs which do not have $k+1$  vertex-disjoint cycles.  A classical result of Erdos and P\'{o}sa says that each such graph $G$ contains a blocker of size at most $f(k)$.  Here a {\em blocker} is a set $B$ of vertices such that $G-B$ has no cycles.

 

We give a minor extension of this result, and deduce that almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of size $k$.  This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $R_n$ taken uniformly at random from the class: we see for example that the probability that $R_n$ is connected tends to a specified limit as $n \to \infty$.

 

There are corresponding results when we consider unlabelled graphs with few disjoint cycles. We consider also variants of the problem involving for example disjoint long cycles.

 

This is joint work with Valentas Kurauskas and Mihyun Kang.

HTML clipboard /*-->*/ /*-->*/

Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph $G=(V,E)$ is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.

 

We show the existence of an oblivious routing scheme with competitive ratio $O(\log n)$ and a lower bound of $\Omega(\log n/\logl\og n)$ for this model when the aggregation function agg is an $L_p$-norm.

 

Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics and the work on minimum congestion oblivious. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the $L_p$-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the $L_1$-norm while the result on congestion minmizing oblivious routing solves it for $L_\infty$. We give a single proof that shows the existence of a good tree-based oblivious routing for any $L_p$-norm.

One of the main aims in the theory of percolation is to find the `critical probability' above which long range connections emerge from random local connections with a given pattern and certain individual probabilities. The quintessential example is Kesten's result from 1980 that if the edges of the square lattice are selected independently with probability $p$, then long range connections appear if and only if $p>1/2$.  The starting point is a certain self-duality property, observed already in the early 60s; the difficulty is not in this observation, but in proving that self-duality does imply criticality in this setting.

Since Kesten's result, more complicated duality properties have been used to determine a variety of other critical probabilities. Recently, Scullard and Ziff have described a very general class of self-dual percolation models; we show that for the entire class (in fact, a larger class), self-duality does imply criticality.

Let $G=(V,E)$ be a graph with weights $\{w_e : e \in E\}$, and assume all weights are distinct. If $G$ is finite, then the well-known Prim's algorithm constructs its minimum spanning tree in the following manner. Starting from a single vertex $v$, add the smallest weight edge connecting $v$ to any other vertex. More generally, at each step add the smallest weight edge joining some vertex that has already been "explored" (connected by an edge) to some unexplored vertex.

If $G$ is infinite, however, Prim's algorithm does not necessarily construct a spanning tree (consider, for example, the case when the underlying graph is the two-dimensional lattice ${\mathbb Z}^2$, all weights on horizontal edges are strictly less than $1/2$ and all weights on vertical edges are strictly greater than $1/2$).

The behavior of Prim's algorithm for *random* edge weights is an interesting and challenging object of study, even
when the underlying graph is extremely simple. This line of research was initiated by McDiarmid, Johnson and Stone (1996), in the case when the underlying graph is the complete graph $K_n$. Recently Angel et. al. (2006) have studied Prim's algorithm on regular trees with uniform random edge weights. We study Prim's algorithm on $K_n$ and on its infinitary analogue Aldous' Poisson-weighted infinite tree. Along the way, we uncover two new descriptions of the Poisson IIC, the critical Poisson Galton-Watson tree conditioned to survive forever.

Joint work with Simon Griffiths and Ross Kang.

Let $F$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. We present a polynomial time algorithm that finds a satisfying assignment of $F$ with high probability for constraint densities $m/n

Let $A$ be a finite set in some ambient group. We say that $A$ is a $K$-approximate group if $A$ is symmetric and if the set $A.A$ (the set of all $xy$, where $x$, $y$ lie in $A$) is covered by $K$ translates of $A$. I will illustrate this notion by example, and will go on to discuss progress on the "rough classification" of approximate groups in various settings: abelian groups, nilpotent groups and matrix groups of fixed dimension. Joint work with E. Breuillard.

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

For graphs $L_1,\dots,L_k$, the Ramsey number $R(L_1,\ldots,L_k)$ is the minimum integer $N$ such that for any edge-colouring of the complete graph $K_N$ by $k$ colours there exists a colour $i$ for which the corresponding colour class contains $L_i$ as a subgraph.

In this talk, we shall discuss recent developments in the case when the graphs $L_1,\dots,L_k$ are all cycles and $k\ge2$.

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.

We consider Markovian models on graphs with local dynamics. We show that, under suitable conditions, such Markov chains exhibit both rapid convergence to equilibrium and strong concentration of measure in the stationary distribution. We illustrate our results with applications to some known chains from computer science and statistical mechanics.

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).

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)

Regions of a link diagram can be colored in black and white in a checkerboard manner. Putting a vertex in each black region and connecting two vertices by an edge if the corresponding regions share a crossing yields a planar graph. In 1987 Thistlethwaite proved that the Jones polynomial of the link can be obtained by a specialization of the Tutte polynomial of this planar graph. The goal of my talk will be an explanation of a generalization of Thistlethwaite's theorem to virtual links. In this case graphs will be embedded into a (higher genus, possibly non-oriented) surface. For such graphs we used a generalization of the Tutte polynomial called the Bollobas-Riordan polynomial. For graphs on
surfaces the natural duality can be generalized to a duality with respect to a subset of edges. The generalized dual graph might be embedded into a different surface. I will explain a relation between the Bollobas-Riordan polynomials of dual graphs. This relation unifies various Thistlethwaite type theorems.

Parity games are simple two-player, infinite-move games particularly useful in Computer Science for modelling non-terminating reactive systems and recursive processes.  A longstanding open problem related to these games is whether the winner of a parity game can be decided in polynomial time.  One of the most promising algorithms to date is a strategy improvement algorithm of Voege and Jurdzinski, however no good bounds are known on its running time.

In this talk I will discuss how the problem of finding a winner in a parity game can be reduced to the problem of locally finding a global sink on an acyclic unique sink oriented hypercube.  As a consequence, we can improve (albeit only marginally) the bounds of the strategy improvement algorithm.

This talk is similar to one I presented at the InfoSys seminar in the Computing Laboratory in October.

In the first part of the talk we will introduce the notion of property testing and briefly discuss some results in testing graph properties in the framework of property testing.

Then, we will discuss a recent result about testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion:   \newline an $a$-expander is a graph $G = (V,E)$ in which every subset $U$ of $V$ of at most $|V|/2$ vertices has a neighborhood of size at least $a|U|$. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately $O(n^{1/2})$.

We design a property testing algorithm that accepts every $a$-expander with probability at least 2/3 and rejects every graph that is $\epsilon$-far from an $a^*$-expander with probability at least 2/3, where $a^* = O(a^2/(d^2 log(n/\epsilon)))$, $d$ is the maximum degree of the graphs, and a graph is called $\epsilon$-far from an $a^*$-expander if one has to modify (add or delete) at least $\epsilon d n$ of its edges to obtain an $a^*$-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is $O(d^2 n^{1/2} log(n/\epsilon)/(a^2 \epsilon^3))$.

This is a joint work with Christian Sohler.

The homological Hall lemma is a topological tool that has recently been used to derive Hall type theorems for systems of disjoint representatives in hypergraphs.

After outlining the general method, we.ll describe one such theorem in some detail. The main ingredients in the proof are:

1) A relation between the spectral gap of a graph and the topological connectivity of its flag complex.

2) A new graph domination parameter defined via certain vector representations of the graph.

Joint work with R. Aharoni and E. Berger

How can one guarantee the presence of an oriented four-cycle in an oriented graph G? We shall see, that one way in which this can be done, is to demand that G contains no large `biased. subgraphs; where a `biased. subgraph simply means a subgraph whose orientation exhibits a strong bias in one direction.

Furthermore, we discuss the concept of biased subgraphs from another standpoint, asking: how can an oriented graph best avoid containing large biased subgraphs? Do random oriented graphs give the best examples? The talk is partially based on joint work with Omid Amini and Florian Huc.

Linear operators preserving non-vanishing properties are an important

tool in e.g. combinatorics, the Lee-Yang program on phase transitions, complex analysis, matrix theory. We characterize all linear operators on spaces of multivariate polynomials preserving the property of being non-vanishing when the variables are in prescribed open circular domains, which solves the higher dimensional counterpart of a long-standing classification problem going back to P\'olya-Schur. This also leads to a self-contained theory of multivariate stable polynomials and a natural framework for dealing with Lee-Yang and Heilmann-Lieb type problems in a uniform manner. The talk is based on joint work with Petter Brändén.

For any simple graph G and any positive integer lambda, let

P(G,lambda) denote the number of mappings f from V(G) to

{1,2,..,lambda} such that f(u) not= f(v) for every two adjacent

vertices u and v in G. It can be shown that

P(G,lambda) = \sum_{A \subseteq E} (-1)^{|A|} lambda^{c(A)}

where E is the edge set of G and c(A) is the number of components

of the spanning subgraph of G with edge set A. Hence P(G,lambda)

is really a polynomial of lambda. Many results on the chromatic

polynomial of a graph have been discovered since it was introduced

by Birkhoff in 1912. However, there are still many unsolved

problems and this talk will introduce the progress of some

problems and also some new problems proposed recently.

We call a family of permutations A in Sn 'intersecting' if any two permutations in A agree in at least one position. Deza and Frankl observed that an intersecting family of permutations has size at most (n-1)!; Cameron and Ku proved that equality is attained only by families of the form {σ in Sn: σ(i)=j} for i, j in [n].

We will sketch a proof of the following `stability' result: an intersecting family of permutations which has size at least (1-1/e + o(1))(n-1)! must be contained in {σ in Sn: σ(i)=j} for some i,j in [n]. This proves a conjecture of Cameron and Ku.

In order to tackle this we first use some representation theory and an eigenvalue argument to prove a conjecture of Leader concerning cross-intersecting families of permutations: if n >= 4 and A,B is a pair of cross-intersecting families in Sn, then |A||B|

Let G be the union of a red graph R and a blue graph B where every edge of G is in R or B (or both R and B). We call such a graph 2-painted. Given 2-painted graphs G and H, we say that G contains a copy of H if we can find a subgraph of G which is isomorphic to H. Let 0

Joint work with Nicolas Broutin.

The phase transition is a phenomenon that appears in natural sciences in various contexts. In the random graph theory, the phase transition refers to a dramatic change in the number of vertices in the largest components by addition of a few edges around a critical value, which was first discussed on the standard random graphs in the seminal paper by Erdos and Renyi. Since then, the phase transition has been a central theme of the random graph theory. In this talk we discuss the phase transition in random graphs with a given degree sequence and random graph processes with degree constraints.

A tree-rooted map is a planar map together with a

distinguished spanning tree. In the sixties, Mullin proved that the

number of tree-rooted maps with $n$ edges is the product $C_n C_{n+1}$

of two consecutive Catalan numbers. We will present a bijection

between tree-rooted maps (of size $n$) and pairs made of two trees (of

size $n$ and $n+1$ respectively) explaining this result.

Then, we will show that our bijection generalizes a correspondence by

Schaeffer between quandrangulations and so-called \emph{well labelled

trees}. We will also explain how this bijection can be used in order

to count bijectively several classes of planar maps

Let d be a fixed natural number. There is a theorem, due to Chvátal, Rodl,

Szemerédi and Trotter (CRST), saying that the Ramsey number of any graph G

with maximum degree d and n vertices is at most c(d)n, that is it grows

linearly with the size of n. The original proof of this theorem uses the

regularity lemma and the resulting dependence of c on d is of tower-type.

This bound has been improved over the years to the stage where we are now

grappling with proving the correct dependency, believed to be an

exponential in d. Our first main result is a proof that this is indeed the

case if we assume additionally that G is bipartite, that is, for a

bipartite graph G with n vertices and maximum degree d, we have r(G)

The partition function of the random cluster model on a graph $G$ is also known as its Potts model partition function. (Only the points at which it is evaluated differ in the two models.) This is a multivariate generalization of the Tutte polynomial of $G$, and encodes a wealth of enumerative information about spanning trees and forests, connected spanning subgraphs, electrical properties, and so on.

An elementary property of electrical networks translates into the statement that any two distinct edges are negatively correlated if one picks a spanning tree uniformly at random. Grimmett and Winkler have conjectured the analogous correlation inequalities for random forests or random connected spanning subgraphs. I'll survey some recent related work, partial results, and more specific conjectures, without going into all the gory details.

In the past decades the $G_{n,p}$ model of random graphs has led to numerous beautiful and deep theorems. A key feature that is used in basically all proofs is that edges in $G_{n,p}$ appear independently.

The independence of the edges allows, for example, to obtain extremely tight bounds on the number of edges of $G_{n,p}$ and its degree sequence by straightforward applications of Chernoff bounds. This situation changes dramatically if one considers graph classes with structural side constraints. In this talk we show how recent progress in the construction of so-called Boltzmann samplers by Duchon, Flajolet, Louchard, and Schaeffer can be used to reduce the study of degree sequences and subgraph counts to properties of sequences of independent and identically distributed random variables -- to which we can then again apply Chernoff bounds to obtain extremely tight results. As proof of concept we study properties of random graphs that are drawn uniformly at random from the class consisting of the dissections of large convex polygons. We obtain very sharp concentration results for the number of vertices of any given degree, and for the number of induced copies of a given fixed graph.

A number of phylogenetic algorithms proceed by searching the space of all possible phylogenetic (leaf labeled) trees on a given set of taxa, using topological rearrangements and some optimality criterion. Recently, such an approach, called BSPR, has been applied to the balanced minimum evolution principle. Several computer studies have demonstrated the accuracy of BSPR in reconstructing the correct tree. It has been conjectured that BSPR is consistent, that is, when applied to an input distance that is a tree-metric, it will always converge to the (unique) tree corresponding to that metric. Here we prove that this is the case. Moreover, we show that even if the input distance matrix contains small errors relative to the tree-metric, then the BSPR algorithm will still return the corresponding tree.

Let d be a fixed natural number. There is a theorem, due to Chvátal, Rodl,

Szemerédi and Trotter (CRST), saying that the Ramsey number of any graph G

with maximum degree d and n vertices is at most c(d)n, that is it grows

linearly with the size of n. The original proof of this theorem uses the

regularity lemma and the resulting dependence of c on d is of tower-type.

This bound has been improved over the years to the stage where we are now

grappling with proving the correct dependency, believed to be an

exponential in d. Our first main result is a proof that this is indeed the

case if we assume additionally that G is bipartite, that is, for a

bipartite graph G with n vertices and maximum degree d, we have r(G)

Abstract: The Maximum Induced Planar Subgraph problem asks

for the largest set of vertices in a given input graph G

that induces a planar subgraph of G. Equivalently, we may

ask for the smallest set of vertices in G whose removal

leaves behind a planar subgraph. This problem has been

linked by Edwards and Farr to the problem of _fragmentability_

of graphs, where we seek the smallest proportion of vertices

in a graph whose removal breaks the graph into small (bounded

size) pieces. This talk describes some algorithms

developed for this problem, together with theoretical and

experimental results on their performance. The material

presented is joint work either with Keith Edwards (Dundee)

or Kerri Morgan (Monash).

Packings and coverings in graphs are related to two main problems of

graph theory, respectively error correcting codes and domination.

Given a set of words, an error correcting code is a subset such that

any two words in the subset are rather far apart, and can be

identified even if some errors occured during transmission. Error

correcting codes have been well studied already, and a famous example

of perfect error correcting codes are Hamming codes.

Domination is also a very old problem, initiated by some Chess problem

in the 1860's, yet Berge proposed the corresponding problem on graphs

only in the 1960's. In a graph, a subset of vertices dominates all the

graph if every vertex of the graph is neighbour of a vertex of the

subset. The domination number of a graph is the minimum number of

vertices in a dominating set. Many variants of domination have been

proposed since, leading to a very large literature.

During this talk, we will see how these two problems are related and

get into few results on these topics.

Phylogenetics is the reconstruction and analysis of 'evolutionary'

trees and graphs in biology (and related areas of classification, such as linguistics). Discrete mathematics plays an important role in the underlying theory. We will describe some of the ways in which concepts from combinatorics (e.g. poset theory, greedoids, cyclic permutations, Menger's theorem, closure operators, chordal graphs) play a central role. As well as providing an overview, we also describe some recent and new results, and outline some open problems.

We give different criteria for transience of branching Markov chains. These conditions enable us to give a classification of branching random walks in random environment (BRWRE) on Cayley graphs in recurrence and transience. This classification is stated explicitly for BRWRE on $\Z^d.$ Furthermore, we emphasize the interplay between branching Markov chains, the spectral radius, and some generating functions.

Hypergraph Transversals have been studied in Mathematics for a long time (e.g. by Berge) . Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science, especially in database Theory, Logic, and AI. We give a survey of various applications and review some recent results on the complexity of computing all minimal transversals of a given hypergraph.

Glauber dynamics on $\mathbb{Z}^d$ is a dynamic representation of the zero-temperature Ising model, in which the spin (either $+$ or $-$) of each vertex updates, at random times, to the state of the majority of its neighbours. It has long been conjectured that the critical probability $p_c(\mathbb{Z}^d)$ for fixation (every vertex eventually in the same state) is $1/2$, but it was only recently proved (by Fontes, Schonmann and Sidoravicius) that $p_c(\mathbb{Z}^d)

The transportation problem (TP) is a classic problem in operations research. The problem was posed for the first time by Hitchcock in 1941 [Hitchcock, 1941] and independently by Koopmans in 1947 [Koopmans, 1948], and appears in any standard introductory course on operations research.

The mxn TP has m supply points and n demand points. Each supply Point i holds a quantity r_i, and each demand point j wants a quantity c_j, with the sum of femands equal to the sum of supplies. A solution to the problem can be written as a mxn matrix X with entries decision x_{ij} having value equal to the amount transported from supply point i to demand point j. The objective is to minimize total transportation costs when unit transporation costs between each supply and each demand point are given.

The set of feasible solutions of TP, is called the transportation polytope.

The 1-skeleton (edge graph) of this polytope is defined as the graph with vertices the vertices of the polytope and edges its 1-dimensional faces.

In 1957 W.M. Hirsch stated his famous conjecture cf. [Dantzig, 1963]) saying that any d-dimensional polytope with n facets has diameter at most n-d. So far the best bound for any polytope is O(n^{\log d+1}) [Kalai and Kleitman, 1992]. Any strongly polynomial bound is still lacking. Such bounds have been proved for some special classes of polytopes (for examples, see [Schrijver, 1995]). Among those are some special classes of transportation polytopes [Balinski, 1974],[Bolker, 1972] and the polytope of the dual of TP [Balinski, 1974].

The first strongly polynomial bound on the diameter of the transportation polytope was given by Dyer and Frieze [DyerFrieze, 1994]. Actually, they prove a bound on the diameter of any polytope {x|Ax=b} where A is a totally unimodular matrix. The proof is complicated and indirect, using the probabilistic method. Moreover, the bound is huge O(m^{16}n^3ln(mn))3) assuming m less than or equal to n.

We will give a simple proof that the diameter of the transportation polytope is less than 8(m+n-2). The proof is constructive: it gives an algorithm that describes how to go from any vertex to any other vertex on the transportation polytope in less than 8(m+n-2) steps along the edges.

According to the Hirsch Conjecture the bound on the TP polytope should be

m+n-1. Thus we are within a multiplicative factor 8 of the Hirsch bound.

Recently C. Hurkens refined our analysis and diminished the bound by a factor 2, arriving at 4(m+n-2). I will indicate the way he achieved this as well.

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.

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.

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

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.