London Combinatorics Colloquia

This week saw the two linked London Combinatorics Colloquia, at Queen Mary and the London School of Economics.

Not so long ago, a one-day meeting in Reading organised by Anthony Hilton was a fixture of the calendar. When Anthony came to QM, he brought the colloquium with him; the same year, Norman Biggs came to the end of full-time empolyment at LSE, and his colleagues took advantage of the absence of the Reading meeting to put on a one-day colloquium for him. Fortunately we were able to cooperate, and the double event has continued in the same format since then.

This year saw a fine collection of talks. János Pach observed that four of the twelve talks mentioned Szemerédi, fitting in the year he won the Abel prize, but perhaps indicating a predominance of a certain sort of combinatorics …

I will describe briefly my favourite talks.

Günter Ziegler gave a talk which began with a conjecture from two Kolkata mathematicians, Nandakumar and Ramana Rao, in 2006, and ended with a theorem by a mathematician from Madras (as it then was), Ram, in 1909. The problem states:

Given a convex polygon in the plane and a positive integer n, is it possible to divide the polygon into n convex pieces any two of which have the same area and the same perimeter?

The theorem asserts:

The greatest common divisor of the entries in the nth row of Pascal’s triangle (omitting the initial and final 1) is 1 if n is not a prime power, and p if n is a power of the prime p.

By a long chain of argument, using optimal transport (going back to Monge in 1751), weighted Voronoi diagrams, and equivariant obstruction theory, he and Pavle Blagojević use the theorem to prove that the dissection is possible if n is a prime power.

János Pach gave a talk entitled “Szemerédi strikes back”. It was an excellently-paced survey and a proof with a beautiful trick. First, briefly, the background. Van der Waerden’s Theorem asserts that, given c and l, there is a number n such that, if the first n positive integers are coloured with c colours, there is a monochromatic arithmetic progression of length l. Erdős and Rényi asked for a density version, which was proved by Szemerédi by combinatorial means, and two years later by Furstenberg using ergodic theory. I have told the story here.

A few years ago, Furstenberg and Weiss proved an analogous theorem for binary trees. Let Tn be the binary tree with n levels. A replica of Td in Tn is a copy of Td with a property that the two children of a node in the small tree (which are descendants of the corresponding node in the big one) are descended from different children of this node, and that a level in the small tree is contained in a level in the big one; it is arithmetic if the levels of the big tree on which vertices of the small tree occur form an arithmetic progression. Furstenberg and Weiss showed that, given c and l, there exists n such that, if the vertices of Tn are coloured with c colours, there is a monochromatic arithmetic replica of Tl. They alsos showed a “density version” of this partition result.

Pach observed that, if the word “arithmetic” is omitted from the theorem, then it can be proved by a simple combinatorial argument with an explicit bound. Now if we want an arithmetic replica, we find a replica of Tm, where m is the number in van der Waerden’s theorem; then look at the set of levels used, and find an arithmetic progression of size l, giving an arithmetic replica. This argument also does the density version, replacing van der Waerden’s theorem by Szemerédi’s.

With all the emphasis on Szemerédi’s regularity lemma, perhaps it is time to revisit a dream of mine: that the regularity lemma can be used to prove non-existence results for certain kinds of strongly regular graphs. I will just discuss one special case here, concerning triangle-free strongly regular graphs. Such a graph has v vertices and valency k, no triangles, and two non-adjacent vertices have μ common neighbours. Only finitely many are known. There is one particular (extremal) subfamily of “negative Latin square” type, where v = s2(s+3)2, k = s(s2+3s+1), and μ = s(s+1). For s = 1, we have the Clebsch graph, and for s = 2, the Higman–Sims (or Mesner) graph. No others are known. For s = 3, the non-existence has been shown computationally. This is the limit of our knowledge.

The regularity lemma says that any sufficiently large graph can be partitioned into (many large) pieces with the property that, for almost all pairs of pieces, the edges between those pieces A and B behave like a random bipartite graph: that is, the edge density between subsets X and Y of A and B is close to the edge density between A and B.
For dense graphs, this implies that given any three pieces, the number of triangles with one vertex in each piece is approximately what you would expect in a random tripartite graph. The argument fails for sparse graphs, however, since the approximation is sufficiently rough that zero is a possible number of triangles.

Various authors have worked on sparse versions of the regularity lemma. As far as I know, none of these will do the job I want; I would like to be proved wrong!

A putative strongly regular graph of the type considered, with n vertices, is sparse but not too sparse, with edge density about n−1/4. Also, the fact that it is strongly regular prevents it from having dense “hotspots” (a hypothesis in some versions of the sparse regularity lemma). Is it possible to prove that a graph looking like this must necessarily contain a triangle?

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.

4 Responses to London Combinatorics Colloquia

  1. Pete says:

    Is the 2 in the formula for k meant to be there?

  2. Alexander Gavrilyuk has sent me a reprint of a paper he published with A. A. Makhnev, in Doklady Akademii Nauk (2005), proving the non-existence of the 324-vertex triangle-free strongly regular graph without the use of a computer.

  3. mercadee says:

    One of the first mathematicians to realize this possibility was Carl Friedrich Gauss , who then carefully measured out large right triangles as part of his geographical surveys in order to check the theorem. He found no counterexamples to the theorem within his measurement precision.

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