Past Seminars › Seminar Series

Combinatorial Theory Seminar (past)

Tue, 02/03/2010
14:30 		Nicolas Trotignon (Paris) Combinatorial Theory Seminar Add to calendar L3
Decomposition of graphs and $ \chi $-boundedness
A graph is $ \chi $-bounded with a function $ f $ is for all induced subgraph H of G, we have $ \chi(H) \le f(\omega(H)) $.  Here, $ \chi(H) $ denotes the chromatic number of $ H $, and $ \omega(H) $ the size of a largest clique in $ H $. We will survey several results saying that excluding various kinds of induced subgraphs implies $ \chi $-boundedness. More precisely, let $ L $ be a set of graphs. If a $ C $ is the class of all graphs that do not any induced subgraph isomorphic to a member of $ L $, is it true that there is a function $ f $ that $ \chi $-bounds all graphs from $ C $? For some lists $ L $, the answer is yes, for others, it is no.   A decomposition theorems is a theorem saying that all graphs from a given class are either "basic" (very simple), or can be partitioned into parts with interesting relationship. We will discuss whether proving decomposition theorems is an efficient method to prove $ \chi $-boundedness. 
Tue, 23/02/2010
14:30 		Lowell Beineke (Purdue) Combinatorial Theory Seminar Add to calendar L3
Line Graphs and Beyond
The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations.  In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).
Tue, 23/02/2010
14:30 		Lowell Beineke (Purdue) Combinatorial Theory Seminar Add to calendar L3
Line Graphs and Beyond
The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations. In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).
Tue, 16/02/2010
14:30 		Vadim Lozin (Warwick) Combinatorial Theory Seminar Add to calendar L3
Boundary properties of graphs
The notion of a boundary graph property is a relaxation of that of a minimal property. Several fundamental results in graph theory have been obtained in terms of identifying minimal properties. For instance, Robertson and Seymour showed that there is a unique minimal minor-closed property with unbounded tree-width (the planar graphs), while Balogh, Bollobás and Weinreich identified nine minimal hereditary properties of labeled graphs with the factorial speed of growth. However, there are situations where the notion of minimal property is not applicable. A typical example of this type is given by graphs of large girth. It is known that for each particular value of k, the graphs of girth at least k are of unbounded tree-width and their speed of growth is superfactorial, while the limit property of this sequence (i.e., the acyclic graphs) has bounded tree-width and its speed of growth is factorial. To overcome this difficulty, the notion of boundary properties of graphs has been recently introduced. In the present talk, we use this notion in order to identify some classes of graphs which are well-quasi-ordered with respect to the induced subgraph relation.
Tue, 09/02/2010
14:30 		David Conlon (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Combinatorial theorems in random sets
The famous theorem of Szemerédi says that for any natural number $ k $ and any $ a>0 $ there exists $ n $ such that if $ N\ge n $ then any subset $ A $ of the set $ [N] =\{1, 2,\ldots , N\} $ of size $ |A| \ge a N $ contains an arithmetic progression of length $ k $. We consider the question of when such a theorem holds in a random set. More precisely, we say that a set $ X $ is $ (a, k) $-Szemerédi if every subset $ Y $ of $ X $ that contains at least $ a|X| $ elements contains an arithmetic progression of length $ k $. Let $ [N]_p $ be the random set formed by taking each element of $ [N] $ independently with probability $ p $. We prove that there is a threshold at about $ p = N^{-1/(k-1)} $ where the probability that $ [N]_p $ is $ (a, k) $-Szemerédi changes from being almost surely 0 to almost surely 1. There are many other similar problems within combinatorics. For example, Turán’s theorem and Ramsey’s theorem may be relativised, but until now the precise probability thresholds were not known. Our method seems to apply to all such questions, in each case giving the correct threshold. This is joint work with Tim Gowers.
Tue, 26/01/2010
14:30 		Jan Hladky (University of Warwick) Combinatorial Theory Seminar Add to calendar L3
Tree packing conjectures; Graceful tree labelling conjecture
A family of graphs $ H_1,...,H_k $ packs into a graph $ G $ if there exist pairwise edge-disjoint copies of $ H_1,...,H_k $ in $ G $. Gyarfas and Lehel conjectured that any family $ T_1, ..., T_n $ of trees of respective orders $ 1, ..., n $ packs into $ K_n $. A similar conjecture of Ringel asserts that $ 2n $ copies of any trees $ T $ on $ n+1 $ vertices pack into $ K_{2n+1} $. In a joint work with Boettcher, Piguet, Taraz we proved a theorem about packing trees. The theorem implies asymptotic versions of the above conjectures for families of trees of bounded maximum degree. Tree-indexed random walks controlled by the nibbling method are used in the proof. In a joint work with Adamaszek, Adamaszek, Allen and Grosu, we used the nibbling method to prove the approximate version of the related Graceful Tree Labelling conjecture for trees of bounded degree. In the talk we shall give proofs of both results. We shall discuss possible extensions thereof to trees of unbounded degree.
Tue, 19/01/2010
14:30 		Peter Keevash (QMUL) Combinatorial Theory Seminar Add to calendar L3
Shadows and intersections: stability and new proofs
We give a short new proof of a version of the Kruskal-Katona theorem due to Lovász. Our method can be extended to a stability result, describing the approximate structure of configurations that are close to being extremal, which answers a question of Mubayi. This in turn leads to another combinatorial proof of a stability theorem for intersecting families, which was originally obtained by Friedgut using spectral techniques and then sharpened by Keevash and Mubayi by means of a purely combinatorial result of Frankl. We also give an algebraic perspective on these problems, giving yet another proof of intersection stability that relies on expansion of a certain Cayley graph of the symmetric group, and an algebraic generalisation of Lovász’s theorem that answers a question of Frankl and Tokushige.
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.
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, 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, 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
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, 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, 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, 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, 16/06/2009
14:30 		Amin Coja-Oghlan (Edinburgh) Combinatorial Theory Seminar Add to calendar L3
A better algorithm for random k-SAT
Let $ F $ be a uniformly distributed random $ k $-SAT formula with $ n $ variables and $ m $ clauses. We present a polynomial time algorithm that finds a satisfying assignment of $ F $ with high probability for constraint densities $ m/n < 2^k \ln(k)/k $. Previously no efficient algorithm was known to find solutions with a non-vanishing probability beyond $ m/n=1.817 2^k/k $ [Frieze and Suen, Journal of Algorithms 1996]. The density $ 2^k \ln(k)/k $ matches the replica symmetry breaking transition, whose existence was recently established rigorously [Achlioptas and Coja-Oghlan, FOCS 2008].
Tue, 02/06/2009
14:30 		Ben Green (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Approximate groups
Let $ A $ be a finite set in some ambient group. We say that $ A $ is a $ K $-approximate group if $ A $ is symmetric and if the set $ A.A $ (the set of all $ xy $, where $ x $, $ y $ lie in $ A $) is covered by $ K $ translates of $ A $. I will illustrate this notion by example, and will go on to discuss progress on the "rough classification" of approximate groups in various settings: abelian groups, nilpotent groups and matrix groups of fixed dimension. Joint work with E. Breuillard.
Tue, 26/05/2009
14:30 		Mark Walters (QMUL) Combinatorial Theory Seminar Add to calendar L3
Hamilton cycles in random geometric graphs
The Gilbert model of a random geometric graph is the following: place points at random in a (two-dimensional) square box and join two if they are within distance $ r $ of each other. For any standard graph property (e.g.  connectedness) we can ask whether the graph is likely to have this property.  If the property is monotone we can view the model as a process where we place our points and then increase $ r $ until the property appears.  In this talk we consider the property that the graph has a Hamilton cycle.  It is obvious that a necessary condition for the existence of a Hamilton cycle is that the graph be 2-connected. We prove that, for asymptotically almost all collections of points, this is a sufficient condition: that is, the smallest $ r $ for which the graph has a Hamilton cycle is exactly the smallest $ r $ for which the graph is 2-connected.  This work is joint work with Jozsef Balogh and Béla Bollobás
Tue, 19/05/2009
14:30 		Jozef Skokan (LSE) Combinatorial Theory Seminar Add to calendar L3
Multicolour Ramsey numbers for cycles
For graphs $ L_1,\dots,L_k $, the Ramsey number $ R(L_1,\ldots,L_k) $ is the minimum integer $ N $ such that for any edge-colouring of the complete graph $ K_N $ by $ k $ colours there exists a colour $ i $ for which the corresponding colour class contains $ L_i $ as a subgraph. In this talk, we shall discuss recent developments in the case when the graphs $ L_1,\dots,L_k $ are all cycles and $ k\ge2 $.
Tue, 12/05/2009
14:30 		Mihyun Kang (TU Berlin) (TU Berlin) Combinatorial Theory Seminar Add to calendar L3
How to count planar graphs

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

Syndicate content