7
$\begingroup$

Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there is a sequence $I_1,\ldots,I_n$ of elements in ${\cal P}(X)$ such that the following holds:

  • $I_0\subset I_1\subset\cdots \subset I_{n-1}\subset I_n=X$;
  • $f(I_0)\leq f(I_1)\leq\cdots\leq f(I_{n-1})\leq f(I_n)$; and
  • $|I_{i}|=|I_{i-1}|+1$ for all $i\in[1..n]$,

where $\leq$ denotes the standard order on $\mathbb{R}$, and $|I_i|$ denotes the cardinality of $I_i$ (seen as a subset of $X$).

Note that this does not imply that $f$ is monotone, i.e., for elements $I$ and $J$ in ${\cal P}(X)$ such that $I\subset J$, it does not necessarily hold that $f(I)\leq f(J)$. The condition mentioned above just implies that for every element $I$, different from $X$, there exists an element $J$ (of size $|J|=|I|+1$) such that $f(I)\leq f(J)$. One can thus follow a path from $I$ to $X$ (top element) with a non-decreasing $f$-score. This property can be used to locate elements in the lattice that maximize $f$ and satisfy other constraints.

My question is the following: Do such functions have a name? It seems a quite natural condition but haven't been able to find this condition in the literature.

Update: As an example of a class of functions with this property consider a positive function $g$ defined on the elements of $X$, i.e., for each $j\in X$, $g(j)>0$.

Denote by $\bar I$ the complement $X\setminus I$ of a subset $I$ of $X$.

Define $f$ on subsets $I$ of $X$ as follows: $$ f(I):=\frac{1}{|\bar I|}\sum_{j\in \bar I} g(j), $$ i.e., $f$ is just the average of the $g$-values of elements not in $I$. As a special case, when $I=X$, let $f(X):=\max\{ g(j)\mid j\in X\}$.

Such functions are not monotone. For example, let $X=\{a,b,c\}$ and consider $g(a)=5$, $g(b)=3$ and $g(c)=2$. We have that

  • $f(\emptyset)=\frac{5+3+2}{3}\asymp 3.33$
  • $f(\{a\})=\frac{3+2}{2}=2.5$, $f(\{b\})=\frac{5+2}{2}=3.5$ and $f(\{c\})=\frac{5+3}{2}=4$
  • $f(\{a,b\})=2$, $f(\{a,c\})=3$ and $f(\{b,c\})=5$
  • $f(\{a,b,c\})=5$.

As counter example to monotonicity, simply take $\{a\}\subseteq \{a,b\}$ and observe that $f(\{a\})=2.5$, yet $f(\{a,b\})=2$.

Nevertheless, as can be observed from the example, this function satisfies the property described earlier.

More generally, $f(I)\leq f(I\cup\{j\})$ whenever $g(j)\leq f(I)$. One can argue that such $j$ always exists when averages are concerned. Indeed, suppose that $g(j)> f(I)$ for every $j\in \bar I$. Then, $$ f(I)=\frac{1}{|\bar I|}\sum_{j\in \bar I} g(j)> \frac{|\bar I|}{|\bar I|} f(I)= f(I),$$ a contradiction.

Furthermore, let $j^\star\in \bar I$ such that $g(j^\star)\leq f(I)$. Observe that \begin{align*} f(I\cup\{j^\star\})-f(I)&=\frac{1}{|\bar I|-1}\sum_{j\in \overline{I\cup\{j^\star\}}} g(j)-\frac{1}{|\bar I|}\sum_{j\in \bar I} g(j)\\ &=\bigl(\frac{1}{|\bar I|-1}-\frac{1}{|\bar I|}\bigr)\sum_{j\in \overline{I\cup \{j^\star\}}} g(j) - \frac{1}{|\bar I|} g(j^\star)\\ &=\bigl(\frac{|\bar I|-|\bar I|+1}{(|\bar I|-1)|\bar I|}\bigr)\sum_{j\in \overline{I\cup \{j^\star\}}} g(j) - \frac{1}{|\bar I|} g(j^\star)\\ &=\frac{1}{|\bar I|}\bigl( f(I\cup\{j^\star\}) - g(j^\star)\bigr).\tag{1} \end{align*} It now suffices to observe that $g(j^\star)\leq f(I)$ implies that \begin{align*} g(j^\star) &\leq \frac{1}{|\bar I|}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j) + \frac{1}{|\bar I|} g(j^\star)\\ g(j^\star)\bigl(1-\frac{1}{|\bar I|}\bigr)&\leq \frac{1}{|\bar I|}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\ g(j^\star)\bigl(\frac{|\bar I|-1}{|\bar I|}\bigr)&\leq \frac{1}{|\bar I|}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\ g(j^\star)&\leq \frac{1}{|\bar I|-1}\sum_{j\in \overline{I\cup \{j^\star\}}} g(j)\\ g(j^\star)&\leq f(I\cup\{j^\star\}).\tag{2} \end{align*} Combining (1) and (2) results in $f(I\cup\{j^\star\})\geq f(I)$, as desired.

Remark Instead of averaging over elements in $\bar I$, one could also average over elements in $I$ but then the property needs to be formulate wrt to the lattice $({\cal P}(X),\supseteq)$.

$\endgroup$
  • 1
    $\begingroup$ I don't see why this is such a natural condition. Do you have examples of natural functions that aren't monotone that satisfy this property? $\endgroup$ – Peter Shor Sep 24 '17 at 15:13
  • $\begingroup$ Thanks for you question. This condition pops up when considering averaging functions. I have updated the question with a general description of a class of functions satisfying this property, yet which are not necessarily monotone (also shown by example). $\endgroup$ – sirolf Sep 24 '17 at 19:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.