ACCMCC, Days 2 and 3

Tuesday started with an impressive plenary talk from Nevena Francetić on “group divisible coverings” (these are, roughly, like covering arrays but with some blanks. The range of methods she used was impressive: the Rödl nibble, an extension of Baranyai’s theorem, and so forth. It picked up themes from Daniel Horsley’s talk the day before, which I unaccountably failed to mention.

Ian Wanless talked about extending the notion of parity for Latin squares to sets of mutually orthogonal Latin squares. He mentioned in passing the Alon–Tarsi conjecture, but didn’t have time to do it justice.

Charles Semple’s talk started off by explaining why biologists have moved on from discussing phylogenetic trees to more general networks: recombination can occur between different species. The networks have, apart from a root and leaves (the latter being the current species), nodes which “fan out” and others which “fan in”. This gives us lots of new counting problems, which have relevance to the mathematical biologists.

After tea, Adam Mammoliti gave us a lovely survey of the Erdős–Ko–Rado theorem, extensions and generalisations. Unfortunately, his talk clashed with one by Paul Leopardi on bent functions which I would also have liked to hear.

Wednesday had just one talk, a plenary by Saad El-Zanati, before the conference excursion to St Helena Island which I have already described. He is at a university with no PhD program, but he works wonders with undergraduates and even high school students, on decomposing regular graphs into isomorphic trees or forests. Ringel conjectured that an n-edge gree decomposes the complete graph on 2n+1 vertices; someone (I forgot to make a note of who it was) made the same conjecture for the complete bipartite graph on n+n vertices; Graham and Häggkvist extended these conjectures to any 2n-regular graph and any n-regular bipartite graph. Saad and his colleagues have extended these to decompositions into forests. Plenty of special cases here for undergraduates and high school students to tackle and make a contribution!

So here is a very simple special case. A 2n-regular graph can be decomposed into n-edge stars. How? The graph has even valency, so has an Eulerian orientation; this has n edges leaving and n entering every vertex. Now a vertex and its n out-neighbours form a star, and every edge lies in just one such star.


About Peter Cameron

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

Leave a Reply

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

You are commenting using your 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