Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

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, 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, 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, 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, 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, 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, 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, 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.

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

Syndicate content