Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

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

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

Syndicate content