Article contents
The length of an s-increasing sequence of r-tuples
Published online by Cambridge University Press: 08 January 2021
Abstract
We prove a number of results related to a problem of Po-Shen Loh [9], which is equivalent to a problem in Ramsey theory. Let a = (a1, a2, a3) and b = (b1, b2, b3) be two triples of integers. Define a to be 2-less than b if ai < bi for at least two values of i, and define a sequence a1, …, am of triples to be 2-increasing if ar is 2-less than as whenever r < s. Loh asks how long a 2-increasing sequence can be if all the triples take values in {1, 2, …, n}, and gives a log* improvement over the trivial upper bound of n2 by using the triangle removal lemma. In the other direction, a simple construction gives a lower bound of n3/2. We look at this problem and a collection of generalizations, improving some of the known bounds, pointing out connections to other well-known problems in extremal combinatorics, and asking a number of further questions.
MSC classification
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2021. Published by Cambridge University Press
References
- 3
- Cited by