Combinatorial Theory Seminar (past)
|
Tue, 06/05/2008 14:30 |
Mike Paterson (Warwick) |
Combinatorial Theory Seminar  |
L3 |
| How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be of order log n. Recently, we (Paterson and Zwick) constructed n-block stacks with overhangs of order n^{1/3}, exponentially better than previously thought possible. The latest news is that we (Paterson, Peres, Thorup, Winkler and Zwick) can show that order n^{1/3} is best possible, resolving the long-standing overhang problem up to a constant factor. I shall review the construction and describe the upper bound proof, which illustrates how methods founded in algorithmic complexity can be applied to a discrete optimization problem that has puzzled some mathematicians and physicists for more than 150 years. | |||
|
Tue, 29/04/2008 14:30 |
Mihyun Kang (Humboldt University) |
Combinatorial Theory Seminar |
L3 |
| 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. | |||
|
Tue, 15/04/2008 14:30 |
Olivier Bernardi |
Combinatorial Theory Seminar |
L3 |
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  edges is the product 
of two consecutive Catalan numbers. We will present a bijection
between tree-rooted maps (of size ) and pairs made of two trees (of
size and  respectively) explaining this result.
Then, we will show that our bijection generalizes a correspondence by
Schaeffer between quandrangulations and so-called well labelled
trees. We will also explain how this bijection can be used in order
to count bijectively several classes of planar maps |
|||
|
Tue, 04/03/2008 13:30 |
David Conlon (Cambridge) |
Combinatorial Theory Seminar |
L3 |
| 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) <= 2^{C d) n, for some constant C. We also discuss how this result may be extended to hypergraphs. This allows us to give a clean and short proof of the hypergraph analogue of the CRST theorem. This latter work was done jointly with Jacob Fox and Benny Sudakov. | |||
|
Tue, 19/02/2008 13:30 |
David Wagner (Waterloo University) |
Combinatorial Theory Seminar |
L3 |
The partition function of the random cluster model on a graph  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 , 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. |
|||
|
Tue, 12/02/2008 13:30 |
Angelika Steger (ETH Zurich) |
Combinatorial Theory Seminar |
L3 |
In the past decades the  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 appear independently.
The independence of the edges allows, for example, to obtain extremely tight bounds on the number of edges of 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. |
|||
|
Tue, 05/02/2008 13:30 |
Magnus Bordewich (Durham University) |
Combinatorial Theory Seminar |
L3 |
| 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. | |||
|
Mon, 04/02/2008 13:30 |
David Conlon (Cambridge) |
Combinatorial Theory Seminar |
L3 |
| 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) <= 2^{C d) n, for some constant C. We also discuss how this result may be extended to hypergraphs. This allows us to give a clean and short proof of the hypergraph analogue of the CRST theorem. This latter work was done jointly with Jacob Fox and Benny Sudakov. | |||
|
Tue, 29/01/2008 13:30 |
Graham Farr (Monash University) |
Combinatorial Theory Seminar |
L3 |
| 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). | |||
|
Tue, 22/01/2008 13:30 |
Paul Dorbec (Oxford) |
Combinatorial Theory Seminar |
L3 |
| 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. | |||
|
Tue, 27/11/2007 13:30 |
Mike Steel (University of Canterbury, NZ) |
Combinatorial Theory Seminar |
L3 |
| 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. | |||
|
Tue, 20/11/2007 15:30 |
Sebastian Muller (Graz) |
Combinatorial Theory Seminar |
SR1 |
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  Furthermore, we emphasize the interplay between branching Markov chains, the spectral radius, and some generating functions. |
|||
|
Tue, 20/11/2007 13:30 |
Georg Gottlob (Oxford) |
Combinatorial Theory Seminar |
L3 |
| 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. | |||
|
Tue, 13/11/2007 15:30 |
Rob Morris (Cambridge) |
Combinatorial Theory Seminar |
SR1 |
Glauber dynamics on  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  for fixation (every vertex eventually in the same state) is  , but it was only recently proved (by Fontes, Schonmann and Sidoravicius) that  .
Bootstrap percolation is a simpler, monotone version of Glauber dynamics, in which sites can only change state in one direction (from to , say). In this talk I shall discuss some recent advances in the study of bootstrap percolation on ![$ [n]^d $](/files/tex/8f89ab15232ca9fd6665537df805c947a6c731df.png) , and show how these can be applied to obtain improved bounds on the critical probability for Glauber dynamics in high dimensions.
This is joint work with József Balogh and Béla Bollobás. |
|||
|
Tue, 13/11/2007 13:30 |
Leen Stougie (Einhoven) |
Combinatorial Theory Seminar |
L3 |
| 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. | |||
|
Tue, 06/11/2007 15:30 |
Tobias Muller (Eindhoven) |
Combinatorial Theory Seminar |
SR1 |
| 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. | |||
|
Tue, 06/11/2007 13:30 |
Oliver Riordan (Oxford) |
Combinatorial Theory Seminar |
L3 |
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  as special cases. Nick Wormald and I have applied this method to itself, obtaining a much stronger result, with a best-possible error term. We also obtain results as  varies with , including results almost all the way down to the phase transition. |
|||
|
Tue, 30/10/2007 15:30 |
Pierre Charbit (Paris) |
Combinatorial Theory Seminar |
L3 |
| 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 | |||
|
Tue, 30/10/2007 13:30 |
Matthias Reitzner (Vienna) |
Combinatorial Theory Seminar |
L3 |
| 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. | |||
|
Tue, 23/10/2007 16:30 |
Laszlo Szekely (USC) |
Combinatorial Theory Seminar |
SR1 |
| 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. | |||
