# Past 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
13 November 2007
13:30
Leen Stougie
Abstract
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.
• 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