Critical Probabilities in Percolation
Speaker: Béla Bollobás, Cambridge University and Memphis University, UK & USA
In the talk I shall report on some results on critical probabilities I have obtained with Oliver Riordan (Oxford), Paul Balister (Memphis), József Balogh (San Diego) and Robert Morris (Rio de Janeiro). The models I shall consider include percolation on random Voronoi tessellation in the plane and in high dimensions, bootstrap percolation on grids in all dimensions, and bootstrap percolation on the discrete cube.
Retired, 65 Not Out
Speaker: Adrian Bondy, University Lyon 1 and University Paris 6, France
An evocation of the development of combinatorics in France, with particular emphasis on the roles played by the many recently retired colleagues to whom this conference is dedicated.
Sparse quasi-random graphs
Speaker: Fan Chung, University of California, San Diego, USA
It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasi-random, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Zn.
We will discuss some extension of these ideas to sparse graphs and sequences.
Speaker: Vašek Chvátal, Canada Research Chair in Combinatorial Optimization, Concordia University, Canada
The ternary relation of betweenness shows up in different settings. I will talk about three of them.
The first is ordered geometry; there, primitive notions of points and lines are linked by the relation of incidence and by axioms of betweenness; two classic theorems here are the Sylvester-Gallai theorem and the de Bruijn-Erd?s theorem. I conjectured in 1998 and Xiaomin Chen proved in 2003 that the Sylvester-Gallai theorem generalizes to metric spaces when lines in these spaces are defined right; together, we conjectured that the de Bruijn-Erd?s theorem also generalizes to metric spaces when lines in these spaces are defined right (with “right” having a different sense in each of the two instances); the two of us and Ehsan Chiniforooshan have partial results on this conjecture.
The second of the three settings is abstract convexity; there, families of sets called “convex” obey certain axioms. Such finite structures are called convex geometries when they have the Minkowski-Krein-Milman property: every set is the convex hull of its extreme points. Two classical examples of convex geometries come from shelling of partially ordered sets and simplicial shelling of triangulated graphs. In 2008 I characterized, by a five-point condition, a class of betweennesses generating a class of convex geometries that subsumes the two examples. Laurent Beaudou, Ehsan Chiniforooshan, and I have additional results on such betweennesses.
The last setting lies between physics and philosophy: in his effort to develop a causal theory of time, Hans Reichenbach introduced the notion of causal betweenness, which is a ternary relation defined on events in probability spaces. In 2009, Baoyindureng Wu and I characterized, by easily verifiable properties, abstract ternary relations isomorphic to Reichenbach’s causal betweenness.
Open questions on well-quasi-orders
Speaker: Neil Robertson, Ohio State University, USA
A well-quasi-order is a reflexive and transitive relation where all descending chains and antichains are finite. There have been extensive advances in well-quasi-order theory for graphs and matroids over the past thirty years. Still, the area has many interesting concrete unsolved problems and the natural progression towards testing the observation of Crispin Nash-Willliams that all natural well-quasi-orders are better-quasi-orders has only a few highlights, in works of Igor Kriz and Robin Thomas, now nearly 20 years old. This lecture will describe what seem to me to be the central questions and describe work by two of my former students, Yared Nigussie and Christian Altomare, respectively, towards transforming graph minor WQO into BQO, and formulating a conjecture which includes Richard Laver’s theorem about scattered total orders and the graph minor WQO theorem.
Forbidden subgraphs and factors in graphs
Speaker: Akira Saito, Nihon University, Japan
Sumner proved that a connected claw-free graph of even order has a 1-factor. But why did he choose a claw as a forbidden subgraph? The answer is clear : If we forbid one graph to force the existence of a 1-factor in a connected graph of even order, we have to forbid a claw, or its induced subgraph. And this is the case even if we allow finitely many exceptions. Starting from this observation, we discuss the relationship between forbidden subgraphs and the existence of factors. We first consider a 1-factor in a connected graph and give an overview of the history of the research, which has recently been completed by Ota and Sueiro. We then discuss the same problem for graphs of higher connectivity. We will also explore the problem on 2-factors.
Bounding stable sets in graphs and codes
Speaker: Alexander Schrijver, CWI and University of Amsterdam, Netherlands
Finding a maximum-size stable set in a graph is a hard problem. A special case is finding maximum-size error-correcting codes, where the graphs have even exponential size. On the other hand, Delsarte and Lovasz gave good upper bounds, using linear and semidefinite programming.
We extend these methods with tools from representation theory and C*-algebra, yielding sharper code bounds. For instance, it gives A(20,8)=256, that is, the maximum number of 0,1 words of length 20 any two of which have Hamming distance at least 8, is equal to 256. In other words, the quadruply shortened Golay code is optimum.
In the talk we give an introduction to these methods and results.
Joint work with Dion Gijswijt and Hans Mittelmann.
Embedding Sparse Graphs into Dense Graphs
Speaker: Endre Szemerédi, Hungarian Academy of Sciences, Hungary
We are going to present a method for embedding sparse graph. We will consider the Posa-Seymour conjecture, the El-Zahar conjecture and we will give a tight degree bounds for the existence of a spanning tree in a dense graph. Briefly we will mention a partial result for the Gyarfas-Lehel conjecture.