Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
$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
    
I have no idea to be honest. –  Olivier Bégassat Jan 2 '13 at 19:11
show 6 more comments

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
+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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.