One-Day Meeting in Combinatorics 2007

Wednesday, 14 March 2007

The meeting will take place in the Mathematical Institute, Oxford. The schedule is as follows:

Anyone interested is welcome to attend. Some funds may be available to contribute to the expenses of research students who wish to attend the meeting.

Further details can be obtained from Alex Scott.

Support for this event by the London Mathematical Society and the British Combinatorial Committee is gratefully acknowledged.

Programme

Graham Brightwell (LSE)

Order-invariant poset processes

We study random processes generating partially ordered sets. These processes operate by adding one point at a time, with the added element being maximal. A property of interest is "order-invariance": if we condition on the partial order produced after k steps, then the partial order is equally likely to have been generated according to each of its linear extensions. Order-invariant processes have attracted interest from physicists who see them as possible models of the space-time universe. We give some examples and some results.

Philippe Flajolet (INRIA)

Boltzmann sampling and random generation of combinatorial structures

Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient algorithms for the random generation of both labelled and unlabelled objects. The resulting algorithms generate in an unbiased manner discrete configurations that may have nontrivial symmetries, and they do so by means of real-arithmetic computations. Based on analytic-combinatorial methods, it is possible to develop a collection of construction rules for such samplers, which applies to a wide variety of combinatorial classes. Examples include the efficient generation of trees, permutations, graphs, molecules, and languages obeying a variety of constraints.

[Based on joint work with Philippe Duchon, Eric Fusy, Guy Louchard, Carine Pivoteau, and Gilles Schaeffer; articles and slides are available at the author's web site.]

Nati Linial (Jerusalem)

Combinatorial and computational applications of factorization norms

(Joint work with Adi Shraibman.)

Factorization norms of real matrices have been investigated in depth as a chapter in the theory of Banach spaces. We came across this concept in our attempts to develop a complexity theory for sign matrices (in which every entry is 1 or -1). It turns out that these norms can indeed be used in the study of various problems in computational complexity, e.g., (i) Large margin classifiers from the field of machine learning and (ii) Communication complexity. I will illustrate the power of this method by presenting a very simple proof for a theorem of the Littlewood-Offord type which yields a polynomial upper bound on the number of +1/-1 combinations of small norm. If time permits I will mention another application, namely, a theorem about the equivalence between discrepancy and "margin complexity".

Jaroslav Nesetril (Prague)

Dualities for finite structures

The dualities in question are homomorphism dualities, which have recently attracted attention in the context of logic, complexity and TCS. We present various constructions of duals in connections with some of these applications.

Bruce Reed (McGill/INRIA/CNRS)

(1,2)-Colourings of Graphs

A (1,2)-Colouring of a graph is an assignment of integers to its vertices so that adjacent vertices get colourings differing by 2 and vertices at distance 2 get colours differing by 1. We discuss a number of results in this area. We also discuss the related problem of colouring squares of graphs. In particular, we show that every square of a planar graph of maximum degree D has list chromatic number (1+o(1))3D/2.