I meant to finish up the last item with a comment on the relationship between teaching and examining. I have never regarded examining as more than a necessary evil for teachers. So many times, while I was marking the scripts, did I wish I could call the student in and say, “Did you really mean to write that?”, or “Couldn’t you turn on your brain and get a bit further there?” Exam scripts which the students never get to see have almost no teaching value. The only possible value is that occasionally a lower-than-expected mark suggests to students that they don’t have quite the grasp of the subject that they thought they did.
Anyway, exams done, it was on to the two one-day colloquia. As usual, I can’t talk about all the nice stuff we had, so I will just concentrate on a few.
The opening talk of the conference was maybe the best of all. Peter Keevash talked about the existence of designs, a topic I have discussed here before. He made a brave attempt to explain to us the ideas in the proof. I pricked up my ears at one point. Not much of the talk bore much resemblance to traditional combinatorial design theory; but the last step of the proof, where he has an approximation to the required design with some flaw or “hole” which has to be fixed, he does so by means of a trade or null design. This is a concept which has been much studied by design theorists since it was introduced by Richard Wilson, and by Graver and Jurkat. A null design is a function from the set of k-subsets of the point set to the integers such that the sum of the values over all k-sets containing a given t-set is zero. So, thought of as a “multiset” of blocks with both positive and negative multiplicities, it is a t-design with λ = 0. If we separate it as the difference of “positive” and “negative” parts, then if a t-design contains the positive part, we may remove it and “trade” it for the negative part without losing the property of being a t-design.
My other favourite talk from the Queen Mary day was by Ehud Friedgut, on questions related to what was one of my favourite combinatorial problems until he, David Ellis and Haran Pilpel solved it: the Deza–Frankl conjecture. This is an Erdős–Ko–Rado type result for permutations, asserting that, for sufficiently large n (in terms of t), a t-intersecting family of permutations on an n-set has cardinality at most (n−t)!, with equality if and only if the set is a coset of a t-point stabiliser in the symmetric group. Deza and Frankl proved the inequality for t = 1 in the 1970s. Much later, Ku and I characterised equality for t = 1 (there are now several different proofs of this). But Ellis, Friedgut and Pilpel proved the full conjecture, and the first two with Yuval Filmus have pushed on much further to stability and quasi-stability results. Unlike what Ku and I did, they use the right techniques, which are a mixture of representation theory, harmonic analysis, and combinatorics.
At the LSE day, Penny Haxell talked about her work with Lothar Narins and Tibor Szabó characterising the bipartite graphs G for which the topological connectedness of the simplicial complex of independent sets in the line graph of G attains its lower bound ν(G)/2−2, where ν(G) is the matching number of G. If you are yawning already, she did a very fine job of explaining the unlikely relevance of this to some old conjectures about Hall-type conditions for perfect matchings in certain hypergraphs, using attractive tools like Sperner’s colouring lemma.
Pavel Valtr updated us on the status of the Happy End Theorem. This asserts that, given n, a set of sufficiently many points in the plane in general position must contain a convex n. It is so-called because Erdős and Szekeres proved it to answer a question of Esther Klein; she subsequently married George Szekeres, and they had a very long and happy marriage, dying within a few hours of each other quite recently. It is conjectured that 2n−2+1 points suffice; this is now known up to n = 6, but the general upper bound (which Pavel also explained) is close to the square of this. The proof of the lower bound was computational (but with a lot of human cleverness); the proof of the upper bound resembled the theorem that a permutation on n2+1 contains either an increasing or decreasing subsequence of length n+1, which I will be talking about in Leuven next week.
My lecture closed the meeting and was designated the Norman Biggs lecture. You can find the slides on my St Andrews web page.
I am spending the weekend in St Andrews doing the next marking job (fortunately much smaller than the last one!)
Peter Cameron's Blog 