Scottish Combinatorics Meeting

SCM logo

At the end of April, I was at the first Scottish Combinatorics Meeting in Glasgow.


The first day was somewhat overcast, but we were safely indoors in the Mathematics department: coffee, lunch and tea were provided in the common room.

As usual, I will concentrate on talks that impressed me in some way. Alex Scott finished the day with a chalk-and-talk on “Colouring graphs without odd holes”. He began by reminding us that the chromatic number χ(G) of a graph G is always at least the clique number cl(G). A beginner might wonder whether there is an inequality in the other direction: is χ bounded above by some function of cl? He pointed out that Mycielski’s theorem definitively refutes this, by constructing triangle-free graphs (that is, cl = 2) with arbitrarily high χ.

Next, one might wonder whether there is a graph (or class of graphs) for which forbidding this graph (or graphs in the class) results in a bound for χ in terms of cl. The result of Erdős that there are graphs with arbitrarily high girth and chromatic number shows that, if a single forbidden graph X is to have this property, then X must be a forest: Gyárfás and Sumner conjectured the converse.

Turning to classes of graphs, the Perfect Graph Theorem of Chudnovsky, Robertson, Seymour and Thomas shows that graphs with no odd holes or odd antiholes have χ = cl. (An odd hole is an induced subgraph which is a cycle of odd length at least 5; an odd antihole is an induced subgraph which is the complement of such a cycle.) If we don’t require equality but merely a bound, can one get by with less? Yes, Alex, with Paul Seymour, has shown that a graph with no odd holes has chromatic number bounded by a function (doubly exponential) of the clique number.

A number of problems remain, including reducing the size of the function, and getting by with just a subset of the odd holes.

Other talks on the first day were by David Manlove, on practical matching problems in healthcare (junior doctor allocation and kidney donor matching), and Sergey Kitaev, on representing graphs by words (the alphabet being the vertex set of the graph, and in the simplest case two vertices are joined if and only if their letters alternate in the word). Sergey gave a short commercial for his new book (with Vadim Lozin) on the subject.

There were also two student talks, by Jason Smith and Fiona Skerman.

After a drink, we went for a good dinner in what we were told was the best tapas restaurant in Glasgow.

The next morning dawned clear and sunny, and a not-too-early start allowed time for a stroll in Kelvin Grove, where the blossom was out.

Kelvin Grove

Back to the conference, and a day of very interesting talks, which I will describe more briefly.

Mark Jerrum started by telling us about the “switch Markov chain” for choosing a random perfect matching of a bipartite graph. This takes two edges ab and cd of the current graph, and replaces them by ac and bd if possible. Of course this required that abdc is a 4-cycle; graphs with long induced cycles are bad news! Indeed, the largest hereditary class of bipartite graphs for which the Markov chain is ergodic is the class of chordal bipartite graphs. However, it is not rapidly mixing, even when restricted to the smaller class of biconvex bipartite graphs. However, Mark and his collaborators have proved rapid mixing for the still smaller class of monotone bipartite graphs, by an ingenious use of the canonical paths method.

Keith Edwards told us about a unified approach to upper bounds for various graph parameters. His method gives rise to the recurrence

dg(d) = (d−2)g(d−1)+g(d−2)+1,

which he solved for us – you are encouraged to try it yourself, it makes a nice exercise!

Mary Cryan told us about her work towards showing that the Hirsch conjecture (stating that if a d-dimensional polytope has n facets, then the 1-skeleton has graph diameter at most nd), which is known to be false in general, actually holds for transportation polytopes. She also gave us the motivation for Hirsch’s original bold conjecture.

A highlight for me was Andrew Treglown’s talk on the “other” Cameron–Erdős conjecture.

In 1990, Erdős and I conjectured that the number of sum-free subsets of {1,…,n} (sets containing no solution to the equation x+y = z) was O(2n/2); more specifically, it is asymptotically c.2n/2, where c takes one of two different values according as n is even or odd. We gave “formulae” for the constants, which are about 4.6 for odd n and 4.0 for even n. The conjecture was proved in the early 2000s by Sasha Sapozhenko and Ben Green.

It is easy to see that there are lower bounds of this form. The set of odd numbers, and the set of numbers between n/2+1 and n, are both sum-free, as are all of their subsets. Erdős and I showed that the conjecture held for sets which either consisted of odd numbers or which had least element not too much less than n/2, and the gap which Sapozhenko and Green filled was to show that the remaining sets are asymptotically fewer in number than these.

In 1999, Erdős and I looked at maximal sum-free sets. The many sets just mentioned lie in just two maximal sets, and we conjectured that the number of maximal sets was much smaller than 2n/2; we constructed examples to show that 2n/4 is a lower bound. Andrew and his collaborators have now proved this in a strong form analogous to the original conjecture: the number of maximal sum-free sets is asymptotically c.2n/4, where c takes four possible values depending on the congruence of n mod 4. However, they do not know what the constants are!

There were also student talks by Stuart Hannah, Grahame Erskine and Ciaran McCreesh.

It was a very successful conference, and everything ran smoothly. All credit to Kitty Meeks and her team for putting on such a nice event. Kitty mentioned in her opening remarks that she hoped it would be the first of a sequence, and several people returned to this theme. Indeed, negotiations about the second Scottish Combinatorics Meeting are already in progress!


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition 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