| Title | Pages | Summary | Download |
| Bipartite graphs of approximate rank 1 | 39 | This paper deals with a generalization of the notion of quasirandomness from approximately regular bipartite graphs to ones where the vertices can have different degrees. We also prove a weakening of Szemer\'edi's regularity lemma, for which this generalized quasirandomness supplies a counting lemma. Finally, we combine the two results to give a new proof of a theorem of Green and Konyagin. | dvi, pdf |
| Quasirandom Groups | 29 | It follows quite easily from the classification of finite Abelian groups that any Abelian group of order n contains a product-free subset of size at least n/3: that is, a subset X such that if x and y belong to X then xy does not belong to X. Babai and Sós asked whether this result could be extended to non-Abelian groups if one was allowed to replace the constant 1/3 by a smaller positive constant. In this paper the answer is shown to be no. It is shown that the existence of a large product-free subset is equivalent to the existence of a non-trivial low-dimensional representation. Since there are families of groups that do not have low-dimensional representations, our result shows that there are families of groups that do not have large product-free subsets. We call such families quasirandom for reasons that are explained in the paper, and we prove a number of results about their properties. The paper ends with some open problems. | dvi, pdf |
| Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs | 50 | This paper gives a new proof of a result of Frankl and Rödl. An earlier result of Ruzsa and Szemerédi states that from any graph with few triangles one can remove a small number of edges to make it triangle-free, a result that turns out to have Szemerédi's theorem for progressions of length 3 as an easy consequence. Frankl and Rödl generalized this from graphs to 3-uniform hypergraphs, thereby reproving Szemerédi's theorem for progressions of length 4. The approach of this paper is simpler than theirs: most of the 50 pages consist of a survey of background material and known facts that motivate the proofs we give in the final few sections. Indeed, one of the main aims of the paper is to try to present a truly readable introduction to some of the complexities of hypergraphs. | dvi,pdf |
| Hypergraph Regularity and the Multidimensional Szemerédi Theorem | 42 | This paper proves the generalization of the results of the previous paper to k-uniform hypergraphs for arbitrary k. Two notable consequences are Szemerédi's theorem and its multidimensional version (which was originally proved by Furstenberg and Katznelson using ergodic theory methods and not known by any other argument). Results similar to the main results of this paper, with the same consequences, were obtained independently by Nagle, Rödl and Schacht. This is not quite a final draft: I expect to polish it a bit and have a final version here by mid-April. Note added 12/4: I have now polished it quite a lot. I may do a little bit more, but it is in near-final form. | dvi,pdf |
| A new proof of Szemerédi's theorem | 129 | Szemerédi's theorem asserts that for every delta > 0 and every k there exists an N such that every subset A of the set {1,2,...,N} of cardinality at least delta N contains an arithmetic progression of length k. This statement was reproved by Furstenberg a few years later, but neither proof gives reasonable estimates for N. (Furstenberg's gives no estimate at all, and the bound from Szemerédi's is too enormous to be worth working out explicitly.) This proof generalizes Roth's method for progressions of length three, using exponential sums and giving an estimate for N which is doubly exponential in 1/delta and quintuply exponential in k. This paper has now appeared in GAFA, and you can get the journal version by following links from MathSciNet. | dvi |
| A new proof of Szemerédi's theorem for arithmetic progressions of length four | 23 | This paper deals with the first special case of Szemerédi's theorem that does not easily yield to a proof using exponential sums. It has the advantage of being much shorter than the paper on the general result, but actually the material of this paper is covered separately, and in some ways better, in the bigger paper. | ps |
| Lower bounds of tower type for Szemerédi's uniformity lemma | 16 | Szemerédi's uniformity lemma states that, given any reasonably dense graph, there is a partition of its vertices such that the bipartite graphs formed by the pairs of cells are almost all `quasirandom', in a precise and useful sense. This result has numerous applications, but its applicability is limited by the fact that Szemerédi's bound for the number of cells (as a function of the amount that the graph should resemble one built out of random pieces) is very large. In this paper, it is shown that this was in fact necessary. It is unusual for a tower-type function to appear in quite as natural a combinatorial context as this. | ps |
| An infinite Ramsey theorem and some Banach-space dichotomies | 39 | The infinite Ramsey theorem of the title is similar in spirit to combinatorial results of Nash-Williams, Silver, Galvin and Prikry, Mathias and Ellentuck. Where they consider sets of subsets of N, this paper looks at sets of sequences in a Banach space. In both cases, subject to topological (or, equivalently, descriptive) restrictions, one can find a substructure where the collection of sets or sequences has a particularly good structure. In the Banach-space case, this can be used to prove interesting dichotomies - that is, statements that every Banach space has a subspace with one of two highly incompatible properties. Combined with a result of Komorowski and Tomczak-Jaegermann, one of the results of this paper can be used to show that separable Hilbert space is the only Banach space isomorphic to all its infinite-dimensional subspaces, solving a problem of Banach. | dvi |
| The unconditional basic sequence problem. (With B. Maurey) | 29 | This paper constructs the first known example of an infinite-dimensional Banach space containing no unconditional basic sequence. In fact, the best way to understand the space turns out to be through its linear operators: every operator on the space is a strictly singular (that is, small in a certain useful sense) perturbation of a multiple of the identity. As an easy consequence, the space is not isomorphic to any proper subspace of itself, which answers a question of Banach. | ps | Banach spaces with small spaces of operators. (With B. Maurey) | 29 | Here we extend the results of the previous paper, giving a fairly general method for constructing spaces with given algebras of operators. Although these algebras have to satisfy strong constraints, the method has several applications. For example, it gave the first known prime Banach space other than lp or c0. (In fact, the space is isomorphic to a proper subspace if and only if the subspace is finite-codimensional.) It also gave a space isomorphic to its two-codimensional subspaces but not to its hyperplanes, and a space isomorphic to its cube but not to its square. The last two spaces are counterexamples to the Schroeder-Bernstein problem for Banach spaces (which asks whether X and Y must be isomorphic if X is isomorphic to a complemented subspace of Y and vice-versa). Warning: this is not quite the final version of the paper, which I am still searching for in the mess that is my filespace. However, the journal version is available online, linked from MathSciNet. | ps |
| Title | Pages | Summary | Download |
| The two cultures of mathematics | 17 | This article was for an IMU volume entitled Mathematics: Frontiers and Perspectives. It is basically a defence of combinatorics against some of the criticisms commonly made of it. Judging from some of the reaction to the article, it is perhaps worth saying that when I quote the views of `theoreticians', it is because I agree with them. My aim is not to dispute their criteria for what constitutes worthwhile mathematics, but rather to show that combinatorics meets these criteria (suitably, and I hope reasonably, interpreted). | ps |
| Rough structure and classification | 40 | This was my attempt to do the `Hilbert thing', at a conference in Tel Aviv in 1999 entitled Visions in Mathematics . I start with some speculations about computers - I think that before too long they will have a much more serious role to play in helping mathematicians to find proofs, or even finding proofs for themselves. I then make some general remarks about what I call `rough structure' and `rough classification' in combinatorics, stating several problems that I find interesting. In a final section, I give a more miscellaneous list of (mostly well known) open problems that I would love to see solved. Unlike Hilbert, I do not intend my list of problems to have a major influence on the course of mathematics in the next century - it is just a list of problems that I like. | ps |
| The importance of mathematics | 1 hour | This is a streaming video of a lecture given at a meeting of the Clay Mathematics Institute. As its title suggests, it is an attempt to justify pure mathematics. The lecture was aimed at the general public and assumes very little mathematical background. I also have a pdf version, but unfortunately without the illustrations, which are quite important. | video , pdf |
| Does mathematics need a philosophy? | N/A | A talk given to the new Cambridge University Society for the Philosophy of Mathematics and the Mathematical Sciences. | html |
| Some unsolved problems in additive/combinatorial number theory | 18 | A survey of the slightly hard to classify part of number theory of which Szemerédi's theorem is a very good example, focusing mainly on unsolved problems. | dvi |
| Recent results in the theory of infinite-dimensional Banach spaces | 10 | A survey of results in Banach-space theory that were recent in 1994. This paper provides an introduction to the Banach-space results in some of the more detailed research papers listed above. | dvi |