Harald Helfgott, a friend of SymOmega, has only yesterday uploaded an article on the arxiv claiming a proof of the “Ternary Goldbach Conjecture”:
Every odd integer is the sum of three primes.
This is big news in number theory since it is one of the best results on the Goldbach Conjecture to date. The “Ternary GC” also had its origins in the letters of Goldbach and Euler in 1742, and is sometimes referred to as Goldbach’s weak conjecture, since if every even number greater than 4 is the sum of two primes, then by adding the number 3 to the two primes will result in every odd number greater than 5 being the sum of three primes.
I’ve just posted a paper entitled “The Merino-Welsh Conjecture holds for Series-Parallel Graphs” to the arxiv which proves precisely the assertion given in the paper’s title. This paper resulted from Steve Noble’s visit here last year, where we worked quite hard on this conjecture, and in fact I blogged about the problem then. The conjecture is that the number of spanning trees of a graph is dominated either by the number of acyclic orientations or by the number of totally cyclic orientations.
Previous results on the Merino-Welsh conjecture had proved the result for either very sparse graphs (where the number of spanning trees is dominated by the number of acyclic orientations) or very dense graphs (where the number of spanning trees is dominated by the number of totally cyclic orientations) regardless of the graph’s structure. However for intermediate-sized graphs — in particular those with — the graph structure counts, and there is a subtle interplay between the numbers of the two types of orientations.
Series-parallel graphs are always a great test case, because there is a natural decomposition of a series-parallel graph into smaller series-parallel graphs that provides an ideal inductive framework for a vast range of applications. For us, it provides enough structure to be able to keep track of the numbers of spanning trees and both types of orientation. Not entirely precisely, but enough to identify certain series-parallel graphs that cannot form part of a minimal counterexample to the conjecture. Working systematically, it was possible to ultimately exhaust all the possibilities for graphs that might be part of a minimal counterexample, thereby showing that this hypothetical counterexample cannot actually exist.
On one hand, I rather like this paper because the approach to coping with the interaction between the parameters seems novel and interesting, but on the other hand it relies heavily on the very constrained construction steps allowed in building series-parallel graphs and so will be almost impossible to generalise to larger classes!
A position here in the School of Maths and Stats at UWA has just been advertised. It is a full-time continuing position as either an Assistant or Associate Professor (Level B/C) and the school is looking for ` a generalist mathematician with excellent skills in teaching and learning to develop and deliver a range of first year units to students from across the University.’ More details are available at the link above and queries should be directed to the Head of School, Andrew Bassom.
Over the summer break, John and I each supervised a 2nd year undergraduate student in a research project, and the previous post summarised Michael Martis’ project. I supervised Melissa Lee, who learned about the energy of graphs and this is what she did
Hello everyone! My name is Melissa Lee and I’m about to start my third year of Chemical Engineering and Pure Mathematics at UWA. Over these summer holidays, I’ve been given the opportunity to take on a six week research project with Professor Gordon Royle. The area that I have researched is the energy of graphs, with a particular focus on extremal cases. It’s been a new and exciting time for me, being my first experience of research and also my first taste of graph theory.
The idea of the energy of a graph was first introduced by Serbian mathematician Ivan Gutman at a conference in Austria in 1978. Its origins lie in chemistry, where it is defined as “the total electron energy of a conjugated hydrocarbon as calculated with the Hückel Molecular Orbital method”. The concept didn’t receive much attention from mathematicians for many years. However, sometime around the turn of the century, mathematicians realised its value and since then, increasing numbers of papers have been published each year about the energy of graphs.
This year’s Australasian Conference on Combinatorial Mathematics and Combinatorial Computing will be held here at UWA from the 9th to 13th of December. Put the date in your diary now and start looking for cheap flights to Perth.
The conference webpage is available here, where you can find the exciting lineup of invited speakers that we have lined up so far.
Details of previous conferences in the series are available at the CMSA webpage.
Regular readers of this blog (hi mum!) will already know that chromatic polynomials are one of my favourite research topics, and one on which I have made several posts.
Well, when I was in Sydney last year, my old friend Graham Farr pointed out that the cusp of 2012/2013 is the centenary of the chromatic polynomial, because the paper in which it originated “A determinant formula for the number of ways of coloring a map” was published in the Annals of Mathematics, 14 and dated 1912-1913. Of course the original aim was to prove the four-colour theorem quantitatively by showing that for any planar graph , but this never worked out.
So it’s now been 100 years since the chromatic polynomial arrived, and there’s still lots about it that we don’t understand, so Happy Birthday, Chromatic Polynomial!
One of the most irritating things that we don’t understand is actually the very first conjecture about chromatic roots. In 1946, Birkhoff & Lewis did manage to prove that for a planar graph and any real and started the study of real chromatic roots. They also conjectured that for any real which of course implies the four-colour theorem and more. While chromatic roots (integer, real, complex) have been intensively studied, partly because the chromatic polynomial is intimately related to the partition function of the -state Potts model, it is slightly embarrassing that we cannot even answer this very first problem, now obviously known as the Birkhoff-Lewis conjecture.
Birkhoff-Lewis conjecture: If is a planar graph then for .
I’ve tried quite hard to solve this problem, but there are no obvious weak points to attack. Beraha and Kahane showed that planar graphs have complex chromatic roots arbitrarily close to , while Sokal showed that they have complex chromatic roots arbitrarily close to any point in the complex plane and I showed that they have real chromatic roots arbitrarily close to, but smaller than, .
So it’s just this one little interval that is the only possibly unresolved root-free region amidst a sea of chromatic roots! I’m busy applying for grants now and working up to another attack on chromatic roots. I won’t promise to solve this problem of course, because it’s obviously hard, but I can always hope!