BCC, day 3

Further to my comment about non-communication betweem group theory and combinatorics yesterday, the table labelled “Maths” at breakfast this morning was for group theorists, while combinatorialists were somewhere else …

The format of this BCC is a little different from usual. We finish at lunchtime on Friday instead of continuing in the afternoon. This means that an extra slot has to be found for one of the nine plenary speakers, who might otherwise have spoken on Friday afternoon. The solution was to have no contributed talks on Wednesday morning, but instead to have two plenaries and then an early lunch before the outing to Warwick castle.

The two talks this morning went together remarkably well. First, Nik Ruškuc (my boss for the next 23 days) talked about well quasi-orders in combinatorics, starting with Higman’s theorem. He showed us some brief extracts from Higman’s paper, including the statement that in the author’s opinion it was the range of applications rather than the depth of the proofs that made the topic interesting. Nik took us through various kinds of structure (words, permutations, trees, graphs, posets) and various notions of inclusion (subword/subgraph, induced subgraph, minor), describing when the WQO property is true and a sketch of what it buys you if it does hold. For a small example, words over a finite alphabet are well-quasi-ordered by the (not necessarily contiguous) subword relation; a consequence is that any ideal is a regular language (so that there is a finite automaton which recognises it) and hence the generating function for the ideal is a rational function. It would be very interesting if anything like this could be said for other instances of WQO.

He was followed by Sergey Norin, talking about a very specific example of a WQO class, graphs ordered by the minor relation (this, of course, is the content of the famous theorem of Robertson and Seymour). For this class, the results are more detailed, and there is much new material. Much effort has gone into Hadwiger’s conjecture, according to which a graph not having the complete graph on t+1 vertices as a minor can be coloured with t colours. It is known that a proper minor-closed class of graphs has the property that the number of edges of a graph in the class is bounded by a linear function of the number of vertices; so the graph has an invariant d, the “density”, which is the lim sup of the ratio of edges to vertices over the class. The set of densities of proper minor-closed classes is closed, well-ordered (and hence nowhere dense), and is contained in the set of rational numbers (the last fact a very recent theorem of Kapadia and Norin). On this last result, he posed a fascinating question: can the rationality of densities be proved in Peano arithmetic? (This is non-trivial if, as seems reasonable to me, the Robertson–Seymour theorem cannot.)

I skipped the excursion, and spent several hours without completely getting up to date with my email (I fell very far behind when my computer was down); then we had a committee meeting, which finished in time to have a drink with the group theorists before bedtime.


About Peter Cameron

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

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