Submit progress

on Upper bound on the maximal length of a 2-increasing sequence of triples

The statement

For each positive integer $n$ , let $[n]$ denote the set $\{1, 2, \ldots, n\}$ . For triples $a = (a_1, a_2, a_3)$ and $b = (b_1, b_2, b_3)$ of integers, we say that $a$ is $2$ -less than $b$ , denoted $a <_2 b$ , if $a_i < b_i$ for at least two coordinates $i \in \{1, 2, 3\}$ . A sequence of triples is called $2$ -increasing if every pair of distinct elements in the sequence satisfies the $2$ -less relation in the order they appear. Let $F(n)$ denote the maximal length of a $2$ -increasing sequence of triples with each coordinate belonging to $[n]$ . Prove that for every natural number $n$ ,

F(n) \leq n^{3/2}.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.