Combinatorics › Past Events › One-Day Meeting 2006

One-Day Meeting in Combinatorics 2006

Wednesday, 15 March 2006 10.30 am   Coffee       11.00 am   Bert Gerards (CWI Amsterdam)     Towards a structure theory for matrices and matroids       11.55 am   Marc Noy (Univ. Politicnica de Catalunya)     Counting labelled planar graphs       12.50 pm   Lunch       2.15 pm   Peter Cameron (QMUL)     Orbital chromatic roots       3.10 pm   Angelika Steger (ETH Zurich)     Extremal subgraphs of random graphs       4.05 pm   Tea       4.30 pm   Alan Frieze (Carnegie Mellon)     Anti-Ramsey properties of random graphs The meeting will take place in the Mathematical Institute, University of Oxford. Anyone interested is welcome to attend. Some funds may be  available to contribute to the expenses of research students who wish to attend the meeting. Further details can be obtained from Alex Scott. Support for this event by the London Mathematical Society and the Peter Cameron (Queen Mary University of London) Orbital chromatic roots Given a graph and a group of automorphisms of the graph, there is a polynomial (the orbital chromatic polynomial) which counts orbits of the group on proper colourings of the graph. This reduces to the usual chromatic polynomial if the group is trivial. Unlike the chromatic polynomial, the real roots of orbital chromatic polynomials are dense in the real numbers. However, under certain parity conditions on the automorphisms, we find the same zero-free intervals as are known for the chromatic polynomial. There is an analogous orbital polynomial for flows in a given finite abelian group A; but it is a multivariate polynomial, and to count orbits on flows we have to substitute for the variables the numbers of elements of various orders in A. In some situations, it reduces to a univariate polynomial: for example, if the order of A is coprime to the order of the automorphism group, or if A is a group of prime exponent. In these case, we can ask about orbital flow roots. Much less is known than for orbital chromatic roots. Alan Frieze (Carnegie Mellon) Anti-Ramsey properties of random graphs A colouring of the edges of a graph G is b-bounded if no colour is used more than b times. A set of edges X is polychromatic if no colour appears twice among X. We study some instances of the question: Does there exist a b-bounded colouring of G which does not contain a polychromatic copy of H, where H is polychromatic if E(H) is? We review some earlier results and estimate thresholds in the case of random graphs. Joint work with Tom Bohman, Oleg Pikhurko and Cliff Smyth. Bert Gerards (CWI Amsterdam) Towards a structure theory for matrices and matroids Together with Jim Geelen and Geoff Whittle, we are currently undertaking a program of research aimed at extending the results and techniques of the Graph Minors Project of Robertson and Seymour to matrices and matroids. During this talk I report on where we stand and where we expect to go. Marc Noy (Univ. Politicnica de Catalunya) Counting labelled planar graphs We present a precise asymptotic estimate for the number of labelled planar graphs with $ n $ vertices. The proof is based on singularity analysis of generating functions. The same technique also allows us to prove that the number of edges in random planar graphs follows asymptotically a normal limit law with mean and variance linear in $ n $. Other parameters in random planar graphs, like the number of connected components, are analyzed as well. Angelika Steger (ETH Zurich) Extremal subgraphs of random graphs For a graph $ G $, let $ ET(G) $ denote the maximum number of edges in a triangle-free subgraph (not necessarily induced) of $ G $, and let $ EB(G) $ be the maximum number of edges in a bipartite subgraph of $ G $. So $ EB(G) $ is just the maximum size of a cut in $ G $. Of course, we always have $ ET(G) \ge EB(G) $, but the general intuition – guided by various known results – suggests that, for dense enough graphs, these two parameters will typically be equal. In a 1990 paper, Babai, Simonovits and Spencer studied these parameters for random graphs $ G(n,p) $ and confirmed this intuition for dense graphs. In particular, they proved that there is a positive constant $ \delta $ such that, for $ p \ge 1/2 - \delta $, with high probability we have $ ET(G(n,p)) = EB(G(n,p)) $. Babai, Simonovits and Spencer asked whether this result could be extended to cover all constant values of $ p $. We this talk we answer this question affirmatively and show that the above property in fact holds whenever $ p=p(n) \ge n^{-\delta} $, for some fixed $ \delta > 0 $. This is joint work with Graham Brightwell and Konstantinos Panagiotou.

Last updated by Keith A. Gillow on Sun, 05/09/2010 - 8:58am from a page originally created by Waldemar Schlackow.
This page is maintained by Alex Scott. Please use the contact form for feedback and comments.