We call a family of permutations A in Sn 'intersecting' if any two permutations in A agree in at least one position. Deza and Frankl observed that an intersecting family of permutations has size at most (n-1)!; Cameron and Ku proved that equality is attained only by families of the form {σ in Sn: σ(i)=j} for i, j in [n].
We will sketch a proof of the following `stability' result: an intersecting family of permutations which has size at least (1-1/e + o(1))(n-1)! must be contained in {σ in Sn: σ(i)=j} for some i,j in [n]. This proves a conjecture of Cameron and Ku.
In order to tackle this we first use some representation theory and an eigenvalue argument to prove a conjecture of Leader concerning cross-intersecting families of permutations: if n >= 4 and A,B is a pair of cross-intersecting families in Sn, then |A||B|
Cover a plane with curves, one curve through each point
in each direction. How can you tell whether these curves are
the geodesics of some metric?
This problem gives rise to a certain closed system of partial
differential equations and hence to obstructions to finding such a
metric. It has been an open problem for at least 80 years. Surprisingly
it is harder in two dimensions than in higher dimensions. I shall present
a solution obtained jointly with Robert Bryant and Mike Eastwood.
We consider one-dimensional Brownian motion conditioned (in a suitable
sense) to have a local time at every point and at every moment bounded by some fixed constant. Our main result shows that a phenomenon of entropic repulsion occurs: that is, this process is ballistic and has an asymptotic velocity approximately 4.5860... as high as required by the conditioning (the exact value of this constant involves the first zero of a Bessel function). I will also describe other conditionings of Brownian motion in which this principle of entropic repulsion manifests itself.
Joint work with Itai Benjamini.
Let d be a fixed natural number. There is a theorem, due to Chvátal, Rodl,
Szemerédi and Trotter (CRST), saying that the Ramsey number of any graph G
with maximum degree d and n vertices is at most c(d)n, that is it grows
linearly with the size of n. The original proof of this theorem uses the
regularity lemma and the resulting dependence of c on d is of tower-type.
This bound has been improved over the years to the stage where we are now
grappling with proving the correct dependency, believed to be an
exponential in d. Our first main result is a proof that this is indeed the
case if we assume additionally that G is bipartite, that is, for a
bipartite graph G with n vertices and maximum degree d, we have r(G)
Let d be a fixed natural number. There is a theorem, due to Chvátal, Rodl,
Szemerédi and Trotter (CRST), saying that the Ramsey number of any graph G
with maximum degree d and n vertices is at most c(d)n, that is it grows
linearly with the size of n. The original proof of this theorem uses the
regularity lemma and the resulting dependence of c on d is of tower-type.
This bound has been improved over the years to the stage where we are now
grappling with proving the correct dependency, believed to be an
exponential in d. Our first main result is a proof that this is indeed the
case if we assume additionally that G is bipartite, that is, for a
bipartite graph G with n vertices and maximum degree d, we have r(G)