In the late 1960s, when I was born as a mathematician, I worked on finite permutation groups, on the edge of finite geometry and the combinatorics of very regular structures. I was dimly aware that there was a completely different kind of combinatorics, in which the probabilistic method was one of the main tools, but at the time these two areas seemed to have little to say to each other.
Perhaps the first crack in the wall came with the work of Lászlo Babai in the late 1970s. Permutation groups had struggled for a century to find good bounds for the order of a primitive groups of degree n not containing the symmetric and alternating group. Wielandt found an exponential bound for groups which are not 2-transitive; this was extended and improved by Praeger and Saxl to give a bound 4n for all primitive groups. Then Babai, using ideas from the combinatorics of coherent configurations and the probabilistic method, produced a bound for the orders of primitive but not 2-transitive groups which is much better for large n, namely n4√n log n. This is best possible apart from the logarithm in the exponent.
Babai just managed to save this problem from the Classification of Finite Simple Groups, which bulldozes away some very attractive problems and results, and enables us to prove much stronger bounds with known exceptions.
One of my papers with Laci also contains a novel application of the probabilistic method. There are a number of results of the form “every [finite] group is the automorphism group of a [finite] X”; for example, Frucht in the case where X=graph (or cubic graph). Sometimes there is a simple reason why such a result cannot hold. The automorphism group of a tournament must have odd order; but every finite group of odd order is the automorphism group of a finite tournament.
The result that Laci and I proved concerns automorphism groups of switching classes of tournaments. Such a group must have a double cover with a unique involution; so first we need to understand such groups. A cohomological argument due to George Glauberman, described here, shows that the groups are precisely those whose Sylow 2-subgroups are cyclic or dihedral. Then an application of the probabilistic method shows that, given such a group, we can construct a switching class of tournaments for which it is the full automorphism group. The novelty is the use of the probabilistic method rather than explicit construction.
The person who did most to bring together the “Hungarian” probabilistic combinatorics with finite geometry was another Hungarian, Tamas Szőnyi, who combined a deep knowledge of finite and algebraic geometry with a thorough understanding of random techniques. The British Combinatorial Conference always has to struggle a bit to find speakers who can interest researchers in the most diverse areas of combinatorics. Tamas fitted the bill very well, when he spoke at the conference at Queen Mary and Westfield College (as we then were) in 1997.
These things are on my mind now because of a lovely talk last Friday by Jeroen Schillewaert, on small maximal partial ovoids in generalized quadrangles. Briefly, then, the definitions:
- a generalized quadrangle is a point-line geometry, with at least three points on a line and at least three lines through a point, having the properties that two points lie on at most one line, and if a point p is not on a line l then it is collinear with a unique point of l.
- Such a geometry has a constant number (say s+1) of points on a line and a constant number (say t+1) of lines through a point; the pair (s,t) is called the order of the GQ.
- A partial ovoid is a set of points, no two collinear; it is maximal if no point can be added without violating this condition.
It is known that √s ≤ t ≤ s2. There are obvious upper and lower bounds for the size of a maximal partial ovoid, of size about s and st respectively. In the case where t = s2, the best explicit construction of a small maximal partial ovoid produces one of size about s2/2.
Jeroen Schillewaert and his co-author Jacques Verstraëte have given a randomized construction procedure that succeeds, asymptotically almost surely, in finding a maximal partial ovoid of size s times a power of log s, a dramatic improvement and not far from the trivial lower bound. There is not too much clever finite geometry (this has the advantage that it works for any GQ with these parameters, not just a classical GQ), but some fairly sophisticated probability theory. They hope to extend the result to wider classes of GQs.
And it was a very good talk, using blackboard and chalk.