Now that I am back in Perth from the 33rd Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, I can give a summary report of the conference.
Overall the conference was a great success. On the mathematical side there were many interesting talks with all the other plenary talks being good. A brief summary is as follows:
The second plenary talk on Monday was by Barbara Maenhaut from The University of Queensland who spoke on `Graph decompositions and factorisations’. This surveyed recent results in this area. One was the conjecture that every complete graph of even order has a factorisation into 1-factors such that the union of any two is a Hamiltonian cycle. Such factorisations are called perfect 1-factorisations.
Both plenary talks on Tuesday mentioned the work of our own Gordon Royle. The first was by Adrian Bondy from the Institut Camille Jordan, who spoke on ‘Aspects of Reconstruction’. The original reconstruction conjecture is that every graph on at least three vertices can be recognised from the set of subgraphs formed from it by deleting a vertex. Adrian spoke about recent work on a variation of the problem where for each vertex you complement the sets of incident edges. It is conjectured that any graph on at least 4 vertices in switching reconstuctible. Gordon got a mention, as along with Mark Ellingham, he has proved that this is true for triangle free graphs. There is also a version in the digraph case where for each vertex v you take the graph formed by switching the direction of the arcs incident with v.
The second was by Luis Goddyn from Simon Fraser University who spoke on `Excluded minors for bicirculant matroids’. A circular matroid of a graph has elements the edges of the graph and the minimal dependent sets are the cycles. A bicircular matroid for a graph has minimal dependent sets the connected subgraphs consisting of two cycles. They currently have a list of 27 excluded minors and believe this is complete but have a small number of cases of possible ranks and number of elements which need to be checked. This used Gordon’s catalogue with Dillon Mayhew for small matroids. The talk was also notable for Luis’s interesting dress sense.
Jaroslav Nesetril from Charles University spoke on `Existence vs Counting (on large and sparse structures).’ The main idea was to take a family of graphs and then form a new family of graphs consisting of all graphs in the original family plus those obtained by either contracting an edge or deleting a vertex. This process can be repeated. If you eventually obtain all graphs the original class is call somewhere dense while if you don”t it is called nowhere dense. For example, the set of planar graphs is nowhere dense while the set of all graphs of valency at most 3 is somewhere dense.
The final plenary talk was by Edy Baskoro from the Institut Teknologi Bandung, Indonesia, who spoke `On the existence of almost moore digraphs.’ The maximal number of vertices of a graph of diameter d and valency k is at most . A graph meeting this bound is called a Moore graph (see this earlier post), while a graph whose number of vertices is 1 less than this bound is called an almost Moore graph. Similar questions can be asked in the directed case.
On the social side of things, the conference excursion was a trip to the Tamburlaine winery where we did some wine tasting and had a tour of the winery. We then went to another winery for lunch where we had the best conference excursion lunch I have ever had. The conference dinner was at Customs House where we were well fed and there was even a band. The best student talk prize was shared by Joanne Hall from RMIT and Beata Faller from the University of Canterbury.