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 British Combinatorial Committee is gratefully acknowledged.
Programme
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.
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.
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.
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 {\em 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.