Large sets of pairwise comparable triples
Two elements $s, s'$ of $[N]^3$ are comparable if $s - s'$ has two strictly positive coordinates or two strictly negative ones. The question below is perhaps the most basic of those considered by Gowers and Long. Green suggests that part of the difficulty is that the bound sought lies below the range where a spectral (Delsarte-type) bound on the independence number could work.
Problem. Let $S \subset [N]^3$ be a set any two distinct elements of which are comparable. Is $|S| \le N^{2 - \delta}$ for some $\delta > 0$?
Source: W. T. Gowers and J. Long, The length of an s-increasing sequence of r-tuples, Combin. Probab. Comput. 30 (2021), Problem 1.9, motivated by a question of P.-S. Loh. Listed as Problem 88 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- CO — Combinatorics
- Keywords
- comparability, Delsarte bound, extremal combinatorics, independent sets, tripod packing
- Literature checked
- Oct. 26, 2026 by clemens-admin
References
@article{gowers2021long,
author = {Gowers, W. T. and Long, J.},
title = {The length of an $s$-increasing sequence of $r$-tuples},
journal = {Combinatorics, Probability and Computing},
volume = {30},
number = {5},
pages = {686--721},
year = {2021},
doi = {10.1017/S0963548320000371},
eprint = {1609.08688},
archivePrefix = {arXiv}
}
@misc{loh2015,
author = {Loh, Po-Shen},
title = {Directed paths: from {R}amsey to {R}uzsa and {S}zemer{\'e}di},
year = {2015},
eprint = {1505.07312},
archivePrefix = {arXiv}
}
@article{tiskin2007,
author = {Tiskin, Alexander},
title = {Packing tripods: narrowing the density gap},
journal = {Discrete Mathematics},
volume = {307},
number = {16},
pages = {1973--1981},
year = {2007},
doi = {10.1016/j.disc.2004.12.028}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 88; version of January 2026, most recent update December 2025},
year = {2026}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00958, "Large sets of pairwise comparable triples", clopen.solutions.