Please note that this site concerns the historical Centre for Discrete Mathematics at Queen Mary, which is now closed. Please see the Combinatorics Group page for current information about Combinatorics at Queen Mary, University of London (QMUL), and the Combinatorics Study Group page for information about the weekly seminar at QMUL.
On Friday, 10 October, Stephen Tate (Warwick) will talk in the Combinatorics Study Group on “Combinatorics in Statistical Mechanics”, a talk which will be of wider interest.
Further details can be found here.
The new director of the Centre for Discrete Mathematics is Professor David Arrowsmith.
We thank Peter Keevash for all he has done for the Centre, and wish David well in the job.
Speaker: Peter Harremoës
Time and Place:
4pm, 16 January 2013, in Maths Room 203 at 4pm and is followed by a reception at 5pm in the Maths Foyer.
Title: Occam’s Razor in Action – information as link between statistics and probability theory
Abstract: Probability theory and statistics are normally considered as two distinct but related fields of mathematics. In this talk I will demonstrate how ideas from information theory may be used to glue all three fields together.
In the first part of the talk I will discuss some basic but important information theoretic concepts and results like codes, Kraft’s inequality, entropy, information divergence, and rate distortion theory. In the second half of the talk I will give a short overview of the newest results on how all the basic theorems of probability theory can be reformulated so that the results become stronger and so that the proofs become simpler and so that applications become more directly applicable in statistics.
The talk will include the presentation of a number of open problems.
We are pleased to announce the Workshop
Combinatorial Probability and Statistical Mechanics
to be held on 21 – 23 February 2013 in Queen Mary, University of London.
The workshop is the first in the new series of meetings co-organised by the School of Mathematical Sciences at QMUL and the Mathematics Institute of the University of Warwick.
The aim of the workshop is to bring together researchers who study various aspects and applications of random combinatorial structures, in particular from the viewpoints of stochastic processes, asymptotic enumeration, analytic combinatorics and the analysis of algorithms.
The website for the workshop is here.
If you are coming to the workshop, it would be helpful if you email D.S.Stark@qmul.ac.uk, so that we have some idea of the number of attendees.
Please note that the Queen Mary Algorithms Day will be the day before the workshop; you may wish to attend both.
Note 22/10/2012: This talk has been cancelled because of ill-health.
Van Vu (Yale) will speak in the Pure Mathematics Colloquium at Queen Mary on Monday, 22 October 2012, at 4:00pm in room M103 (Mathematical Sciences building). Please note the change of time! The title is Random matrices: Law of the determinant.
We will discuss the obvious question raised in the title. The problem has been considered for quite a while, with partial results from Turan, Komlos, Dixon, Girko, Delannay-Le Caer, Dembo and many others.
We will give a brief survey and then focus on recent results of Tao, Nguyen, and the speaker which give answers for quite general setting. If time allows, we will also discuss a few open questions.
The Queen Mary Algorithms Day will take place on 20 February 2013. A list of speakers can be found on the webpage.
We will be posting slides of as many as possible of the talks at the workshop on Information Flows and Information Bottlenecks last week.
The first couple are already up, and others will appear soon. They are linked from the workshop programme page.
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.
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.