Cayley graph

Cayley graph also know as Cayley colour graph, Cayley diagram, group diagram, or colour group  is a graph that encodes the abstract structure of a group

Definition Suppose that G is a group and S is a generating set. The Caylet graph \Gamma=\Gamma(G,S) is a colored directed graph constructed as follows

  • Each element g of G is assigned a vertex: the vertex set V(\Gamma) of \Gamma is identified with G.
  • Each generator s of S is assigned a color c_s.
  • For any g\in G,s\in S, the vertices corresponding to the elements g and gs by a directed edge of colour c_s. Thus the edge set E(\Gamma) consists of pairs of the form (g,gs), with s\in S providing the color.

In geometric group theory, the set S is usually assumed to be finite, symmetric and not containing the identity element of the group. In this case, the uncolored Cayley graph is an ordinary graph; its edges are not oriented and it does not contain loops (single-element cycles).

Jordan curve theorem and Alexander horned sphere

Jordan curve or a simple closed curve in the plane \mathbf{R}^2 is the image C of an injective continuous map of a circle into the plane, \varphi:S^1\to\mathbf{R}^2. A Jordan arc in the plane is the image of an injective continuous map of a closed interval into the plane.

With these definitions, the Jordan curve theorem can be stated as follow:

Let C be a Jordan curve in the plane \mathbf{R}^2. Then its complement, \mathbf{R}^2\setminus C, consists of exactly two connected components. One of these components is bounded (the interior) and the other is unbounded (the exterior), and the curve C is the boundary of each component.

Furthermore, the complement of a Jordan arc in the plane is connected.

The Schoenflies theorem is a sharpening of the Jordan curve theorem.

If C\subset\mathbf{R}^2 is a simple closed curve, then there is a homeomorphism f:\mathbf{R}^2\to\mathbf{R}^2 such that f(C) is the unit circle in the plane.

If the curve is smooth then the homeomorphsim can be chosen to be a diffeomorphism. Such a theorem is valid only in two dimension. In three dimensions there are counterexamples such as Alexander’s horned sphere. Although they separate space into two regions, those regions are so twisted and knotted that they are not homeormorphic to the inside and outside of a normal sphere.

Invariance of domain and retraction

Invariacne of domain

Invariance of domain states:

Theorem (Invariance of domain) If U is an open subset of \mathbf{R}^n and f:U\to\mathbf{R}^n is an injective continuous map, then V=f(U) is open and f is a homeomorphism between U and V.

The conclusion of the theorem can equivalently be formulated as: “f is an open map”. It is of crucial importance that both domain and range of f are contained in the Euclidean space of the same dimension. The theorem is also not generally true in infinite dimension.

retraction is a continuous mapping from the entire space into a subspace which preserves the position of all points in that space. A deformation retraction is a map which captures the idea of continuously shrinking a space into a subspace.


Definition Let X be a topological space and A be a subspace of X. Then a continuous map

\displaystyle r:X\to A

is a retraction if the restriction of r to A is the identity map on A; that is, r(a)=a for all a in A. Equivalently, denoting by

\displaystyle \iota:A\hookrightarrow X

the inclusion, a retraction is a continuous map r such that

\displaystyle r\circ\iota=\mathrm{id}_A.

A subspace A is called a retract of X if such a retraction exists.

Theorem Let X be a Hausdorff space and A be a retract of X. Then A is closed.

Proof Let x\notin A and a=r(x)\in A. Since X is Hausdorff, x and a have disjoint neighborhood U and V, respectively. Then r^{-1}(V\cap A)\cap U is a neighborhood of x disjoint from A. Hence, A is closed. \Box

A space X is known as an absolute retract if for every normal space Y contains X4 as a closed subspace, latex X$ is a retract of Y.

Deformation retract and strong deformation retract

Definition A continuous map

\displaystyle F:X\times [0,1]\to X

is a deformation retraction of a space X onto a subspace A if, for every x in X and a in A,

\displaystyle F(x,0)=x,\ F(x,1)\in A,\ \text{and}\ F(a,1)=a.

In other words, a deformation retraction is a homotopy between a retraction and the identity map on X. The subspace A is called a deformation retract of A. A deformation retraction is a special case of homotop equivalence.

Separation theorems in the plane

1 The Jordan separation theorem

Our proof of the Jordan curve theorem divides into three parts. The first, which we call the Jordan separation theorem, states that a simple closed curve in the plane separates it into at least two components. The second says that an arc in the plane does not separate the plane. And the third, the Jordan curve theorem proper, says that a simple closed curve C in the plane separates it into precisely two components, of which C is the common boundary.

Lemma 1 Let C be a compact subspace of S^2, let b be a point of S^2\setminus C; and let h be a homeomorphism of S^2\setminus b with \mathbf{R}^2. Suppose U is a component of S^2\setminus C. If U does not contain b, then h(U) is a bounded component of \mathbf{R}^2\setminus h(C). If U contains b, then h(U\setminus b) is the bounded component of \mathbf{R}^2\setminus h(C).

In particular, if S^2\setminus C has n components, then \mathbf{R}^2\setminus h(C) has n components.

Proof  We show first that if U is a component of S^2\setminus C, then U\setminus \{b\} is connencted.

Let (U_\alpha) be the set of components of S^2\setminus C; let V_\alpha=h(U_\alpha\setminus\{b\}). Because S^2\setminus C is locally connected, the set U_\alpha are connected, disjoint open subsets of S^2. Therefore the sets V_\alpha are connected, disjoint, open subsets of \mathbf{R}^2\setminus h(C), so the sets V_\alpha are the components of \mathbf{R}^2\setminus h(C).

Lemma 2 (Nulhomotopy lemma) Let a and b be points of S^2. Let A be a compact space, and let

\displaystyle f:A\to S^2\setminus\{a,b\}

be a continuous map. If a and b lie in the same component of S^2\setminus f(A), then f is nulhomotopic.

Definition 1 If X is a connected space and A\subset X, we say that A separates X if X\setminus A is not conneted; if X\setminus A has n components, we say that A separates X into n components.

Definition 2 An arc is a space homeomorphic to the unit inverval [0,1]. The end points of A are the two points p and q such that A\setminus\{p\} and A\setminus\{q\} are connected; the other points of A are called interior points of A.

simple closed curve is a space homeomorphic to the unit circle S^1.

Theorem 1Suppose X=U\cup V, where U and V are open sets of X. Suppose that U\cap V is path connected, and that x_0\in U\cap V. Let i and j be the inclusion mappings of U and V, respectively, into X. Then the images of the induced homomorphisms

\displaystyle i_*:\pi_1(U,x_0)\to \pi_1(X,x_0)\ \ \text{and} \ \ j_*:\pi_1(V,x_0)\to \pi_1(X,x_0)

generate \pi_1(X,x_0).

Theorem 2 (The Jordan separation theorem) Let C be a simple closed curve in S^2. Then C separate S^2.

2 Invariance of domain

Lemma 3 (Homotopy extension lemma) Let X be a space such that X\times I is normal. Let A be a closed subspace of X, and let f:A\to Y be a continuous map, where Y is an open subspace of \mathbf{R}^n. If f is nulhomotopic, then f may be extended to a continuous map g:X\to Y that is also nulhomotoptic.

The following lemma is partial converse to the nulhomotopy lemma of the preceding section.

Lemma 4 (Borsuk lemma) Let a and b be points of S^2. Let A be a compact space, and let f:A\to S^2\setminus\{a,b\} be a continuous injective map. If f is nulhomotopic, then a and b lie in the same component of S^2\setminus f(A).

Theorem 3 (Invariance of domain) If U is an open subset o \mathbf{R}^2 and f:U\to\mathbf{R}^2 is continuous and injective, then f(U) is open in \mathbf{R}^2 and the inverse function f^{-1}:f(U)\to U is continuous.

3 The Jordan curve theorem

The special case of the Seifert-van Kampen theorem that we used in proving the Jordan separation theorem tell us something about the fundamental group of the space X=U\cup V in the case where the intersection U\cap V is path connected. In the next theorem, we examine what happens when U\cap V is not path connected. This result will enable us to complete the proof the Jordan curve theorem.

Now we prove the Jordan curve theorem

Theorem (The Jordan curve theorem) Let C be a simple closed curve in S^2. Then C separates S^2 into precisely two components W_1 and W_2. Each of the sets W_1 and W_2 has C as its boundary; that is, C=\overline{W}_i-W_i for i=1,2.

Application of ultrafilters

An ultrafilter on a set X is a collection \mathcal{U} of subsets of X with the following properties:

  1. \emptyset \notin\mathcal{U} and X\in\mathcal{U};
  2. \mathcal{U} is closed under finite intersection;
  3. if A\in\mathcal{U} and A\subset B, then B\in\mathcal{U}
  4. fr every A\subset X, either A\in\mathcal{U} or X\setminus A\in\mathcal{U}.

A trivial example of an ultrafilter is the collection of all sets containing some fixed element x of X. Such ultrafilters are called principal. It is not trivial that there are any non-principal ultrafilters, but this can be proved using Zorn’s lemma.

The following facts about filters, which follow easily from the basic definition, will be used in this post. Let \mathcal{U} be an ultrafilter on a set X.

  1. If X is partitioned into finitely many sets A_1,\dots,A_n, the precisely one A_i belongs to \mathcal{U}.
  2. If F and G do not belong to \mathcal{U} then neither does F\cup G.
  3. If any finite set belongs to \mathcal{U} then \mathcal{U} is a principal filter.

Examples 1: generalized limits

We can think of the process of taking limits of sequence as a linear functional defined on the convergent sequences.

Can we generalize L by finding a linear functional \phi that is defined on all bounded sequences and not just all convergent on ? In order for it to count as a generalization, we would like \phi to be linear, and we would like \phi(a) to equal L(a) whenever a is convergent sequence.

If \mathcal{U} is a non-principal ultrafilter, and (a_1,a_2,\dots) is a sequence that takes values in [-1,1], then we can define a limit along \mathcal{U} as follows. Let \mathcal{J} be the collection of all subintervals J of [-1,1] such that \{n:a_n\in J\} belongs \mathcal{U}. Then the ultrafilter properties of \mathcal{U} imply that \mathcal{J} has all ultrafilter properties but restricted to intervals.

From this it follows that \mathcal{J} is something like a “principal interval-ultrafilter”. More precisely, it contains all open intervals that contain some particular point a. To see this, for each n\in\mathbf{N} partition [-1,1] into finitely many subintervals of length at most 1/n. Then one of these subintervals belongs to \mathcal{J}. So for every n we have an interval \mathcal{J}_n of length 1/n that belongs to \mathcal{J}. Now let I_n=J_1\cap \dots\cap J_n. Since \mathcal{J} is closed under intersection, I_n belongs to \mathcal{J}. Let \{a\} be the intersection of the closures of the  I_n (which are non-empety and nested). If U is any open interval containing a, then U contains some I_n, so belongs to \mathcal{U}.

Thus ,we have found a number a with the following property: for every \varepsilon>0, the set \{n:|a_n-a|<\varepsilon\} belongs to \mathcal{U}. Moreover, it is easy to see that this a is unique. We write it as \lim_{\mathcal{U}}a_n. It is easy to cheak that \lim_{\mathcal{U}} is linear.

To see ever more clearly how this ties in with the usual notion of a limit, note that a_n converges to a if and only if for every \varepsilon>0, the set \{n:|a_n-a|<\varepsilon\} belongs to the cofinite filter.

Set systems as quantifiers

It is often better to think of a set system as a quantifiers. In particular, if \mathcal{U} is an ultrafilter then one often finds oneself writing sentences of the form \{x\in X:P(x)\}\in\mathcal{U}, as we have already seen. But it can be much easier to deal with these sentences if one instead writes \mathcal{U}x\in X\ P(x). One can read this as  “For \mathcal{U}-almost every x\in X\ P(x)“.

Descriptive set theory

1 Polish space

Definition A topological space is called polish space if it is separable and completely metrizable (i.e. admits a complete compatible metric).

We work with Polish topological spaces as opposed to Polish metric spaces becasue we don’t want to fix a particular complete metric, we may change it to serve different purposes; all we care about is that such a complete compatible metric exists.

Lemma If X is a topological space with a compatible metric d, then  the following metric is also compatible: for x,y\in X, \overline{d}(x,y):=\min(d(x,y),1).


  1. Completion of any separable metric space is Polish.
  2. A closed subset of a Polish space is Polish (with respect to relative topology).
  3. A countable disjoint union of Polish spaces is Polish.
  4. A countable product of Polish spaces is Polish (with respect to the product topology).


  1. \mathbf{R}^{\mathbf{N}}, \mathbf{C}^{\mathbf{N}};
  2. The cantor space \mathcal{C}=2^{\mathbf{N}} with the discrete topology in 2;
  3. The Baire space \mathcal{N}=\mathbf{N}^{\mathbf{N}} with the discrete topology on \mathbf{N};
  4. The Hilbert cube I^{\mathbf{N}}, where I=[0,1].


Lemma If X is a metric space, then closed sets are G_\delta; equivalently, open sets are F_\sigma.

Proposition A subset of a Polish space is Polish if and only if it is G_\delta.

Proof Let X be a Polish space and let d_X be a complete compatible metric on X.

\Leftarrow Considering first an open set U\subset X, we exploit the fact that it does not contain its boundary point to define a compatible metric topology of U that makes the boundary of U “look like infinite” in order to prevent sequences that converge to the boundary from being Cauchy. In fact, instead of defining a metric  explicitly, we define a homeomorphism of U with a closed subset of X\times \mathbf{R} by

\displaystyle x\mapsto (x,\frac{1}{d_X(x,\partial U)}),

where d_X is a complete compatible metric for X.

\Rightarrow Let Y\subset X be  completely metrizable and let d_Y be a complete compatible metric for Y. Define an open set  V_n\subset X as the union of all open sets U\subset X that satisfy

  1. U\cap Y=\emptyset,
  2. \text{diam}_{d_X}(U)<1/n,
  3. \text{diam}_{d_Y}(U\cap Y)<1/n.

We show that Y=\bigcap_{n\in\mathbf{N}}V_n.

2 Trees

For a nonempty set A, we denote by A^{<\mathbf{N}}  the set of  finite tuples of elements of A, i.e.

\displaystyle A^{<\mathbf{N}}=\bigcup_{n\in\mathbf{N}}A^n,

where A^{0}=\{\emptyset\}. For s\in A^{<\mathbf{N}}, we denote by |s| the length of s.

Definition  For a set A, a subset T of A^{<\mathbf{N}} is called a (set theoretic) tree if it is cloded downward under \subset.

Posets, simplicial complexes, and polytopes


Definition partially ordered set or poset is a set P equipped with a relation \leq that is reflexive, antisymmetric, and transitive. That is, for all x,y,z\in P:

  1. x\leq x.
  2. If x\leq y and y\leq x, then x=y (antisymmetry)
  3. If x\leq y and y\leq z, then x\leq z (transitivity).

We say that x is covered by y, written x\lessdot y, if x<y and there is no  z such that x<z<y. Two posets P,Q are isomorphic  if  there is a bijection \phi:P\to Q that is order-persverin; that is, x\leq y in P iff \phi(x)\leq \phi(y) in Q.

We’ll usually assume that P is finite.

Ranked posets

Definition A chain x_0<x_1<\dots<x_n is saturated if it is not properly contained in any other chain from x_0 to x_n; equivalently, if x_{i-1}\lessdot x_i for every i\in [n]. In this case, the number n is the length of the chain. A poset P is ranked if for every x\in P, all saturated chains with top element x have the same length; this number is called the rank  of x and denoted r(x).  A poset is graded if it is ranked and bounded.

Definition Let P be a ranked set with rank function r. The rank-generating function  of P is the formal power series

\displaystyle F_p(q):=\sum_{x\in P}q^{r(x)}.

Simplicial complexes

Definition Let V be a finite set of vertices. An simplicial complex \Delta on V is a nonempty family of subsets of V with the property that if \sigma\in\Delta and \tau\subset\sigma, then \tau\in\Delta. Equivalently, \Delta is an order ideal in the Boolean algebra 2^V. The element of \Delta are called its faces or simplices.

The incidence algebra of a poset

Let P be a poset and let \mathrm{Int}(P) denote the set of (nonempty) intervals of P, i.e., the sets

\displaystyle [x,y]:=\{z\in P:x\leq z\leq y\}

for all x\leq y.

We will always assume that p is locally finite, i.e., every interval is finite.

Definition (Incidence algebra) The incidence algebra is the set of funciton f:\mathrm{Int}(P)\to\mathbf{C} (“incidence funcitons”), made into a \mathbf{C}-vector space with pointwise addition, subtraction and scalar multiplication, and equipped with the convolution product 

\displaystyle (f*g)(x,y)=\sum_{z\in[x,y]}f([x,z])g([z,y]).

It is often convenient to set f(x,y)=0 if  x\nleqslant y. Note that the assumption of local finiteness is both necessary and sufficient for convolution to be well-defined.

Proposition Convolution is associative (although it is not in general commutative).

Proposition An incidence function f\in I(P) has a left/right two side side-convolution inverse if and only if f([x,x])\neq 0 for all x. In that case, the inverse is given by the formula

\displaystyle f^{-1}([x,y])=\begin{cases} f([x,x])^{-1} & \text{if}\ x=y,\\  -f([y,y])^{-1}\sum_{z:x\leq z<y} f^{-1}(x,z)f(z,y)& \text{if}\ x<y.  \end{cases}


Lattice property of the class of signed measures

Signed measures have values either in (-\infty,+\infty] or [-\infty,-\infty), to avoid the possibility of adding +\infty to -\infty. If  (X,\mathcal{X},\mu) is a signed measure space and A is a measurable set, define

\displaystyle \mu_+(A):=\sup_{B\subset A}\mu(B),\quad \mu_-(A):=-\inf_{B\subset A}\mu(B),\quad |\mu|=\mu_++\mu_-.

The set function \mu_-,\mu_+ and |\mu| are respectively the positive, negative and total variations of \mu.

Theorem If \mu and \nu are signed measures on a measurable space, there is a signed measure \mu\vee \nu majorizing \mu and \nu and majorized by every other signed measure majorant \mu and \nu.

Proof If \mu-\nu is a well-defined signed measure, that is if \mu(X) and \nu(X) are not both +\infty or both -\infty. Let X_+ be a maximal positivity set and X_- be a maximal negativity set, for \mu-\nu. Define

\displaystyle (\mu\vee\nu)(A):=\mu(A\cap X_+)+\nu(A\cap X_-).

This sum defines a measure with the required properties.

Tangent spaces and derivatives

Partial derivatives with respect to local coordinates

Let U\to\mathbf{R}^n be a smooth chart defined over an open set U in M. Then there are smooth real-valued functions x^1,x^2,\dots,x^n on U such that

\displaystyle \varphi(u)=(x^1(u),x^2(u),\dots,x^n(u))

for all u\in U. The functions x^1,x^2,\dots,x^n determined by the chart (U,\varphi) constitute smooth local coordinate functions defined over the domain U of the chart.

Definition Let x^1,x^2,\dots,x^n be smooth local coordinates defined over an open set U in a smooth manifold M of dimension n, and let V be the corresponding open set in \mathbf{R}^n defined such that


Lindelof hypothesis


\displaystyle \mu(\sigma):=\inf\{a\in\mathbf{R}:\zeta(\sigma+it)=O(|t|^a)\}.

It is trivial to check that \mu(\sigma)=0 for \mu(\sigma)=0 for \sigma>1, and the functional equation of zeta function implies that

\displaystyle \mu(\sigma)=\mu(1-\sigma)-\sigma+1/2.

The Phragmen-Lindelof theorem implies that \mu is a convex function. The Lindelof hypothesis states \mu(1/2)=0, which together with the above properties of \mu implies that \mu(\sigma) is 0 for \sigma\geq 1/2 and 1/2-\sigma for \sigma\leq 1/2.