South-eastern

Intracoastal Waterway

The South-Eastern International Conference on Combinatorics, Graph Theory and Computing has been going for 44 years. I am not sure of its early history. For some time it alternated between Boca Raton (Florida) and Baton Rouge (Louisiana), but now it has settled down to a permanent home in Boca Raton.

I like being away from home, but don’t like getting there. I seem to have a particular aversion to travelling to the USA. I have had some quite unpleasant experiences at the hands of US immigration officers in the past: transit through the USA is even worse than travelling to a US destination, since you are not their problem. Don’t ask me about my trip to Jamaica in 1996 or to New Zealand in 2004. I am paranoid about those bureaucrats anyway, but when they misuse language such as

  • “visa waiver”: this means you do need a visa, it costs 77 pounds, and we won’t welcome you without it;
  • “we can’t check you in on-line at this time”: this means we can’t check you in on-line ever;

then my paranoia seems justified. Also, of course, Miami was one of the blackspots of the Jamaica trip. This may explain why I left it rather late to make the arrangements.

But as always, when you are there, people are wonderfully hospitable. It was a memorable conference in many ways. Every night there was either a reception (with food provided) or the Conference banquet. The plenary speakers mostly each give two lectures, so they can discuss their subject more widely or in a more leisurely way. I learned a lot.

The South-Eastern has some of the difficulties facing the BCC. Among these are

  • slowly declining attendance (they are trying to address this; they gave every participant an evaluation form, and gently bullied us into filling them in; and
  • a disproportionate amount (in my humble opinion) of graph theory among the contributed talks (they had kept a balance in the invited talks, and had arranged the parallel sessions so that there was usually one which was not straight graph theory in every session).

I talked in the last post about Bruce Sagan’s talk, which for many people was the highlight of the conference. But here are some of the other things that caught my attention.

  • Ron Gould interpolated between the graph properties of being k-connected (which means that, given two k-tuples of distinct vertices, you can connect them up in some order with internally disjoint paths) and k-linked (which means that you can specify the order).
  • Frank Ruskey and Stephen Tanny both talked about iterated recurrence relations (where the formula for F(n) involves F at an argument which itself depends on a value of F at an earlier value).
  • Doug West gave a very nice talk about discharging. I had thought that this was just a tool in the proof of the Four-Colour Theorem; he set out to convince people like me that it is much more than that and can be used in a whole variety of situations. Typically it converts information such as a bound for the average degree of subgraphs of the graph into structural information such as that certain configurations must be present in the graph. Lots of examples.
  • Here is an exercise for you, from a talk by Ralph Grimaldi. A subset of {1,…n} is called extraordinary if its cardinality is equal to its minimal element. The sequence counting extraordinary sets is the Fibonacci sequence. (Exercise: find the most direct bijection to one of the standard types of “Fibonacci objects”.) He had formulae in terms of Fibonacci numbers for some related quantities.
  • Wendy Myrvold and Patrick Fowler talked about current densities in benzenoids (molecules built out of benzene rings) placed in magnetic fields. The problem is to find good heuristics that don’t involve the labour of solving Schrödinger’s equation on a very fine grid.
  • My personal favourite was a talk by John Bate about a very simple idea for improving the performance of graph isomorphism algorithms, in the case where you have a big list of graphs containing many isomorphic pairs. The standard method is to compute a canonical labelling of each graph, and store this: then testing isomorphism is simply testing equality of the canonical labellings. The new idea is to store every labelling you find along the way; if a labelling of one graph coincides with a labelling of another, then the graphs are isomorphic, and you can down tools. The list management can be done so efficiently that there is virtually no overhead; he demonstrated big speed-ups.
  • Anton Betten has just completed the classification of packings of spreads in PG(3,3) (that is, partitions of the lines into spreads), up to isomorphism of the ambient projective space. I wonder if John Bate’s idea might have speeded up the computation!
  • Bruce Sagan’s second talk was also a delight, putting together two topics which obviously should be related, but hadn’t been up to now: permutation statistics (classical: descents, major index, etc.) and permutation patterns (relatively new: counting permutations avoiding specified patterns).
  • The chromatic number of the distance-d graph in Euclidean space (vertices are the points, joined if they are at distance d) is of course classical. Since re-scaling the distance gives an isomorphic graph, it is enough to consider the case d = 1. What if we allow only points with rational coordinates? Now distances actually realised are square roots of rationals, and we can only re-scale by a rational, so we have to allow d to be any square-free positive integer to cover all cases. So there are many different graphs. Are they all non-isomorphic, or only some, or all isomorphic? Nobody knows. But in four dimensions, Pete Johnson has shown that the chromatic number is at most 4, and Matt Noble gave a talk showing that this bound is exact. (He used Lagrange’s four-squares theorem.) So chromatic number does not distinguish!
  • Alexander Soifer talked about the book he is writing, about Paul Erdős’ problems, mentioning four of his favourites: three early problems, including the generalisation of the Happy End Theorem; and the $5000 problem, which asks whether if we have a sequence of natural numbers for which the sum of the reciprocals diverges, it necessarily contains arbitrarily long arithmetic progressions. (Paul Erdős used to speak at 9.30 on Thursdays at the Southeastern Conference, and Sasha’s talk was as close to this point as he could manage.)

But the absolute highlight of the conference was a concert on Tuesday night by Bruce Sagan. In the first half, dressed in traditional costume, he played Swedish folk music and some of his own compositions in the same style, on the fiddle, a Norwegian fiddle with beautiful inlay called a hardingfele, and a Swedish pegged fiddle called a nyckelharpa. (You can see pictures of these instruments on Bruce’s web page here.) In the second half, he played with flautist Maria Provost, who also happened to be the bubbling-over-with-enthusiasm conference organiser; they played a Telemann canonic sonata (the flute and violin play identical music, a couple of bars apart – this more-or-less precludes any key changes, but in the hands of a master can provide wonderful music.)

There was an excursion to the Everglades, with a ride on an air-boat. I don’t usually do conference excursions, but figured I could hardly go to Florida and not see the Everglades! The boat is powered by two large backward-facing propellors, so that when they are coming and going to the dock, it seems as if you are standing on the tarmac at a busy airport. But we got a good feel for the vastness and wildness of the Everglades, and saw two alligators, a turtle, a giant egret, a hawk, cormorants, and various other birds.

Advertisements

About Peter Cameron

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

2 Responses to South-eastern

  1. Pingback: Pinter Play « Log24

  2. The slides of my two conference talks are at http://www.maths.qmul.ac.uk/~pjc/talks/southeastern/

    There are screen and printer versions, illustrating the ever-popular beamer handout.

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