London Combinatorics Colloquia, 2

It’s that time of year again, and while I miss the buttercups in Reading, we had as usual a feast of interesting mathematics and a large and enthusiastic audience.

It was a bit more tightly focussed than I would have liked. We had a lot of references to Szemerédi’s Regularity Lemma; even Ben Green was using a version of the Regularity Lemma for integers, proved by him and Terry Tao, in his talk. (Curiously, Szemerédi was giving a new proof of a known result, avoiding the use of the Regularity Lemma in order to obtain better bounds.) No finite geometry, no enumeration …

I’ll just talk briefly about three of the highlights.

An old result of Erdős asserts that, if A is any finite set of natural numbers of size n, then A contains a sum-free subset of size at least n/3. The proof is simple and beautiful, so here it is. Pick a random real number a from the uniform distribution on [0,1], and let Sa be the set of those n in A for which the fractional part of an is between 1/3 and 2/3. Clearly Sa is sum-free. The average size of Sa is obviously n/3. So there is some choice of a for which the size of Sa is at least n/3.

Ben, with his students Sean Eberhard and Freddie Manners, has proved that the constant 1/3 here is best possible. He gave us a clear outline of the proof. It is necessary to avoid two kinds of “large” sum-free sets. These were very familiar to me from my own work on sum-free sets. The first are periodic sets, such as the set of odd numbers, the set of numbers congruent to 2 or 3 (mod 5), and so on, which occur with positive probability in the choice of a random sum-free set; the second consists of the interval [x, 2x) which comes up (along with the odd numbers) in the Cameron–Erdős conjecture (which was proved by Ben in his PhD thesis).

He described the method of doing this in a couple of simplified cases. To me, it had an adèlic flavour about it; the real completion of the rationals is involved with avoiding the intervals, and the p-adic completions in avoiding the periodic sets.

Gábor Kun, as usual, had a very interesting project to talk about. This is a “finitization” of the concept of amenability. A bit technical, so I won’t attempt a description; but it involved a conjecture of von Neumann, a conjecture of Thomassen, and an algorithmic the Lovász Local Lemma.

The final talk on the second day, the Norman Biggs lecture, was given by Noga Alon, who always gives a good talk, and this was no exception. He was talking about random Cayley graphs, and asking in particular what can be said about the girth or the chromatic number of a random Cayley graph for a given group. He started off by asking: if the order of the group is 10^(10^(10^10)) (I won’t attempt that in HTML), and we choose a generating set of size 10^10, then the chromatic number is with high probability 2 if the group is an elementary abelian 2-group, 3 if it is cyclic of prime order, and bigger than 10 if it is PSL(2,p).

There were lots of technical results, but there was only time to give us a brief taste of the methods used.

Given that these techniques are now available, is it time to revisit Babai’s problem:

Is it true that, if G is a group which is neither abelian nor generalized dicyclic, then a random Cayley graph for G has automorphism group precisely G with high probability?

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.