Linear separability

(Cover, 1965)  Suppose we have $N$ data points distributed at random in $\mathbb{R}^d$ with an unspecified distribution.  Assume that there is no subset of $d$ or fewer points which are linearly dependent.  We then assign each of the points to one of the two classes $\mathcal{C}_1$ and $\mathcal{C}_2$ with equal probability.

The fraction $F(N,d)$ of realizations that is linearly separable is given by the expression
$$F(N,d) = \left\{     \begin{matrix}     1 \quad &\mathrm{when}\; N \le d+1 \\     \frac{1}{2^{N-1}}\sum\limits_{i=0}^d \left( \begin{matrix} N-1 \\ i \end{matrix} \right) \quad & \mathrm{when}\; N \ge d + 1     \end{matrix}\right.$$ Intuitively, the probability of separability increase with increasing dimension $d$.

[TODO] include plot...

http://www-isl.stanford.edu/~cover/papers/paper76.pdf

Simply connectedness

Informally, a thick object in our space is simply-connected if it consists of one piece and does not have any "holes" that pass all the way through it.

A sphere (or, equivalently, a rubber ball with a hollow center) is simply connected, because any loop on the surface of a sphere can contract to a point, even though it has a "hole" in the hollow center.

The stronger condition, that the object has no holes of any dimension, is called contractibility.

Another characterization of simply-connectedness is the following:

$X$ is simply-connected if and only if 

• it is path-connected, and 
• whenever $p: [0,1] \rightarrow X$ and $q: [0,1] \rightarrow X$ are two paths (i.e. continuous maps) with the same start and endpoint ($p(0)=q(0)$ and $p(1) == q(1)$), then $p$ and $q$ are homotopic relative to {0,1}.

Intuitively, this means that $p$ can be "continuously deformed" to get $q$ while keeping the endpoints fixed. Hence the term simply connected: for any two given points in $X$, there is one and "essentially" only one path connecting them.

Examples:

• All convex sets in $\mathbb{R}^n$ are simply connected.
• A sphere is simply connected.