I asked this question a few days ago on MO, but I haven't received an answer. So I thought I would ask here. I have also added a relaxed version of the question here.

Let $F$ be a set-valued, finite-valued map from a set $X$ to subsets of $X$. Consider the following property: $|F(x)| \geq |F(y)|$ for all $x,y$ such that $y \in F(x)$. I have defined this property myself in a specific context but I am not sure what name to give it. I would like to know if there is a standard name for this property or similar property in set-valued analysis, combinatorics or elsewhere. Any suggestions for names would also be appreciated.

As a relaxation, suppose $X$ is given by the disjoint union, $X = \bigcup_{i \in \mathbb{N}} X_i$ and assume that $F$ maps elements of $X_i$ to subsets of $X_{i+1}$ for any $i$. In this case one can think of elements of $X$ as nodes of a tree-like graph, where a parent node $x$ is joined to nodes $y \in F(x)$. There are no edges between nodes belonging to the same partition $X_i$. But a child could have multiple parents, so this graph is not necessarily a tree. The property $F$ here says that every child of a node has at most as many children as the node. Any suggestions for names here would also be helpful.

At first this property appears to be a kind of monotonicity, but I would like to resort to the name "monotone" only if I can't find something more suitable.

  • $\begingroup$ I would consider F as a directed graph instead of a function, but I do not have any suggestion for the name of the property. $\endgroup$ Commented Aug 25, 2012 at 1:31
  • $\begingroup$ Have you looked up the notions of tree-width and clique-width? Not sure if they are exactly what you want, but they may help. $\endgroup$
    – Vijay D
    Commented Aug 27, 2012 at 3:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.