Forthcoming Seminars › Seminar Series

Combinatorial Theory Seminar

Tue, 18/01/2011
14:30 		Christopher Dowden Combinatorial Theory Seminar Add to calendar L3
"Extremal planar graphs"
Tue, 08/02/2011
16:30 		Lutz Warnke Combinatorial Theory Seminar Add to calendar SR2
"The C_ell -free process".
The $ C_\ell $-free process starts with the empty graph on $ n $ vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of $ C_\ell $ is created. For every $ \ell \geq 4 $ we show that, with high probability as $ n \to \infty $, the maximum degree is $ O((n \log n)^{1/(\ell-1)}) $, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the $ C_\ell $-free process typically terminates with $ \Theta(n^{\ell/(\ell-1)}(\log n)^{1/(\ell-1)}) $ edges, which answers a question of Erd\H{o}s, Suen and Winkler. This is the first result that determines the final number of edges of the more general $ H $-free process for a non-trivial class of graphs $ H $. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to `transfer' certain decreasing properties from the binomial random graph to the $ H $-free process.
Tue, 08/03/2011
14:30 		Dominic Welsh (Oxford) Combinatorial Theory Seminar Add to calendar L3
"Random matroids"
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

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

Syndicate content