# Past Combinatorial Theory Seminar

19 February 2008
13:30
David Wagner
Abstract
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.
• Combinatorial Theory Seminar
12 February 2008
13:30
Angelika Steger
Abstract
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.
• Combinatorial Theory Seminar
5 February 2008
13:30
Magnus Bordewich
Abstract
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.
• Combinatorial Theory Seminar
4 February 2008
13:30
David Conlon
Abstract
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.
• Combinatorial Theory Seminar
29 January 2008
13:30
Graham Farr
Abstract
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).
• Combinatorial Theory Seminar
22 January 2008
13:30
Paul Dorbec
Abstract
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.
• Combinatorial Theory Seminar
27 November 2007
13:30
Abstract
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.
• Combinatorial Theory Seminar
20 November 2007
15:30
Sebastian Muller
Abstract
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.
• Combinatorial Theory Seminar
20 November 2007
13:30
Georg Gottlob
Abstract
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.
• Combinatorial Theory Seminar
13 November 2007
15:30
Rob Morris
Abstract
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) < 1$. 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$, 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\'ozsef Balogh and B\'ela Bollob\'as.
• Combinatorial Theory Seminar