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!
Tim Gowers has just announced an exciting new development where it seems that maths is leading the way into a new era of refereed publication. The idea (as I can fathom) is that a journal is a certified front for refereed articles posted on the arxiv. So for example, let’s suppose my fictitious journal — Journal of Good News in Mathematics — has a chief editor and 8 other editors whose job is to organise the refereeing of articles that are submitted to the journal as links to the arxiv. Because there is now no control of the typesetting, the editors may each ask at their discretion for authors to meet a typesetting standard: for example, that all submissions be originally typeset in LaTeX and that there be MSC numbers, keywords, and a concise abstract. Then control of typesetting standards can be administered through the editors refereeing process. It would be very interesting to see if the software can be made to make the initial setup as seamless as possible. That way, it would not take much effort at all for an already existing gold or diamond open access journal to convert directly to this revolutionary new medium.
We again have two new postdoctoral positions in the Centre for the Mathematics of Symmetry and Computation here at UWA, funded by two Australian Research Council Discovery Project grants. Both are two-year positions and in the field of finite permutation groups and graph symmetry. One position is on a grant held by Michael Giudici and the other is on a grant held by myself, Alice Devillers, and Cheryl Praeger.
The deadline for applications is 8th February (2013).
More details and instructions on how to apply can be found here (refs 4261 and 4262).
A while ago, I used the mixed-integer linear programming software Gurobi to show that there are no Cameron-Liebler line classes with certain parameters, and recently I’ve looked at a similarly difficult computational problem: packings of 3-dimensional projective space. But first, some motivation.
Here in the Southern Hemisphere, our academic year is ending and with the jacarandas blooming, the weather heating up and the smell of ripe mangoes pervading the markets, our thoughts turn to summer. In my case, summer usually entails supervising an undergraduate research project, and this year John and I are supervising one student each for the six-week project.
In the past, I have often forgotten that students are not likely to be familiar with all of the “tools of the trade” for a working combinatorialist, and promise myself that I will write up a list of the basic resources necessary — a student’s toolkit if you like, to which I can point the students on Day One. Given that our students start on Monday, I’ve left it to the last minute (as usual) but on the “better late than never” principle, here goes.
MathSciNet – www.ams.org/mathscinet
Navigating the literature is a fundamental skill for any discipline. Mathematicians, and especially pure mathematicians, are especially fortunate in this regard, largely because almost all of the relevant literature appears in mainstream international mathematical journals, which have been indexed since 1940 by American Mathematical Society (also Zentralblatt). Most of these journals are completely indexed, many of the papers have short descriptive reviews, and the more recent papers have their citations both forward- and backward-linked.
Coverage of mathematical papers in non-mathematical journals (e.g. mathematical physics) is much less complete.
Of course, once you’ve identified the papers and books you want to read, you need to get hold of them. Newer articles are almost always available online, and our library has reasonably good subscriptions. Books and older articles are in the library, where again the collection is reasonable, though not great. Much older books and articles, dating back to the early 1900s are in storage, but can be requested. And any item not in the collection can be requested through inter-library loan.
Google Scholar – scholar.google.com
The ubiquitous Google has turned its search and information management skills to academia and here you can find a mixture of pretty much everything. Often it will turn up a preprint of a paper that the library doesn’t have a subscription for, or citations to your articles from unexpected sources. If you want to add citation counts to a grant application, make sure you use Google Scholar counts not MathSciNet!
As combinatorics is essentially about counting and structures that are discrete and finite, it is an ideal domain for computational exploration, and so an awareness of the available tools is useful. In particular,
Mathematica and/or Maple – general purpose computer algebra systems for symbolic manipulation of mathematical expressions. Extensive, powerful, but need licenses.
GAP – computer algebra system focussed particularly on groups and related structures, with its own language. Free.
Magma – commercial program with similar scope to GAP, but with some important algorithms much faster than GAP.
sage – sagemath.org – somewhat haphazard mash-up of open-source code and numerous pre-existing packages (including GAP), glued together (loosely) with a Python-based interface. Enthusiastic community of developers.
nauty – http://cs.anu.edu.au/~bdm/nauty/ – Brendan McKay’s package of graph generation and isomorphism routines is a must for anyone serious about graph theoretic computation. Very limited user interface, so mostly useful as powerful routines for your own C programs.
And there are numerous other programs for more specialized needs (though many of these can be accessed through Sage if you know the right incantation).
Of course, programming and data collection is relatively easy, lots of fun and gives a satisfying feeling of progress, so it’s easy to lose yourself for weeks or months perfecting your program. Just be careful to remember the old proverb:
A week’s programming sometimes saves a day’s thought!
Three web resources stand out:
Online Encyclopedia of Integer Sequences – oeis.org – your program has just told you that there are 1, 1, 1, 3, 7, 24, 93, 434, 2110, 11002 graphs on 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 vertices with some property you are interested in. Is this a known class of graphs? Is this a known property? Type the sequence into oeis.org and if anyone has previously encountered it and deemed it worth recording, you’ll found out.
MathOverflow – mathoverflow.net – A place to ask research-level questions and have some of the world’s best mathematical minds consider them; at least, provided the question is interesting, carefully phrased and shows that you’ve given it serious thought. Use sparingly unless you frequently come up with fascinating questions.
math.stackexchange – math.stackexchange.com – A place to ask lower-level mathematical questions, not necessarily open research questions, but just where you’re stuck on something, or can’t find a reference, or can’t figure out exactly which parts of a conjecture are still unsolved etc.
Once you’ve read the literature, computed your data, proved your results, its time to write it up and present it at a conference. You’ll need
LaTeX/TeX – No more WYSIWYG word processing from now on.
Mathematics is universally typeset using a typesetting program called LaTeX (or TeX). This was written by the brilliant and notoriously perfectionistic computer scientist and mathematician Don Knuth, and uses sophisticated algorithms for the very precise placement of both mathematical and non-mathematical elements in a document. A complicated mathematical expression can be written quickly in a linear text-based fashion, and then it is parsed by the program and each element placed properly.
(more on TeX later)