LSE

We call a graph $H$ \emph{Ramsey-unsaturated} if there is an edge in the

complement of $H$ such that the Ramsey number $r(H)$ of $H$ does not

change upon adding it to $H$. This notion was introduced by Balister,

Lehel and Schelp who also showed that cycles (except for $C_4$) are

Ramsey-unsaturated, and conjectured that, moreover, one may add {\em

any} chord without changing the Ramsey number of the cycle $C_n$, unless

$n$ is even and adding the chord creates an odd cycle.

We prove this conjecture for large cycles by showing a stronger

statement: If a graph $H$ is obtained by adding a linear number of

chords to a cycle $C_n$, then $r(H)=r(C_n)$, as long as the maximum

degree of $H$ is bounded, $H$ is either bipartite (for even $n$) or

almost bipartite (for odd $n$), and $n$ is large.

This motivates us to call cycles \emph{strongly} Ramsey-unsaturated.

Our proof uses the regularity method.

The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to π^2/6.  In dimensions 3 and higher, the "planar" assignment problem is NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do?  In d dimensions, the expected cost is of order at least n^{2-d} and at most ln n times larger, but the upper bound is non-constructive.  For 3 dimensions, we show a heuristic capable of producing a solution within a factor n^ε of the lower bound, for any constant ε, in time of order roughly n^{1/ε}.  In dimensions 4 and higher, the question is wide open: we don't know any reasonable average-case assignment heuristic.

For graphs $L_1,\dots,L_k$, the Ramsey number $R(L_1,\ldots,L_k)$ is the minimum integer $N$ such that for any edge-colouring of the complete graph $K_N$ by $k$ colours there exists a colour $i$ for which the corresponding colour class contains $L_i$ as a subgraph.

In this talk, we shall discuss recent developments in the case when the graphs $L_1,\dots,L_k$ are all cycles and $k\ge2$.

We consider Markovian models on graphs with local dynamics. We show that, under suitable conditions, such Markov chains exhibit both rapid convergence to equilibrium and strong concentration of measure in the stationary distribution. We illustrate our results with applications to some known chains from computer science and statistical mechanics.

Random partial orders and random linear extensions

Several interesting models of random partial orders can be described via a

process that builds the partial order one step at a time, at each point

adding a new maximal element. This process therefore generates a linear

extension of the partial order in tandem with the partial order itself. A

natural condition to demand of such processes is that, if we condition on

the occurrence of some finite partial order after a given number of steps,

then each linear extension of that partial order is equally likely. This

condition is called "order-invariance".

The class of order-invariant processes includes processes generating a

random infinite partial order, as well as those that amount to taking a

random linear extension of a fixed infinite poset.

Our goal is to study order-invariant processes in general. In this talk, I

shall explain some of the problems that need to be resolved, and discuss

some of the combinatorial problems that arise.

(joint work with Malwina Luczak)