Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

Tue, 13/10/2009
14:30 		Louigi Addario-Berry (McGill) Combinatorial Theory Seminar Add to calendar L3
Prim's algorithm and self-organized criticality, in the complete graph
Let $ G=(V,E) $ be a graph with weights $ \{w_e : e \in E\} $, and assume all weights are distinct. If $ G $ is finite, then the well-known Prim's algorithm constructs its minimum spanning tree in the following manner. Starting from a single vertex $ v $, add the smallest weight edge connecting $ v $ to any other vertex. More generally, at each step add the smallest weight edge joining some vertex that has already been "explored" (connected by an edge) to some unexplored vertex. If $ G $ is infinite, however, Prim's algorithm does not necessarily construct a spanning tree (consider, for example, the case when the underlying graph is the two-dimensional lattice $ {\mathbb Z}^2 $, all weights on horizontal edges are strictly less than $ 1/2 $ and all weights on vertical edges are strictly greater than $ 1/2 $). The behavior of Prim's algorithm for *random* edge weights is an interesting and challenging object of study, even when the underlying graph is extremely simple. This line of research was initiated by McDiarmid, Johnson and Stone (1996), in the case when the underlying graph is the complete graph $ K_n $. Recently Angel et. al. (2006) have studied Prim's algorithm on regular trees with uniform random edge weights. We study Prim's algorithm on $ K_n $ and on its infinitary analogue Aldous' Poisson-weighted infinite tree. Along the way, we uncover two new descriptions of the Poisson IIC, the critical Poisson Galton-Watson tree conditioned to survive forever. Joint work with Simon Griffiths and Ross Kang.
Tue, 27/10/2009
14:30 		Stanislav Volkov (Bristol) Combinatorial Theory Seminar Add to calendar L3
The simple harmonic urn
The simple harmonic urn is a discrete-time stochastic process on $ \mathbb Z^2 $ approximating the phase portrait of the harmonic oscillator using very basic transitional probabilities on the lattice, incidentally related to the Eulerian numbers. This urn which we consider can be viewed as a two-colour generalized Polya urn with negative-positive reinforcements, and in a sense it can be viewed as a “marriage” between the Friedman urn and the OK Corral model, where we restart the process each time it hits the horizontal axes by switching the colours of the balls. We show the transience of the process using various couplings with birth and death processes and renewal processes. It turns out that the simple harmonic urn is just barely transient, as a minor modification of the model makes it recurrent. We also show links between this model and oriented percolation, as well as some other interesting processes. This is joint work with E. Crane, N. Georgiou, R. Waters and A. Wade.
Tue, 03/11/2009
14:30 		Oliver Riordan (Oxford) Combinatorial Theory Seminar Add to calendar L3
A general class of self-dual percolation models
One of the main aims in the theory of percolation is to find the `critical probability' above which long range connections emerge from random local connections with a given pattern and certain individual probabilities. The quintessential example is Kesten's result from 1980 that if the edges of the square lattice are selected independently with probability $ p $, then long range connections appear if and only if $ p>1/2 $.  The starting point is a certain self-duality property, observed already in the early 60s; the difficulty is not in this observation, but in proving that self-duality does imply criticality in this setting. Since Kesten's result, more complicated duality properties have been used to determine a variety of other critical probabilities. Recently, Scullard and Ziff have described a very general class of self-dual percolation models; we show that for the entire class (in fact, a larger class), self-duality does imply criticality.
Tue, 10/11/2009
14:00 		Harald Raecke (Warwick) Combinatorial Theory Seminar Add to calendar L3
Oblivious Routing in the $ L_p $ norm
HTML clipboard Gupta et al. introduced a very general multi-commodity flow problem in which the cost of a given flow solution on a graph $ G=(V,E) $ is calculated by first computing the link loads via a load-function l, that describes the load of a link as a function of the flow traversing the link, and then aggregating the individual link loads into a single number via an aggregation function.   We show the existence of an oblivious routing scheme with competitive ratio $ O(\log n) $ and a lower bound of $ \Omega(\log n/\logl\og n) $ for this model when the aggregation function agg is an $ L_p $-norm.   Our results can also be viewed as a generalization of the work on approximating metrics by a distribution over dominating tree metrics and the work on minimum congestion oblivious. We provide a convex combination of trees such that routing according to the tree distribution approximately minimizes the $ L_p $-norm of the link loads. The embedding techniques of Bartal and Fakcharoenphol et al. [FRT03] can be viewed as solving this problem in the $ L_1 $-norm while the result on congestion minmizing oblivious routing solves it for $ L_\infty $. We give a single proof that shows the existence of a good tree-based oblivious routing for any $ L_p $-norm.
Tue, 10/11/2009
14:50 		Colin McDiarmid (Oxford) Combinatorial Theory Seminar Add to calendar L3
Random graphs with few disjoint cycles
HTML clipboard Fix a positive integer $ k $, and consider the class of all graphs which do not have $ k+1 $  vertex-disjoint cycles.  A classical result of Erdos and Pósa says that each such graph $ G $ contains a blocker of size at most $ f(k) $.  Here a blocker is a set $ B $ of vertices such that $ G-B $ has no cycles.   We give a minor extension of this result, and deduce that almost all such labelled graphs on vertex set $ 1,\ldots,n $ have a blocker of size $ k $.  This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $ R_n $ taken uniformly at random from the class: we see for example that the probability that $ R_n $ is connected tends to a specified limit as $ n \to \infty $.   There are corresponding results when we consider unlabelled graphs with few disjoint cycles. We consider also variants of the problem involving for example disjoint long cycles.   This is joint work with Valentas Kurauskas and Mihyun Kang.
Tue, 10/11/2009
16:30 		Gregory Sorkin (IBM Research NY) Combinatorial Theory Seminar Add to calendar SR2
The Power of Choice in a Generalized Polya Urn Model
HTML clipboard We introduce a "Polya choice" urn model combining elements of the well known "power of two choices" model and the "rich get richer" model. From a set of $ k $ urns, randomly choose $ c $ distinct urns with probability proportional to the product of a power $ \gamma>0 $ of their occupancies, and increment one with the smallest occupancy. The model has an interesting phase transition. If $ \gamma \leq 1 $, the urn occupancies are asymptotically equal with probability 1. For $ \gamma>1 $, this still occurs with positive probability, but there is also positive probability that some urns get only finitely many balls while others get infinitely many.
Tue, 17/11/2009
14:30 		Imre Leader (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Higher Order Tournaments
Given $ n $ points in general position in the plane, how many of the triangles formed by them can contain the origin? This problem was solved 25 years ago by Boros and Furedi, who used a beautiful translation of the problem to a non-geometric setting. The talk will start with background, including this result, and will then go on to consider what happens in higher dimensions in the geometric and non-geometric cases.
Tue, 24/11/2009
14:30 		Peter Allen (Warwick) Combinatorial Theory Seminar Add to calendar L3
Dense $ H $-free graphs are almost $ (\chi(H)-1) $-partite
Zarankiewicz showed that no $ K_{r+1} $-free graph with minimum degree exceeding $ (r-1)n/r $ can exist. This was generalised by Erdös and Stone, who showed that $ K_{r+1} $ may be replaced by any graph $ H $ with chromatic number $ r+1 $ at the cost of a $ o(n) $ term added to the minimum degree. Andrásfai, Erdös and Sós proved a stability result for Zarankiewicz' theorem: $ K_{r+1} $-free graphs with minimum degree exceeding $ (3r-4)n/(3r-1) $ are forced to be $ r $-partite. Recently, Alon and Sudakov used the Szemerédi Regularity Lemma to obtain a corresponding stability result for the Erdös-Stone theorem; however this result was not best possible. I will describe a simpler proof (avoiding the Regularity Lemma) of a stronger result which is conjectured to be best possible.

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

Syndicate content