Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T12:18:48.145Z Has data issue: false hasContentIssue false
  • English
  • Français

The length of an s-increasing sequence of r-tuples

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  08 January 2021

W. T. Gowers  and
J. Long
W. T. Gowers
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, Wilberforce Road, CambridgeCB3 0WB, UK
J. Long*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, Wilberforce Road, CambridgeCB3 0WB, UK
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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

Primary: 05D99: None of the above, but in this section
Secondary: 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 5 , September 2021 , pp. 686 - 721
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aronov, B., Dujmović, V., Morin, P., Ooms, A., Fernando, L. and da Silveira, S. X. (2019) More Turán-type theorems for triangles in convex point sets. Electron. J. Combin. 26 P1.810.37236/7224CrossRefGoogle Scholar
Behrend, F. (1946) On sets of integers which contain no three terms in arithmetic progression. Proc. Nat. Acad. Sci. 32 331–332.10.1073/pnas.32.12.331CrossRefGoogle Scholar
Bollobás, B. (1986) Combinatorics; Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press.Google Scholar
Brown, W. G., Erdős, P. and Sós, V. T. (1973) Some extremal problems on r-graphs. In New Directions in the Theory of Graphs, pp. 55–63. Academic Press.Google Scholar
Diaz-Lopez, A. (2016) Po-Shen Loh interview. Notices Amer. Math. Soc. Sept. 2016, 905–908.CrossRefGoogle Scholar
Fox, J. (2011) A new proof of the graph removal lemma. Ann. of Math. 174 561–579.10.4007/annals.2011.174.1.17CrossRefGoogle Scholar
Füredi, Z. and Hajnal, P. (1992) Davenport–Schinzel theory of matrices. Discrete Math. 103 233–251.CrossRefGoogle Scholar
Gowers, W. T. Bipartite graphs of approximate rank one. https://www.dpmms.cam.ac.uk/˜wtg10/approxrankone3.pdf Google Scholar
Loh, P. (2015) Directed paths: from Ramsey to Ruzsa and Szemerédi. To appear in Combin. Probab. Comput. arXiv:1505.07312Google Scholar
Marcus, A. and Klazar, M. (2006) Extensions of the linear bound in the Füredi–Hajnal conjecture. Adv. Appl. Math. 38 258–266.Google Scholar
Marcus, A. and Tardos, G. (2004) Excluded permutation matrices and the Stanley–Wilf conjecture. J. Combin. Theory Ser. A 107 153–160.CrossRefGoogle Scholar
Ruzsa, I. Z. (1993) Solving a linear equation in a set of integers. Acta Arithmetica 65 259–282.CrossRefGoogle Scholar
Ruzsa, I. and Szemerédi, E. (1978) Triple systems with no six points carrying three triangles. Coll. Math. Soc. J. Bolyai 18 939–945.Google Scholar
Sárközy, G. N. and Selkow, S. (2004) An extension of the Ruzsa–Szemerédi theorem. Combinatorica 25 77–84.10.1007/s00493-005-0006-6CrossRefGoogle Scholar
Stein, S. (1967) Factoring by subsets. Pacific J. Math. 22 523–541.CrossRefGoogle Scholar
Stein, S. (1984) Combinatorial packing of ℝn by certain error spheres. IEEE Trans. Inform. Theory 30 364–368.10.1109/TIT.1984.1056880CrossRefGoogle Scholar
Stein, S. (1995) Packing tripods. Math. Intelligencer 17 37–39.Google Scholar
Stein, S. and Szabó, S. (1994) Algebra and Tiling: Homomorphisms in the Service of Geometry, Vol. 25 of The Carus Mathematical Monographs. The Mathematical Association of America.10.5948/UPO9781614440246CrossRefGoogle Scholar
Tidor, J., Wang, V. Y. and Yang, B. (2016) 1-color-avoiding paths, special tournaments, and incidence geometry. arXiv:1608.04153Google Scholar
Tiskin, A. (2007) Packing tripods: narrowing the density gap. Discrete Math. 307 1973–1981.CrossRefGoogle Scholar
Wagner, A. Z. (2017) Large subgraphs in rainbow-triangle free colorings. J. Graph Theory 86 141–148.CrossRefGoogle Scholar