Past Seminars › Seminar Series

Combinatorial Theory Seminar (past)

Tue, 10/03/2009
14:30 		Peter Keevash (QMUL) Combinatorial Theory Seminar Add to calendar L3
Cycles in directed graphs
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.
Tue, 03/03/2009
14:30 		Malwina Luczak (LSE) Combinatorial Theory Seminar Add to calendar L3
Concentration and mixing for Markov chains
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.
Tue, 24/02/2009
14:30 		Peter Cameron (QMUL) Combinatorial Theory Seminar Add to calendar L3
Synchronization and homomorphisms
A graph homomorphism is a mapping of vertices which takes edges to edges. The endomorphisms of a graph (homomorphisms to itself) form a submonoid of he full transformation monoid on the vertex set. In the other direction, there is a construction of a graph from a transformation monoid, which will be described in the talk. Composing these maps gives closure operators on graphs and on monoids which have some interesting properties. There are also connections with finite automata and permutation groups.
Tue, 17/02/2009
14:30 		Dudley Stark (QMUL) Combinatorial Theory Seminar Add to calendar L3
The edge correlation of random forests
The conjecture was made by Pemantle that a forest chosen uniformly at random from all forests in any finite graph G has the edge-negative association property. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices and derive related results for random trees.
Tue, 10/02/2009
14:30 		Christina Goldschmidt (Oxford) Combinatorial Theory Seminar Add to calendar L3
The scaling limit of critical random graphs
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).
Tue, 03/02/2009
14:30 		Ross Kang (McGill) Combinatorial Theory Seminar Add to calendar L3
The t-dependence and t-improper chromatic numbers of random graphs
We consider a natural generalisation of the independence and chromatic numbers and study their behaviour in Erdos-Renyi random graphs. The t-dependence number of a graph G is the size of the largest subset of the vertices of G whose induced subgraph has maximum degree at most t. The t-improper chromatic number of G is the smallest number of parts needed in a partition of the vertex set of G such that each part induces a subgraph of maximum degree at most t. Clearly, when t = 0, these parameters are, respectively, the independence and chromatic numbers of G. For dense random graphs, we determine the asymptotic ehaviour of these parameters over the range of choices for the growth of t as a function of the number of vertices. This is joint work with Nikolaos Fountoulakis and Colin McDiarmid.
Tue, 27/01/2009
14:30 		Graham Brightwell (LSE) Combinatorial Theory Seminar Add to calendar L3
Random partial orders and random linear extensions
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)
Tue, 20/01/2009
14:30 		John Talbot (UCL) Combinatorial Theory Seminar Add to calendar L3
Vertex Turan problems in the hypercube
Let $ Q_n=\{0,1\}^n $ be the $ n $-dimensional hypercube. For $ 1\leq d \leq n $ and $ F\subseteq Q_d $ we consider the question of how large $ S\subseteq Q _n $ can be if every embedding $ i:Q_d\to Q_n $ satisfies $ i(F)\not\subseteq S $. We determine the asymptotic behaviour of the largest $ F $-free subsets of $ Q_n $ for a variety of $ F $, in particular we generalise the sole non-trivial prior result in this area: $ F=Q_2 $ due to E.A. Kostochka. Many natural questions remain open. This is joint work with Robert Johnson.
Tue, 09/12/2008
14:30 		Sergei Chmutov (Ohio State) Combinatorial Theory Seminar Add to calendar L3
Graphs on surfaces and virtual knots
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.
Tue, 02/12/2008
14:30 		Paul Hunter (Oxford) Combinatorial Theory Seminar Add to calendar L3
Strategy Improvement for Parity Games: A combinatorial perspective
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.
Tue, 25/11/2008
14:30 		Artur Czumaj (Warwick) Combinatorial Theory Seminar Add to calendar L3
Testing expansion in bounded degree graphs really fast
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:  
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.
Tue, 11/11/2008
14:30 		Colin McDiarmid (Oxford) Combinatorial Theory Seminar Add to calendar L3
Random graphs from a minor-closed class
Tue, 28/10/2008
14:30 		Andy Twigg (Oxford) Combinatorial Theory Seminar Add to calendar L3
Distance labeling on graphs
Given a graph G, we are asked to preprocess G and compute labels L(u) for vertices such that given L(x) and L(y) we can efficiently answer d_G(x,y). I will describe some results in this area and some open problems.
Tue, 21/10/2008
14:30 		Roy Meshulam (Technion) Combinatorial Theory Seminar Add to calendar L3
Domination numbers, homology and hypergraph matching
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
Tue, 14/10/2008
16:00 		Simon Griffiths (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Subgraphs of Oriented Graphs
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.
Tue, 10/06/2008
14:30 		Julius Borcea (Stockholm) Combinatorial Theory Seminar Add to calendar L3
The Lee-Yang program and Pólya-Schur theory
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ólya-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.
Tue, 03/06/2008
14:30 		F.M. Dong (Singapore) Combinatorial Theory Seminar Add to calendar L3
Unsolved problems related to chromatic polynomials
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.
Tue, 27/05/2008
14:30 		David Ellis (Cambridge) Combinatorial Theory Seminar Add to calendar L3
“Cross-intersecting families of permutations and the Cameron-Ku conjecture"
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| <= [(n-1)!]2, with equality iff A=B= {σ in Sn: σ(i)=j} for some i,j in [n]. A by-product of this is a relatively clean proof of equality in the Deza-Frankl Theorem.
Tue, 20/05/2008
14:30 		Ed Marchant (Cambridge) Combinatorial Theory Seminar Add to calendar L3
"Turan/Erdos-Stone type problems involving coloured graphs"
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
Tue, 13/05/2008
14:30 		Louigi Addario-Berry (Oxford) Combinatorial Theory Seminar Add to calendar L3
Killed Branching Random Walks
Joint work with Nicolas Broutin. The problem is related to searching in trees.  Suppose we are given a complete binary tree (a rooted tree in which the root has degree 2 and every other vertex has degree 3) with independent, identically distributed random edge weights (say copies of some random variable X, which need not be non-negative). The depth d(v) of a vertex v is the number of edges on the path from v to the root. We give each vertex v the label S_v which is the sum of the edge weights on the path from v to the root. For positive integers n, we let M_n be the maximum label of any vertex at depth n, and let M^* = max {M_n: n =0,1,...}. It is of course possible that M^* is infinity. Under suitable moment assumptions on X, it is known that there is a constant A such that M_n/n –> A almost surely and in expectation. We call the cases A>0, A=0, and A< 0 supercritical, critical, and subcritical, respectively. When A <= 0 it makes sense to try to find the vertex of maximum weight M* in the whole tree.  One possible strategy is to only explore the subtree T_0 containing the root consisting only of vertices of non-negative weight.  With probability bounded away from zero this strategy finds the vertex of maximum weight.  We derive precise information about the expected running time for this strategy. Equivalently, we derive precise information about the random variable |T_0|. In the process, we also derive rather precise information about M*. This answers a question of David Aldous.

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

Syndicate content