ACCMCC, Day 1

I’m at the University of Queensland this week for the 39th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing.

It is slightly scary to think that it is nearly 52 years since I came to the University as a student. (Indeed, I joined the UQ Athletics Club in January, although term didn’t start until March.)

The conference was opened by Gordon Royle who talked about graph homomorphisms and cores. A graph homomorphism is a map on the vertex set which takes edges to edges: the effect on non-edges is not specified. There is a quasiorder on finite graphs, the homomorphism order, where one graph precedes another if there is a homomorphism from the first to the second. Two graphs are homomorphism equivalent if there are homomorphisms in both directions between them. A graph of minimal order in its homomorphism equivalence class is a core. Thus, a graph is a core if all its endomorphisms (homomorphisms to itself) are automorphisms.

A homomorphism to a complete graph is the same as a proper vertex colouring. If you have read various posts of mine about synchronization, you will know that graphs whose core is complete play an important role in that theory, and Gordon has had a hand in that; but his talk was about two other aspects of this large subject. I will just describe one.

A graph X is strongly regular if it is regular and the number of common neighbours of two vertices v and w depends only on whether or not v and w are joined. A strongly regular graph is non-trivial if it and its complement are connected. (The trivial strongly regular graphs are disjoint unions of complete graphs and complete multipartite graphs.). Also, a graph X is a pseudocore if all its endomorphisms are either automorphisms or proper colourings. (If there are endomorphisms which are not automorphisms, then the core of X is complete.) David Roberson has announced a proof of the theorem that every non-trivial strongly regular graph is a pseudocore; Gordon gave us a sketch of the proof.

Among the contributed talks was one by David Wood on expanders. He was concerned with bipartite expanders. He and his co-authors have shown that these graphs can have very small values for certain layout parameters such as book numbers and queue numbers; indeed they have best possible results.

A graph is hypohamiltonian if it is not Hamiltonian but every vertex-deleted subgraph is. This sounds like a nightmare to check computationally; but Brendan McKay and his collaborators have found that a cubic planar hypohamiltonian graph of girth 5 has at least 76 vertices, and determined all 76-vertex examples.

My talk was first after lunch, and the slides are in the usual place. Ian Wanless, introducing me, recalled the Peter Cameron who was a Presbyterian minister who moved from Scotland to Australia and was excommunicated for the heresy of supporting the ordination of women. I moved in the opposite direction, and committed the heresy of talking about topology at a combinatorics conference; but combinatorialists are broad-minded, and nobody has drummed me out of the profession yet!

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events and tagged , , , . Bookmark the permalink.

One Response to ACCMCC, Day 1

  1. Gordon Royle has a post on SymOmega (https://symomega.wordpress.com/2015/12/07/minion-and-hamiltonicity/) on using Minion (http://constraintmodelling.org/minion/) to check that Brendan’s three 76 vertex graphs are non-hamiltonian.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s