Cubic vertex-transitive graphs

A graph is called vertex-transitive if for every pair of vertices there is an automorphism of the graph that maps the first to the second. I discussed such graphs and other symmetry classes of graphs in two earlier posts. (I see that I had promised a third in that series but that has yet to eventuate.)

A cubic graph is a graph for which every vertex has valency three, that is, every vertex has exactly three neighbours.  Cubic graphs have been extensively investigated with many graph properties first investigated in the cubic case. For example,  s-arc-transitive graphs were first investigated in the cubic case in the seminal work of William Tutte in two papers in 1947 and 1959.

An arc of a graph is an ordered pair of adjacent vertices and we say that a graph is called arc-transitive if the automorphism group of the graph acts transitively on the set of arcs. The most famous example is the Petersen graph. Arc-transitive graphs are also called symmetric graphs.  Ronald Foster began compiling a list of symmetric cubic graphs in 1932 and this is now known as the Foster census. Marston Conder and Peter Dobcsanyi  extended the census so that it was complete for graphs with at most 768 vertices and Marston has extended it further to include all graphs with at most 2048 vertices. The graphs are available on Marston’s website.

For vertex-transitive cubic graphs there is data collated by Gordon and Brendan McKay that is complete for all graphs with up to 94 vertices as well as all graphs with n vertices for many values of n at most 258. Recently, Primoz Potocnik, Pablo Spiga and Gabriel Verret have comprehensively smashed this upper bound by compiling a list of all vertex-transitive cubic graphs with at most 1280 vertices. This continues the excellent work in graph symmetry that they have been doing in recent years. They have set up a webpage containing the data and a preprint is on the arxiv explaining their methods. I am sure it will be a valuable resource for investigating graphs and testing conjectures. They have already checked that apart from the four known exceptions they each have a Hamiltonian cycle.

As part of their work they have also compiled a list of all arc-transitive graphs of valency 4 on at most 640 vertices. That is also available on their webpage. Primoz is also undertaking a project with Steve Wilson aiming to list all edge-transitive valency 4 graphs on up to 512 vertices. The data so far is available here.

Appreciating the Hamming [7,4,3]-code

You might be familiar with Richard Ehrenborg’s beautiful game where your friend chooses a number from 0 to 15, and you proceed to show in turn seven cards, asking which side of the card the number is on, and then placing each card down carefully on a base card. Each card has a funny shape, with squares poking out at the edges.

The Base Card

Is your number on this side?

Your friend can lie at most once, and so once the cards have been placed down, the number on the base card which is covered at most once by a protruding square, is the number your friend has chosen. What is so cool about this trick is that you have an excellent information rate — seven questions, sixteen numbers to choose from and one lie. What makes this tick is a perfect code, which was known earlier by Golay but is attributed to Hamming (as he could publish his findings and Golay could not). (See Chapter 1, Section 6 of Thomas Thompson’s book). This code has code length 7, dimension 4 and minimum distance 3. So it can correct single errors and detect two errors. However, in demonstrating the glory of the Hamming code to the uninitiated, I felt something was missing; a crappier precursor.

I’ve come up with a simpler game based on a [6,3,3]-code which has a (poor)  information rate of  0.5, and is certainly not perfect (the Hamming bound here is 64/7). The generator matrix for this linear code is

Your friend chooses a number from 0 to 7, and you proceed to present six cards in turn, asking which side of the card the number is on, and then placing each card down carefully on a base card. It still works like the Hamming code, but makes the Hamming code look so much better in comparison. The cards are attached.

The Six Cards

Chromatic Roots – the multiplicity of 2?

My favourite problems in the theory of chromatic roots have a tendency to crop up frequently and I often find myself frantically searching through old emails or (worse) trying to dig up old notes.

One of these problems is the following question:

Is there a combinatorial interpretation for the multiplicity of 2 as a root of the chromatic polynomial of a graph?

(For general background, see my previous post on chromatic roots and the accompanying PDF.)

The specific background to this question is that there are well-understood combinatorial interpretations for the multiplicity of 0 as a chromatic root — it is simply the number of connected components of the graph. If a graph is connected (and hence 0 is a simple chromatic root), then the multiplicity of 1 as a chromatic root is the number of blocks (maximal 2-connected components) of the graph.  So we would like a statement that says “if a graph is 2-connected (and so both 0 and 1 are simple chromatic roots) then the multiplicity of 2 as a chromatic root is the number of ….”. Unfortunately it all grinds to a halt here because,  to my knowledge,  nobody knows how to complete that sentence.

No 16-clue Sudoku puzzles… finally proved!

I received an interesting email today from Gary McGuire containing a paper proving the result that I had long suspected — namely that there is no 16-clue Sudoku puzzle. (See this earlier blog post for some background.)

I have only skimmed the paper so far, but the basic method is clear enough – to examine each of the possible completed grids in turn and exhaustively search the grid to demonstrate that no 16-clue subgrid is uniquely completable. One way of doing this that does not involve actually solving every possible 16-clue subpuzzle is to observe that certain subsets of the cells must necessarily be “hit” by one of the 16 clues or they could simply be rearranged in the final solution. Finding so many subsets of this type that no collection of 16 cells can hit them all is then a (computer) proof that this particular grid contains no 16-clue uniquely completable subgrid.

I’ll add some more details when I have time to read the paper more carefully.

In the meantime, I won’t link to the paper yet, as while it has been uploaded to arxiv, it  won’t appear for a couple of days, presumably due to the holiday break.

Congratulations to Gary and his team!

Alan Robert Woods

John, Michael and I went to a funeral on Friday – this was for our colleague Alan Woods who died totally unexpectedly last week.

We were not especially close to Alan, who was a logician and number theorist, but he came to all of the Groups, Combinatorics and Computation seminars, often asking questions, and in fact he gave the seminar just a few weeks ago. He came along to the after-seminar lunches and the various Maths department functions etc. but I don’t think we ever spoke much about his life outside mathematics.

Perhaps sadly (or perhaps inevitably), I learned much more about him at the funeral than I ever knew before. The service was very moving and his sister and two children gave really lovely speeches describing his other lives as a devoted father, nature-lover, bush-walker, free thinker and record-breaking amateur radio enthusiast.  He was only 58 which makes him, if not exactly a contemporary of mine, at least not a million miles off, which is a rather sobering thought. The funeral was at Karrakatta cemetery on a spectacular Perth day of brilliant light and totally blue skies, but not yet with the dusty dryness and searing heat of full summer. His plot was under a shady tree and, as the celebrant said,  you couldn’t imagine a better time or place to lay to rest a dedicated nature lover.

Mathematically, his name is attached to at least one concept – the Erdős–Woods numbers are the integers numbers such that there is a closed interval of integers with the property that every integer in the interval has a factor in common with either or . According to OEIS A059756, the smallest Erdős–Woods number is with associated interval .

35ACCMCC at Monash

All three of us have just returned from the 35th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, which was held last week at Monash.  Peter Cameron’s latest blog post (of the same title of this one) gives his recollections of the week.

Michael’s slides

I was also at the Victorian Algebra conference last week. Here are my slides. I spoke about my recent work on imprimitive rank three groups with Alice Devillers, Cai Heng Li, Geoffery Pearce and Cheryl Praeger that appeared recently. It was discussed in more detail in an earlier post.

Slides of my Victorian Algebra presentation

It was indeed an honour and a privilege to be the plenary speaker at the 29th Victorian Algebra Conference, which was held at my old stamping ground … La Trobe University (Melbourne, Australia). I spoke on a brief introduction to algebraic combinatorics and its applications to problems outside the usual realm of graph theory. I went to a lot of effort to make Tikz pictures for this talk, so I hope it went down OK.

Sildes of my talk

A depressing ritual

Suffered through the School’s Examiners Meeting yesterday, in what is becoming a rather depressing bi-annual ritual.

In this meeting, we all get together to look at the marks that are going to be sent to Faculty for ratification by the Faculty’s Board of Examiners. As is frequently the case, the Faculty’s contentious “scaling policy” played more of a role in the final marks for many units than any effort or achievement on the part of the class. For my second-year unit, the required scaling was so extreme that, while I have frequently been  uncomfortable in the past with this requirement, this year I feel for the first time that the practice has crossed the rubicon from “marking on the curve” to outright academic fraud.

Some ways I try to be efficient

There are various technological ways I try to cut down the number of mouse clicks or complicated processes in order to remain organised and efficient, and I’m open to know what else I can do. Here is a short list of things I recommend others use, some of which are particular to MAC users:

1. I often use BibDesk to organise my bibtexing. The coolest feature is that it can import directly from MathSciNet; a little browser window opens up, MathSciNet is there, I enter the info I know about the reference, then some papers are listed which match my query. I click on import and it is put in my library. I can then hit CTRL-K to make a cite-key, and then I simply drag the reference into my LaTeX file (in TeXShop).
2. Papers by Mekentosj is very impressive, and I believe it has won some awards for its design. It organises all the pdfs of papers on my desktop, which I can match with mathscinet bibliographic data. The best feature is that I can search all of my papers for various things quite easily. For instance, just like iTunes, I can create a smart album of all papers which are on “generalised quadrangles” (or “generalized quadrangles”). I’ve put the library of papers in my Dropbox so that I can use it on all of my machines, wherever I am in the world!
3. TeXShop is quite a good LaTeX typesetter. I can right-click on the PDF and it will show me in the LaTeX file where that part of the file is. I also find it easy to compile PDFLaTeX and BibTeX quickly using key-strokes (Command + L and Command + B).
4. Cool unix-terminal commands such as “sed” for replacing strings in a file and good old “!” for re-executing a command.
5. iCal has made me more organised, and I have it synchronised with my email server so that I can change my calendar on any machine. The best feature is that I can right click on a date and time in an email, and it will automatically import an appointment into iCal. Most of the time, I don’t need to edit the title or meeting place (it works this out from the body of the email!).

That’s all I can think of for now. More will be added to this list as they come to mind (or I’m reminded by someone else).