Wednesday, 14 March 2007
The meeting will take place in the Mathematical Institute, Oxford. The schedule is as follows:
|11.00 am||Nati Linial (Jerusalem)|
|Combinatorial and computational applications of factorization norms|
|11.55 am||Graham Brightwell (LSE)|
|Order-invariant poset processes|
|2.15 pm||Jaroslav Nesetril (Prague)|
|Dualities for finite structures|
|3.10 pm||Bruce Reed (McGill/INRIA/CNRS)|
|(1,2)-Colouring of graphs|
|4.30 pm||Philippe Flajolet (INRIA)|
|Boltzmann sampling and random generation of combinatorial structures|
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.
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.
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.]
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".
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.
(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.