Past Seminars › Seminar Series

Combinatorial Theory Seminar (past)

Tue, 06/03/2012
14:30 		Nikolaos Fountoulakis (Birmingham) Combinatorial Theory Seminar Add to calendar L3
Random graphs on spaces of negative curvature
Random geometric graphs have been well studied over the last 50 years or so. These are graphs that are formed between points randomly allocated on a Euclidean space and any two of them are joined if they are close enough. However, all this theory has been developed when the underlying space is equipped with the Euclidean metric. But, what if the underlying space is curved? The aim of this talk is to initiate the study of such random graphs and lead to the development of their theory. Our focus will be on the case where the underlying space is a hyperbolic space. We will discuss some typical structural features of these random graphs as well as some applications, related to their potential as a model for networks that emerge in social life or in biological sciences.
Tue, 28/02/2012
14:30 		Penny Haxell (Waterloo) Combinatorial Theory Seminar Add to calendar L3
On packing and covering in hypergraphs
We discuss some recent developments on the following long-standing problem known as Ryser's conjecture. Let $ H $ be an $ r $-partite $ r $-uniform hypergraph. A matching in $ H $ is a set of disjoint edges, and we denote by $ \nu(H) $ the maximum size of a matching in $ H $. A cover of $ H $ is a set of vertices that intersects every edge of $ H $. It is clear that there exists a cover of $ H $ of size at most $ r\nu(H) $, but it is conjectured that there is always a cover of size at most $ (r-1)\nu(H) $.
Tue, 21/02/2012
14:30 		Mark Walters Combinatorial Theory Seminar Add to calendar L3
Lion and Man: Can both win?
Rado introduced the following `lion and man' game in the 1930's: two players (the lion and the man) are in the closed unit disc and they can run at the same speed. The lion would like to catch the man and the man would like to avoid being captured.This game has a chequered history with several false `winning strategies' before Besicovitch finally gave a genuine winning strategy.We ask the surprising question: can both players win?
Tue, 14/02/2012
14:30 		Tobias Mueller, Amsterdam Combinatorial Theory Seminar Add to calendar L3
Line arrangements and geometric representations of graphs
A dot product representation of a graph assigns to each vertex $ s $ a vector $ v(s) $ in $ {\bf R}^k $ in such a way that $ v(s)^T v(t) $ is greater than $ 1 $ if and only $ st $ is an edge. Similarly, in a distance representation $ |v(s)-v(t)| $ is less than $ 1 $ if and only if $ st $ is an edge. I will discuss the solution of some open problems by Spinrad, Breu and Kirkpatrick and others on these and related geometric representations of graphs. The proofs make use of a connection to oriented pseudoline arrangements. (Joint work with Colin McDiarmid and Ross Kang)
Tue, 07/02/2012
14:30 		Imre Leader (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Positive projections
If $ A $ is a set of $ n $ positive integers, how small can the set $ \{ x/(x,y) : x,y \in A \} $ be? Here, as usual, $ (x,y) $ denotes the highest common factor of $ x $ and $ y $. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set $ A $ of $ n $ points in the integer grid $ {\bf Z}^d $, how small can $ (A-A)^+ $, the projection of the difference set of $ A $ onto the positive orthant, be? Freiman and Lev gave an example to show that (in any dimension) the size can be as small as $ n^{2/3} $ (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least $ n^{2/3} $, and they asked if this holds in any dimension. After some background material, the talk will focus on recent developments. Joint work with Béla Bollobás.
Tue, 31/01/2012
14:30 		Lutz Warnke Combinatorial Theory Seminar Add to calendar L3
The early evolution of Achlioptas processes
In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. Although the evolution of such `local' modifications of the Erdös-Rényi random graph processes has received considerable attention during the last decade, so far only rather `simple' rules are well-understood. Indeed, the main focus has been on bounded size rules (where all component sizes larger than some constant B are treated the same way), and for more complex rules hardly any rigorous results are known. In this talk we will discuss a new approach that applies to many involved Achlioptas processes: it allows us to prove that certain key statistics are tightly concentrated during the early evolution of e.g. the sum and product rule. Joint work with Oliver Riordan.
Tue, 24/01/2012
14:30 		Mihyun Kang (TU Graz) Combinatorial Theory Seminar Add to calendar L3
The phase transition in random graph processes through the lens of PDE and singularity analysis
The phase transition deals with sudden global changes and is observed in many fundamental random discrete structures arising from statistical physics, mathematics and theoretical computer science, for example, Potts models, random graphs and random $ k $-SAT. The phase transition in random graphs refers to the phenomenon that there is a critical edge density, to which adding a small amount results in a drastic change of the size and structure of the largest component. In the Erdős–Rényi random graph process, which begins with an empty graph on $ n $ vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches $ n/2 $ and a giant component emerges. Since this seminal work of Erdős and Rényi, various random graph processes have been introduced and studied. In this talk we will discuss new approaches to study the size and structure of components near the critical point of random graph processes: key techniques are the classical ordinary differential equations method, a quasi-linear partial differential equation that tracks key statistics of the process, and singularity analysis.
Tue, 22/11/2011
14:30 		Tom Sanders (Oxford) Combinatorial Theory Seminar Add to calendar L3
Structure and the Fourier transform
We shall discuss how the algebra norm can be used to identify structure in groups. No prior familiarity with the area will be assumed.
Tue, 15/11/2011
14:30 		Wojciech Samotij (Cambridge) Combinatorial Theory Seminar Add to calendar L3
Independent sets in hypergraphs
We say that a hypergraph is stable if each sufficiently large subset of its vertices either spans many hyperedges or is very structured. Hypergraphs that arise naturally in many classical settings posses the above property. For example, the famous stability theorem of Erdos and Simonovits and the triangle removal lemma of Ruzsa and Szemeredi imply that the hypergraph on the vertex set $ E(K_n) $ whose hyperedges are the edge sets of all triangles in $ K_n $ is stable. In the talk, we will present the following general theorem: If $ (H_n)_n $ is a sequence of stable hypergraphs satisfying certain technical conditions, then a typical (i.e., uniform random) $ m $-element independent set of $ H_n $ is very structured, provided that $ m $ is sufficiently large. The above abstract theorem has many interesting corollaries, some of which we will discuss. Among other things, it implies sharp bounds on the number of sum-free sets in a large class of finite Abelian groups and gives an alternate proof of Szemeredi’s theorem on arithmetic progressions in random subsets of integers. Joint work with Noga Alon, Jozsef Balogh, and Robert Morris.
Tue, 08/11/2011
14:30 		Diana Piguet (Birmingham) Combinatorial Theory Seminar Add to calendar L3
Embedding trees in sparse graphs
An embedding of a graph H in a graph G is an injective mapping of the vertices of H to the vertices of G such that edges of H are mapped to edges of G. Embedding problems have been extensively studied. A very powerful tool in this area is Szemeredi's Regularity Temma. It approximates the host graph G by a quasirandom graph which inherits many of the properties of G. Unfortunately the direct use of Szemeredi's Regularity Lemma is useless if the host graph G is sparse. During the talk I shall expose a technique to deal with embedding trees in sparse graphs. This technique has been developed by Ajtai, Komlos,Simonovits and Szemeredi to solve the Erdos-Sos conjecture. Presently the author together with Hladky, Komlos, Simonovits, Stein and Szemeredi apply this method to solve the related conjecture of Loebl, Komlos and Sos (approximate version).
Tue, 25/10/2011
14:30 		Bjarne Toft (University of Southern Denmark) Combinatorial Theory Seminar Add to calendar L3
The board game Hex – history, results, problems
Hex was discovered independently by Piet Hein in Copenhagen in 1942 and byJohn Nash in Princeton in 1948.  The game is interesting because its rules are very simple, yet it is not known how to play best possible.  For example, a winning first move for the first player (who does have  a winning strategy) is still unknown. The talk will tell the history of the game and give simple proofs for basic results about it. Also the reverse game of HEX,sometimes called REX, will be discussed. New results about REX are under publication in Discrete Mathematics in a paper:  How to play Reverse Hex (joint work with Ryan Hayward and Phillip Henderson).
Tue, 18/10/2011
16:00 		Professor Geoff Whittle (Victoria University of Wellington) Combinatorial Theory Seminar Add to calendar L1
LMS Aitken Lecture: "Matroid Representation over Infinite Fields"
 A canonical way to obtain a matroid is from a finite set of vectors in a vector space over a field F. A matroid that can be obtained in such a way is said to be representable over F. It is clear that when Whitney first defined matroids he had matroids representable over the reals as his standard model, but for a variety of reasons most attention has focussed on matroids representable over finite fields. There is increasing evidence that the class of matroids representable over a fixed finite field is well behaved with strong general theorems holding. Essentially none of these theorems hold if F is infnite. Indeed matroids representable over the real– the natural matroids for our geometric intuition – turn out to be a mysterious class indeed. In the talk I will discuss this striking contrast in behaviour. 
Tue, 18/10/2011
14:30 		Professor Geoff Whittle (Victoria University of Wellington) Combinatorial Theory Seminar Add to calendar L3
LMS Aitken Lecture: "Well-quasi-ordering Binary Matroids"
The Graph Minors Project of Robertson and Seymour is one of the highlights of twentieth-century mathematics. In a long series of mostly difficult papers they prove theorems that give profound insight into the qualitative structure of members of proper minor-closed classes of graphs. This insight enables them to prove some remarkable banner theorems, one of which is that in any infinite set of graphs there is one that is a minor of the other; in other words, graphs are well-quasi-ordered under the minor order.A canonical way to obtain a matroid is from a set of columns of a matrix over a field. If each column has at most two nonzero entries there is an obvious graph associated with the matroid; thus it is not hard to see that matroids generalise graphs. Robertson and Seymour always believed that their results were special cases of more general theorems for matroids obtained from matrices over nite elds. For over a decade, Jim Geelen, Bert Gerards and I have been working towards achieving this generalisation. In this talk I will discuss our success in achieving the generalisation for binary matroids, that is, for matroids that can be obtained from matrices over the 2-element field.In this talk I will give a very general overview of my work with Geelen and Gerards. I will not assume familiarity with matroids nor will I assume familiarity with the results of the Graph Minors Project
Tue, 11/10/2011
14:30 		David Conlon (Oxford) Combinatorial Theory Seminar Add to calendar L3
Induced graph removal
The induced graph removal lemma states that for any fixed graph $ H $ on $ h $ vertices and any $ e\textgreater 0 $ there exists $ d\textgreater0 $ such that any graph $ G $ with at most $ d n^h $ induced copies of $ H $ may be made $ H $-free by adding or removing atmost $ e n^2 $ edges. This fact was originally proven by Alon, Fischer, Krivelevich and Szegedy. In this talk, we discuss a new proof and itsrelation to various regularity lemmas. This is joint work with Jacob Fox.
Tue, 14/06/2011
14:30 		Jaroslav Nesetril (Prague) Combinatorial Theory Seminar Add to calendar L3
Ramsey Classes of Graphs and Beyond
It is known that generic and universal structures and Ramsey classes are related. We explain this connection and complement it by some new examples. Particularly we disscuss universal and Ramsey classes defined by existence and non-existence of homomorphisms.
Tue, 07/06/2011
14:30 		Gregory Sorkin (LSE) Combinatorial Theory Seminar Add to calendar L3
Average-case performance of three-dimensional assignment heuristics
The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to π^2/6.  In dimensions 3 and higher, the "planar" assignment problem is NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do?  In d dimensions, the expected cost is of order at least n^{2-d} and at most ln n times larger, but the upper bound is non-constructive.  For 3 dimensions, we show a heuristic capable of producing a solution within a factor n^ε of the lower bound, for any constant ε, in time of order roughly n^{1/ε}.  In dimensions 4 and higher, the question is wide open: we don't know any reasonable average-case assignment heuristic.
Tue, 31/05/2011
14:30 		Colin Cooper (King's College London) Combinatorial Theory Seminar Add to calendar L3
Component structure of the vacant set induced by a random walk on a random graph
We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices or vacant set. In both cases, the size of the vacant set $ N(t) $ can be obtained explicitly as a function of $ t $. Let $ \Gamma(t) $ be the subgraph induced by the vacant set. We show that, for random graphs $ G_{n,p} $ above the connectivity threshold, and for random regular graphs $ G_r $, for constant $ r\geq 3 $, there is a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for $ t\leq (1-\epsilon)t^* $ we have a unique giant plus components of  size $ O(\log n) $ and for $ t\geq (1+\epsilon)t^* $ we have only components of  size $ O(\log n) $. In the case of $ G_r $ we describe the likely degree sequence, size of the giant component and structure of the small ($ O(\log n) $) size components.
Tue, 24/05/2011
14:30 		Angelika Steger (ETH Zurich) Combinatorial Theory Seminar Add to calendar L3
The degree distribution of random planar graphs
A random planar graph $ P_n $ is a graph drawn uniformly at random from the class of all (labelled) planar graphs on $ n $ vertices. In this talk we show that with probability $ 1-o(1) $ the number of vertices of degree $ k $ in $ P_n $ is very close to a quantity $ d_k n $ that we determine explicitly. Here $ k=k(n) \le c \log n $. In the talk our main emphasis will be on the techniques for proving such results. (Joint work with Kosta Panagiotou.)
Tue, 10/05/2011
14:30 		Penny Haxell (Waterloo) Combinatorial Theory Seminar Add to calendar L3
Edge colouring multigraphs
We highlight a technique for studying edge colourings of multigraphs, due to Tashkinov. This method is a sophisticated generalisation of the method of alternating paths, and builds upon earlier work by Kierstead and Goldberg. In particular we show how to apply it to a number of edge colouring problems, including the question of whether the class of multigraphs that attain equality in Vizing's classical bound can be characterised. This talk represents joint work with Jessica McDonald.
Tue, 03/05/2011
14:30 		Bruce Reed (McGill) Combinatorial Theory Seminar Add to calendar L3
Hajos’ Conjecture is almost always true
In 1961 Hajos conjectured that if a graph contains no subdivsion of a clique of order t then its chromatic number is less than t. In 1981, Erdos and Fajtlowicz showed that the conjecture is almost always false. We show it is almost always true. This is joint work with Keevash, Mohar, and McDiarmid.

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

Syndicate content