4
$\begingroup$

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!

$\endgroup$
11
  • $\begingroup$ $Conv(T)=T$ for any affine subspace $T$, and $Conv(S\setminus T)= S$ unless $S=T$. $\endgroup$ Commented Jan 2, 2013 at 18:01
  • $\begingroup$ @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. $\endgroup$
    – Tim
    Commented Jan 2, 2013 at 18:05
  • 1
    $\begingroup$ Also, $$Conv(X)=\bigcup_{F\subset X,~F\text{ finite}}Conv(F)$$ $\endgroup$ Commented Jan 2, 2013 at 18:19
  • $\begingroup$ @OlivierBégassat: Thanks! Did you come up with the three properties yourself? Do you know if they can characterize a convex closure operation? $\endgroup$
    – Tim
    Commented Jan 2, 2013 at 18:24
  • 1
    $\begingroup$ Fyi > in geometry 4 closure operators are widely considered: convex, affine, cone, and linear hulls (spans). $\endgroup$ Commented Jan 3, 2013 at 3:33

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ +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)? $\endgroup$
    – Tim
    Commented Jan 3, 2013 at 2:06
  • $\begingroup$ 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. $\endgroup$
    – Jay
    Commented Jan 3, 2013 at 19:35
  • $\begingroup$ 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? $\endgroup$
    – Tim
    Commented Jan 7, 2013 at 17:40
  • $\begingroup$ (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? (...) $\endgroup$
    – Tim
    Commented Jan 7, 2013 at 17:43
  • $\begingroup$ (...) Is a closure operator a convex closure operator iff it has both finatary and anti-exchange properties? $\endgroup$
    – Tim
    Commented Jan 7, 2013 at 17:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .