Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

Tue, 22/01/2008
13:30 		Paul Dorbec (Oxford) Combinatorial Theory Seminar Add to calendar L3
Packings and coverings in graphs
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, 29/01/2008
13:30 		Graham Farr (Monash University) Combinatorial Theory Seminar Add to calendar L3
The Maximum Induced Planar Subgraph problem
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).
Mon, 04/02/2008
13:30 		David Conlon (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Ramsey numbers of sparse graphs
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, 05/02/2008
13:30 		Magnus Bordewich (Durham University) Combinatorial Theory Seminar Add to calendar L3
Consistency of a Topological Search method in Phylogenetic Inference
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.
Tue, 12/02/2008
13:30 		Angelika Steger (ETH Zurich) Combinatorial Theory Seminar Add to calendar L3
On properties of random dissections of a convex polygon
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.
Tue, 19/02/2008
13:30 		David Wagner (Waterloo University) Combinatorial Theory Seminar Add to calendar L3
Negative correlation inequalities for random cluster models
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.
Tue, 04/03/2008
13:30 		David Conlon (Cambridge) Combinatorial Theory Seminar Add to calendar L3
"Ramsey numbers of sparse graphs"
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.

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

Syndicate content