This question is closely related to this post. A set $A=\{a_1<a_2<\dots<a_n\} \subset \mathbb R$ is said to be convex if the consecutive differences are non-decreasing, i.e. if $a_{j+1} - a_j \geq a_j - a_{j-1}$ for all $2 \leq j \leq n-1 $. The set is concave if the consecutive differences are non-increasing. Let us say a set is monotone if it is either convex or concave. Given an arbitrary set $A$ of $n$ real numbers, the post asked about the size of the largest subset of $A$ which is monotone. A very nice answer was given, which implies that any set contains a monotone subset of size approximately $\log_4 n$, and that this bound is tight (a much more precise answer is given in the post, where the problem is posed slightly differently).

My question (together with colleagues here) is the following: given an arbitrary set $A \subset \mathbb R$ with cardinality $n$, what can we say about the number of subset of $A$ which are monotone?

I just have a couple of simple observations as a starting point. One is that any set of 3 or less elements is monotone, and so an arbitrary set of size $n$ must contain at least $$ \binom{n}{3} $$ monotone subsets. On the other hand, for the construction in the linked post, the number of monotone subsets is at most the number of sets with size at most $\log_4 n$. By counting the number of such subsets, I believe this implies that the number of monotone subsets is at most $$n^{\log_4 n},$$ and slightly better estimates of a similar order can be obtained by taking more care.

Finally, let me mention that I was originally interested in this question for strictly monotone sets (i.e. with the definitions of convex and concave involving strict inequalities). I suspect that the answer is similar in both cases.

  • 1
    $\begingroup$ What about the set $A=\{2^k: k=0,1,...,n\}$ in which every subset is monotone? $\endgroup$ Jan 20, 2022 at 6:57
  • 1
    $\begingroup$ I agree that every subset is monotone in this example. However, I am looking for a lower bound for the number of monotone subsets which holds for all $A$. Or conversely, some construction of a set which has relatively few monotone subsets. $\endgroup$ Jan 20, 2022 at 13:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy