Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

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

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

Syndicate content