Q:

What is an example of a SVM kernel, where one implicitly uses an infinity-dimensional space?

Reading the Wikipedia article about SVMs, I noticed

More formally, a support vector machine constructs a hyperplane or set of hyperplanes in a high- or infinite-dimensional space, which can be used for classification, regression, or other tasks.

I continued with "A Tutorial on Support Vector Machines for Pattern
Recognition" by Christopher JC Burges and stumbled over the following (please not that $x \cdot y$ is the dot product):

Now suppose we first mapped the data to
  some other (possibly infinite dimensional) Euclidean space $\mathcal{H}$, using a mapping which we
  will call $\Phi$:
  $$\Phi : \mathbb{R}^d \rightarrow \mathcal{H}$$
  Then of course the training algorithm would only depend on the data through dot products
  in $\mathcal{H}$, i.e. on functions of the form $\Phi(\mathbf{x}_i)\cdot \Phi(\mathbf{x}_j)$. Now if there were a “kernel function” $K$
  such that $K(\mathbf{x}_i, \mathbf{x}_j) = \Phi(\mathbf{x}_i)\cdot\Phi(\mathbf{x}_j)$, we would only need to use $K$ in the training algorithm,
  and would never need to explicitly even know what $\Phi$ is. One example is
  $$K(\mathbf{x}_i, \mathbf{x}_j ) = e^{- \| \mathbf{x}_i - \mathbf{x}_j\|^2 / 2 \sigma^2}$$
  In this particular example, $\mathcal{H}$ is infinite dimensional, so it would not be very easy to work
  with $\Phi$ explicitly.

I have three questions which are closely related to this. I am happy with any answer which answers any of my questions:

Why would $\mathcal{H}$ be infinitely dimensional in this case?
What is $\Phi$ in this case?
In other sources I read that the Kernel function has to be positive definite. Why?

A:

To understand the first two questions, let's consider $x, y \in \mathbb{R}^2, x=(x_1,x_2), y=(y_1, y_2)$ and examine the polynomial kernel of degree 2:
$$K(x,y)=(x^Ty)^2$$
Which can be rewritten as:
$$K(x,y) = (x_1y_1 + x_2y_2)^2 = x_1^2y_1^2 + 2x_1y_1x_2y_2 + x_2^2y_2^2$$
We know that the kernel function is $K(x,y)=\Phi(x)^T\Phi(y)$, therefore we try to find a feature map $\Phi$ that will be equivalent to the above. Let
$$\Phi(x)=(x_1^2, \sqrt{2}x_1x_2, x_2^2)$$
From this, we can see that $\Phi(x)^T\Phi(y) = x_1^2y_1^2 + 2x_1y_1x_2y_2 + x_2^2y_2^2$, which is the kernel function! 
Notice that by using $\Phi$ we mapped the input vectors from $\mathbb{R}^2$ to $\mathbb{R}^3$, therefore when we compute $K(x,y)$, this mapping will be implicitly performed.
Now, going back to your example (the RBF kernel). Let $\gamma = \frac{1}{2\sigma^2}$ and let's assume $x \in \mathbb{R}^1$:
$$K(x_i, x_j) = e^{-\gamma||x_i - x_j||^2} = e^{-\gamma(x_i - x_j)^2} = e^{-\gamma x_i^2 + 2\gamma x_i x_j - \gamma x_j^2}$$
Using the Taylor expansion of the exponential function for $e^{2\gamma x_i x_j}$ we can rewrite the above as:
$$ K(x_i, x_j) = e^{-\gamma x_i^2-\gamma x_j^2} \left(1 + \frac{2\gamma x_i x_j}{1!} + \frac{(2\gamma x_i x_j)^2}{2!} + \frac{(2\gamma x_i x_j)^3}{3!} + \ldots \right)$$ 
$$ = e^{-\gamma x_i^2-\gamma x_j^2} \left(1 \cdot 1 + \sqrt{\frac{2\gamma}{1!}}x_i \cdot \sqrt{\frac{2\gamma}{1!}}x_j + \sqrt{\frac{(2\gamma)^2}{2!}}x_i^2 \cdot \sqrt{\frac{(2\gamma)^2}{2!}}x_j^2 + \sqrt{\frac{(2\gamma)^3}{3!}}x_i^3 \cdot \sqrt{\frac{(2\gamma)^3}{3!}}x_j^3 + \ldots  \right) = \Phi(x_i)^T \Phi(x_j)$$ 
And, explicitly the feature map will be:
$$\Phi(x) = e^{-\gamma x^2} \left[1, \sqrt{\frac{2\gamma}{1!}}x,\sqrt{\frac{(2\gamma)^2}{2!}}x^2, \sqrt{\frac{(2\gamma)^3}{3!}}x^3, \ldots\right]$$
Which is an infinite-dimensional vector. As you said, in kernel methods we will compute inner products in feature space without explicitly having to define the mapping $\Phi$. Avoiding this explicit mapping is the famous "kernel trick".

