Abstract

We will consider the following deceptively simple question, formulated recently by Po Shen Loh who connected it to an open problem in Ramsey Theory. Define the ‘2-less than’ relation on the set of triples of integers by saying that a triple x is 2-less than a triple y if x is less than y in at least two coordinates. What is the maximal length of a sequence of triples taking values in {1,...,n} which is totally ordered by the ‘2-less than’ relation?

In his paper, Loh uses the triangle removal lemma to improve on the trivial upper bound of n² by a factor of log*(n), and conjectures that the truth should be of order n^3/2. The gap between these bounds has proved to be surprisingly resistant. We shall discuss joint work with Tim Gowers, giving some developments towards this conjecture and a wide array of natural extensions of the problem. Many of these extensions remain open.