Workshop timetable: small changes

Two small changes to the workshop timetable for Wednesday 12 September:

• There will not be a 10-minute introduction; Terence Chan will have an extra 10 minutes.
• Søren Riis will start at 16:00; from 15:30 to 16:00 there will be an additional talk on Synchronization by Peter Cameron.

Maximum overhang problem

A recent talk at the Combinatorics Study Group featured Mikkel Thorup, who was visiting the Centre from AT&T Labs-Research. He spoke about the solution of the 150-year old “Maximum Overhang Problem”, which asks: How far can a stack of identical blocks be made to hang over the edge of a table? The most natural attempt leads to a “harmonic” stack in which the ith block adds an overhang of , so the total overhang has order . This was widely believed to be the correct order of magnitude, to the extent that there was even a physics “proof” purporting to show this.

However, Paterson and Zwick recently showed that in fact an overhang of order can be achieved, which is exponentially larger! As Mikkel said in his talk, the key idea is to realise that a wall is much more effectively counterbalanced than a bridge. This may sound obvious in retrospect, but sometimes a breakthrough just needs a simple idea in an unexpected context. So what is the true order of magnitude? It turns out that is the correct answer – this was proved by Paterson, Peres, Thorup, Winkler and Zwick.

Mikkel left us with a nice open problem, which would reduce the 3d problem to the 2d problem, but is also independently interesting. Is it possible to  create a stable stack of frictionless homogeneous 3d blocks in which there are horizontal forces? For example, you might think that a circle of dominoes can lean against each other in a stable fashion, but apparently it will fall over (very slowly). Mikkel conjectures that no such stack exists. However, if this is true, the proof must use the “rectangular” nature of blocks, as such stacks do exist using triangles.

I’ll add this to the problem page, where anyone interested in thinking about it collaboratively can start a comment thread.

Workshop update

The workshop on information flows and information bottlenecks will take place on Tuesday 11 September and Wednesday 12 September, in room M103, Mathematical Sciences, Queen Mary, University of London. On the first day there will be tutorials; the second day is devoted to research talks.

The draft timetable will be available shortly. We propose to start at 10:00 on Tuesday and 9:30 on Wednesday.

A few slots for contributed talks may be available. If you are interested in giving a talk, please email Søren Riis as soon as possible with a title and abstract of your proposed talk. His email address is soren.riis (at) eecs.qmul.ac.uk .

If you are coming but don’t want to give a talk, it would be helpful to us for planning purposes if you could let us know.

Remember that up-to-date information about the workshop is available on the workshop web page.

Flagmatic

We are very happy to announce that Emil Vaughan’s Flagmatic program is available and is supported by the Centre for Discrete Mathematics.

The program computes exact values of Turán densities of hypergraphs, especially ordinary graphs, directed graphs, and 3-uniform hypergraphs, using Razborov’s flag algebra calculus. The exact values are confirmed by certificates, which enable independent verification of the result. A long list of results which have been obtained using the program is available from the old website, and will be migrated to the new site shortly.

Razborov’s method uses semidefinite programming, and Flagmatic makes use of the semidefinite program solver CSDP. Version 1 of the program is stand-alone; version 2 (available shortly) will be a Sage package.

The Turán density of a set of (hyper)graphs is the limit of edge densities of (hyper)graphs containing no copies of the given (hyper)graphs. The most ancient case is Mantel’s Theorem: the Turán density of a triangle is 1/2, since a graph with no triangle has at most about half as many edges as the complete graph. The Turán density is often but not always rational. The program can also compute induced subgraph densities. It is a tool of great potential value in extremal graph and hypergraph theory.

Information Flows and Information Bottlenecks

Network coding is a relatively new subject, exploiting the fact that the capacity of a network to carry information can be higher than its capacity for regular commodities if the vertices (or edges) of the network have some processing power. The famous “butterfly network”, shown on below, is the simplest example of this paradigm.

In conjunction with EPSRC (grant EP/H016015/1), we are having a two-day workshop on the topic Information Flows and Information Bottlenecks on 11-12 September 2012. The main aim of the workshop is to communicate problems and challenges in multi-user information theory and Network Coding to a wider community including mathematicians. The first day will consist of tutorials to bring participants up to speed in the area; the second will be a conference at which some of the leading researchers will give presentations.

Information about the workshop will be kept here. We will add further details as they become available.

In the meantime, please email Søren Riis or Peter Cameron if you are interested in attending the workshop.

Laplacian eigenvalues and optimality

An LTCC intensive course by R. A. Bailey and Peter J. Cameron
Rockefeller Building, Gower Street, London, 13-14 June 2012

The course brings together concepts from Pure Mathematics (Laplacian
eigenvalues of graphs) and Statistics (optimal design of experiments).

It will be organised as four 2-hour lectures, commencing at 1pm on Wednesday 13 June 2012, and finishing at around 1pm the next day.

Lecture 1: Block designs (RAB)

Block designs in use; complete- and incomplete-block designs; balanced incomplete-block designs; estimation using block designs.

Lecture 2: Graphs and Laplacians (PJC)

The Laplacian matrix of a graph and its spectrum; connections with spanning trees, isoperimetric properties, electrical networks and random walks.

Lecture 3: Designs, graphs and optimality (RAB)

The concurrence and Levi graphs of a block design. Variance and resistance, spanning trees. Definitions of optimality; optimality of BIBDs and group divisible designs.

Lecture 4: More on graphs (PJC)

Optimality and graph properties; variance-balanced designs. The Tutte polynomial; spanning trees, acyclic and totally cyclic orientations of graphs.

To register for the course, email Nisha Jones, office@ltcc.ac.uk
There is a course web page at http://www.maths.qmul.ac.uk/~pjc/LTCC-2012-intensive/

London Combinatorics Colloquia

This week, on Wednesday 16 and Thursday 17 May, there are two one-day combinatorics colloquia. The Wednesday colloquium is at Queen Mary, commencing at 10:30, and will feature talks by Julia Boettcher, Gregory Gutin, Daniel Král, Richard Mycroft, Lutz Warnke, and Günter Ziegler. The Thursday colloquium is at LSE, and the speakers are Rosemary Bailey, Magnus Bordewich, Artur Czumaj, Nikolaos Fountoulakis, János Pach, and Mathias Schacht. See the webpage here for further details, including abstracts of the talks.

The colloquia began when Anthony Hilton, who had run a one-day colloquium at Reading for many years, moved to Queen Mary, and wanted to bring the colloquium with him. At the same time, Norman Biggs retired from LSE, and his colleagues decided to take advantage of the absence of the Reading colloquium to put on an event to mark the occasion. We agreed to cooperate, and the two colloquia have continued since then.

All are very welcome!