# Past Combinatorial Theory Seminar

18 October 2011
14:30
Professor Geoff Whittle
Abstract
<p><div>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.</div><div></div><div></div><div>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.</div><div></div><div></div><div>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</div></p>
• Combinatorial Theory Seminar
11 October 2011
14:30
David Conlon
Abstract
<p>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.</p>
• Combinatorial Theory Seminar
14 June 2011
14:30
Jaroslav Nesetril
Abstract
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.
• Combinatorial Theory Seminar
7 June 2011
14:30
Gregory Sorkin
Abstract
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.
• Combinatorial Theory Seminar
31 May 2011
14:30
Colin Cooper
Abstract
<p>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&nbsp; size $O(\log n)$ and for $t\geq (1+\epsilon)t^*$ we have only components of&nbsp; size $O(\log n)$. <br /><br />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.<br /><br /></p>
• Combinatorial Theory Seminar
24 May 2011
14:30
Angelika Steger
Abstract
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.)
• Combinatorial Theory Seminar
10 May 2011
14:30
Penny Haxell
Abstract
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.
• Combinatorial Theory Seminar
3 May 2011
14:30
Bruce Reed
Abstract
<p>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.</p>
• Combinatorial Theory Seminar
8 March 2011
14:30
Dominic Welsh
Abstract
I shall describe some recent results about the asymptotic behaviour of matroids. Specifically almost all matroids are simple and have probability at least 1/2 of being connected. Also, various quantitative results about rank, number of bases and number and size of circuits of almost all matroids are given. There are many open problems and I shall not assume any previous knowledge of matroids. This is joint work, see below. 1 D. Mayhew, M. Newman, D. Welsh and G. Whittle, On the asymptotic properties of connected matroids, European J. Combin. to appear 2 J. Oxley, C. Semple, L. Wasrshauer and D. Welsh, On properties of almost all matroids, (2011) submitted
• Combinatorial Theory Seminar
22 February 2011
14:30
James King
Abstract
• Combinatorial Theory Seminar