Kolkom in Magdeburg

At the weekend, I was at the Kolloquium über Kombinatorik in Magdeburg.

A two-day meeting with four plenary speakers (of whom I was one) and nearly 60 contributed talks in four parallel sessions. So plenty going on. The conference logo featured a 4-dimensional cube (which I used to help explain Cartesian structures in my talk).

I can’t tell you much about the town, since the hotel provided almost no literature. It appears to be a medium-sized town on the river Elbe, which I am told is one of the few rivers in central Europe in its natural state (untamed by weirs). There is a large island in the river as it passes through the town.

I did manage to find time for a walk downstream a few kilometres along the Elbe, and back on the other side. The left bank is mostly decaying industrial plant (old concrete silos or mills, rusting rolling stock, scarcely used docks) and open space given over to coarse grass and brambles. On the other, a long-distance cycleway (the Elberadweg) goes through a beautiful park; under clear sky and lit by low midday sun it looked splendid, many leaves fallen but enough on the trees to make a good show. Near the end of the walk I passed what looked like the world’s biggest helter-skelter; apparently it is the Millennium Tower.

  

I also managed a quick spin round the old part of town, much rebuilt but with several old churches or cloisters (mostly under repair), and one extraordinary modern building called the Green Citadel, somewhat reminiscent of Gaudi in style.

The local hero, after whom the University is named (and whose image is everywhere) is Otto von Guericke. He famously showed that, if two hemispheres are placed together and the air pumped out, then the force holding them together is so great that horses cannot pull them apart. I remember learning about this in Physics at school but didn’t recall the name. A statue of him is in front of the Neues Rathaus, and a statue of his famous experiment stands just outside the hotel where I stayed.

  

But of course the mathematics was what I was there for. I learned a lot; if I told it all here you would lose the thread. But I do want to highlight a lovely plenary talk by Christine Bachoc. The kind of thing which pleases me greatly is seeing the Bessel functions appear in a talk on combinatorics.

She talked about an old and seemingly intractible problem, the chromatic number of the unit-distance graph in the plane. In other words, how many colours do you need to paint every point in the plane so that points at distance 1 get different colours? The problem was posed by Nelson in 1950, and he and Isbell showed that the required number is at least 4 and at most 7. This is still the state of affairs today!

The upper bound comes from a simple colouring. Take a regular hexagon surrounded by six regular hexagons, and colour these hexagons different colours. Now tesselate the plane with this figure. The scale can be chosen so that the diameter of each hexagon is less than 1, but the distance between nearest hexagons of the same colour is greater than 1.

The lower bound is most easily seen by considering the “Moser spindle”. Take two unit equilateral triangles and identify an edge, forming a rhombus. If we colour the vertices with three colours, the terminals (the two vertices not on the identified edge) must get the same colour. Now form a graph consisting of two such rhombi with one pair of terminals identified and the other pair joined by an edge of unit length. Clearly this graph cannot be coloured with three colours; but it has been drawn with edges of unit length.

The next breakthrough on the plane didn’t come until 1981, when Falconer showed that a measurable colouring (one with each colour class measurable) requires five colours. So it is possible that the answer to this question depends on your set-theoretic universe: in a model in which every set is measurable, the answer could be 5, while it could be 4 in a model satisfying the Axiom of Choice. But this is only speculation.

Of course, people turned to higher dimensions. There are upper and lower bounds known in dimension d which are exponential in d, but with different constants (roughly 3 and 1.2).

What Christine and her co-workers have done is to attack the measurable problem with a technique inspired by the Lovász theta-function. A 2-variable function B on R^d is called positive definite if, for any choice of points x₁,…,x_n, the matrix with (i,j) entry B(x_i,x_j) is positive semi-definite. If such a function is also translation-invariant, it can be written as B(x,y)=f(x−y) for some function f, also called positive definite. Now define the density of f to be the limit superior of the average of f over balls centred at the origin. The theta-value of R^d is then the supremum of the density of a positive definite function which takes the value 1 at the origin and 0 on the unit sphere.

Without loss of generality, in this optimization problem we may assume that f is invariant under rotation, and hence the optimization can be reduced to a 1-dimensional problem. (Readers familiar with Bessel functions will not be surprised that this is the point at which they arise.)

The result is an exponential lower bound for measurable colourings, which is better than the known bound for small dimensions, but (unfortunately) is asymptotically worse. However all is not lost, since it is possible to tweak this method by combining it with the graph-theoretic method previously used, to get genuine improvements. It is also nice that graphs associated with some beautiful objects such as the E₈ root system are used to find some of the best bounds.

I will deal more briefly with other talks.

Ingo Schiermeyer gave a plenary talk about rainbow colourings of graphs. One case he considered was rainbow colourings of trees; he and his collaborators have only been able to settle very simple cases such as paths and stars. As he talked, I looked out of the window at the campus and the pleasant park across the road, and decided that Nature had done a pretty good job of solving the rainbow colouring problem for trees.

Jürgen Bierbrauer talked about “Some funny questions concerning semifields”. I thought his main point was more interesting than the questions. The obvious “similarity” relation between semifields is not isomorphism but the broader relation of isotopism; similarly substructures should be defined up to isotopism. You don’t need to know what isotopism is to get the point, which is this: a semifield which is commutative up to isotopism can contain a substructure which is not. (But this can’t happen for associativity.)

Joachim Schröder talked about the array of numbers discovered by Ernst Schröder (no relation, apparently), and used them to define a 2-parameter family of transformations on sequences of integers. But his talk was remarkable for another thing: it was the first time I have seen a mathematical definition of a crystal ball (the set of lattice points in a ball, obviously – and the points on the boundary form a crystal sphere). There are crystal ball transformations which are left inverses of the Schröder transformations.

And finally a nice talk by Lukáš Mach. He was a bit nervous with his supervisor sitting in the audience, but the material is remarkable. Bárány showed that, for any dimension d, there is a constant c_d such that, given any finite set of points in general position in d-dimensional Euclidean space, there is a point (not necessarily in the set) which is contained in a proportion at least c_d of all the d-simplices spanned by the given points. The problem, of course, is to calculate the value of c_d, which is known to be 2/9 for d=2, but not much more is known.

Gromov introduced a topological method, which depended on a function f_d; I will give the definition for d=2, and it easily generalises. But this depends, I am afraid, on your knowing what Seidel switching of graphs is. A graph is called Seidel-minimal if it has the smallest number of edges of any graph in its Seidel switching class (equivalently, given any cut, there are at least as many non-edges as edges crossing it). Any graph has a coboundary, the set of triples containing an odd number of edges of the graph (referred to as a two-graph in the literature); it is an invariant of the switching class. Now f₂(α) is defined to be the limit inferior of the density of the coboundary of a Seidel-minimal graph of density at least α. (Density here means the proportion of edges or triples out of the total possible.) Gromov gave a lower bound for c_d depending on the functions f_e for all e≤d. So better bounds on f₂ could improve lower bounds for c_d for all d>2.

This is exactly what they have done, using flag algebra computations. They have improved the lower bound for c₃ from 0.06332 to 0.07509. (The best upper bound is 0.09375.)