# How to characterize the convex hull/closure operator

From Wikipedia

Every subset $$A$$ of a vector space $$S$$ over the real numbers, or, more generally, some ordered field, is contained within a smallest convex set (called the convex hull of $$A$$), namely the intersection of all convex sets containing $$A$$. The convex-hull operator $$Conv()$$ has the characteristic properties of a hull operator:

• extensive $$S ⊆ Conv(S)$$,
• non-decreasing $$S ⊆ T$$ implies that $$Conv(S) ⊆ Conv(T)$$, and
• idempotent $$Conv(Conv(S)) = Conv(S)$$.

I was wondering what else properties of the convex hull/closure operator has, so that

• we can define a hull/closure operator with such properties to be a convex hull/closure operator, and
• we can define the class of all convex subsets for a given ground set, by for example claiming a subset is convex if and only if it equals its convex hull?

Thanks and regards!

• $Conv(T)=T$ for any affine subspace $T$, and $Conv(S\setminus T)= S$ unless $S=T$. – Olivier Bégassat Jan 2 '13 at 18:01
• @OlivierBégassat: Thanks! I was wondering if these two additional properties can define a closure operator to be a convex closure operator? References are also appreciated. – Tim Jan 2 '13 at 18:05
• Also, $$Conv(X)=\bigcup_{F\subset X,~F\text{ finite}}Conv(F)$$ – Olivier Bégassat Jan 2 '13 at 18:19
• @OlivierBégassat: Thanks! Did you come up with the three properties yourself? Do you know if they can characterize a convex closure operation? – Tim Jan 2 '13 at 18:24
• Fyi > in geometry 4 closure operators are widely considered: convex, affine, cone, and linear hulls (spans). – alancalvitti Jan 3 '13 at 3:33

There is a theorem in van de Vel's Theory of Convex Structures that may be of interest. First define a closure system. Suppose that $X$ is a set and $\mathcal{C}$ is a collection of subsets of $X$. Then $\langle X, \mathcal{C} \rangle$ is a closure system if and only if for all $\mathcal{A} \subseteq \mathcal{C}$ we have $\cap \mathcal{A} \in \mathcal{C}$. Sometimes people require $\varnothing \in \mathcal{C}$. I can't remember if van de Vel does. For $A \subseteq X$ define $$\mathsf{cl}(A) = \cap \{ C \in \mathcal{C} \colon A \subseteq C \} .$$ In any event the convex subsets of a real vector space satisfy these properties.

Theorem Suppose that $\langle X, \mathcal{C} \rangle$ is a closure system. Then the following statements are equivalent:

1. For all $A \subseteq X$ we have $\mathsf{cl}(A) = \cup \{ \mathsf{cl}(F) \colon F \text{ is a finite subset of } A \}$.
2. For all $\mathcal{D}$ which are collections of subsets of $X$ that are directed by inclusion (see below for a definition of directed by inclusion) we have $\mathsf{cl}(\cup \mathcal{D}) = \cup \{ \mathsf{cl}(D) \colon D \in \mathcal{D} \}$.
3. For all $\mathcal{T}$ which are collections of subsets of $X$ that are totally ordered by inclusion (see below for a definition of totally ordered by inclusion) we have $\mathsf{cl}(\cup \mathcal{T}) = \cup \{ \mathsf{cl}(T) \colon T \in \mathcal{T} \}$.

A collection $\mathcal{D}$ of subsets is directed by inclusion if and only if for all $D_{0}, D_{1} \in \mathcal{D}$ there is a $D \in \mathcal{D}$ with $D_{0}, D_{1} \subseteq D$.

A collection of subsets is totally ordered by inclusion if and only if for all $T_{0}, T_{1} \in \mathcal{T}$ we have $T_{0} \subseteq T_{1}$ or $T_{1} \subseteq T_{0}$.

Edit

This is in response to Tim's comment.

Suppose that $X$ is a set and $\mathcal{F}$ is the collection of finite subsets of $X$. Suppose also that $f \colon \mathcal{F} \rightarrow \mathcal{P}(X)$ where $\mathcal{P}(X)$ is the collection of all subsets of $X$. For each $n \in \mathbb{N}$ define \begin{align} g_{n} \colon \mathcal{P}(X) &\rightarrow \mathcal{P}(X) \\ \text{for all $A \subseteq X$ by the assignment} \\ g_{0} \colon A &\mapsto A \\ g_{n} \colon A & \mapsto g_{n-1}(A) \cup (\cup \{ f(F) \colon F \subseteq g_{n-1}(A) \text{ is finite} \} ) \end{align}

Then $A \mapsto \cup \{ g_{n}(A) \colon n \in \mathbb{N} \}$ is a convex hull operator. The function $f$ generalizes the notion of the points between $x, y \in \mathbb{R}^{k}$. If you think of this construction in this manner then the $g_{n}$ functions just accumulate line segments.

• +1. Thanks! (1) In the theorem just for a closure system and its closure operator, and there is no convexity structure and convexity closure operator involved? What references is the theorem from? (2) When can a closure operator be a convexity closure operator (in abstract sense)? I guess we will need some properties from a convexity closure operator (in concrete sense, for a vector space over an ordered field)? – Tim Jan 3 '13 at 2:06
• The result is, more or less, theorem 1.3 in van de Vel's book. Click on this versionof the book The result is on page 5. – Jay Jan 3 '13 at 19:35
• In thm 1.3, he says that a closure operator is a convex closure operator iff it is domain finite. Is a closure operator being domain finite equivalent to $\operatorname{cl}(X) = \bigcup\left\{\operatorname{cl}(Y) : Y\subseteq X \text{ and } Y \text{ finite} \right\}$, i.e. finitary property in Wikipedia? So can we say that a closure operator is a convex closure operator iff it has the finitary property? – Tim Jan 7 '13 at 17:40
• (2) Wikipedia says "The convex hull in n-dimensional Euclidean space is another example of a finitary closure operator. It satisfies the anti-exchange property: If x is not contained in the union of A and {y}, but in its closure, then y is not contained in the closure of the union of A and {x}. Finitary closure operators with this property give rise to antimatroids." This is a concrete convexity structure, but for an abstract convexity, does its closure satisfy the anti-exchange property? (...) – Tim Jan 7 '13 at 17:43
• (...) Is a closure operator a convex closure operator iff it has both finatary and anti-exchange properties? – Tim Jan 7 '13 at 17:45