That formula of Cayley asserts that there are $n^{n-2}$ trees with vertices labeled $1,\dots,n$. This is a chapter in graph theory, in which graphs are “simple”. More precisely, let's call a graph structure on a set $V$ (called “vertices”) is the datum of a subset $E$ of 2-element subsets of~$V$, called “edges”. So an edge is of the form $\{a,b\}$, where $a$ and $b$ are distinct elements of $V$, and we say that the edge links $a$ to $b$.
A path in this graph is a sequence $(a_0,a_1,\dots,a_n)$ where $a_0,\dots,a_n$ are vertices such that $\{a_{k-1},a_k\}$ is an edge, for each $k\in\{1,\dots,n\}$; this path has length $n$, and it connects $a_0$ to $a_n$. A graph is said to be connected if every two vertices are connected by some path.
A loop is a path whose first vertex $a_0$ equals the last one $a_n$. Examples of loops are paths of length $0,$ given by one vertex. Less trivial examples are obtained by taking an edge $\{a,b\}$ and considering the path $(a,b,a)$; a path that does not contain this pattern will be called a path without back and forth. (There's a translation issue between English and French, for the French wording for this expression is sans aller-retour, which seems more natural to me — you first go somewhere before returning back.) In any case, if every loop without back-and-forth in the graph has length $0$, then one says that the graph is a forest. Finally, a tree is a connected forest.
In a connected graph, any two vertices $a,b$ are connected by some path, and if the graph is a tree, then there is a unique such path which has no back-and-forth. Indeed, if there were two such paths $(a,a_1,\dots,a_{m-1},b)$ and $(a,b_1,\dots,b_{n-1},b)$ connecting $a$ to $b$, where, say, $m+n$ is minimal, then one can build the loop $(a,a_1,\dots,a_{m-1},b,b_{n-1},\dots,b_1,a)$. By definition of a tree, this loop must have some back-and-forth. It must be $(a_{m-1},b,b_{n-1})$, for otherwise the two given paths would have had some back-and-forth. In particular, $a_{m-1}=b_{n-1}$ and the two paths $(a,a_1,\dots,a_{m-1})$ and $(a,b_1,\dots,b_{m-1})$ have no back-and-forth, connect the same pair of points, and their lengths are smaller. This furnishes the desired contradiction.
Theorem (Cayley). — If $V$ is a finite set of cardinality $n\geq 2$, then there are $n^{n-2}$ structures of tree on $V$.
Here is the proof of this theorem that Joyal gives in his paper “Une théorie combinatoire des séries formelles” (Advances in Mathematics 42 (1): 1‑82). I thank François Lamarche for having urged me to read that paper.
Joyal's idea consists in considering the structure of an “animal” obtained by selecting two vertices of a tree. Given two vertices $a,b$, the vertices in the unique path linking $a$ to $b$ are called its vertebrae, and the set of vertices is called its spine. We now need to prove that there are $n^n$ structures of animal on a non-empty set with $n$ elements. (This combinatorial description does not work well for $n=0$, there are no animals with $0$ elements, but $0^0=1$.)
Now, each vertex $x$ in an animal is connected to some vertebra, and there is a preferred vertebra $v(x)$ for which there is a path $(x,\dots,v(x))$ that does not contain any other vertebra than $v(x)$. Note that all vertices $y$ in that path satisfy $v(y)=v(x)$. In particular, $v(v(x))=v(x)$, that is, the map $v$ is idempotent.
Given some vertebra $t$, let us consider the subgraph $T_t$ of the given tree with set of vertices $v^{-1}(t)$. It is again a graph, and is even a tree since each of its vertices is connected to $t$, and a subgraph of a forest is a forest.
As a conclusion, animals $(a,b,T)$ with vertex set $V$ are in bijection with ordered pairs consisting of the sequence $(a,\dots,b)$ of vertebrae forming the spine together with a family of disjoint trees indexed by the spine and whose union if $V$.
On the other hand, one can associate to any self-map $f\colon V\to V$ a similar structure of an idempotent map $v\colon V\to V$ together with a tree structure of $v^{-1}(t)$ for every $t\in V$. Indeed, let $S$ be the set of periodic points for $f$, that is, elements $x\in V$ for which there exists $n\geq 1$ with $f^n(x)=x$. If $x$ is periodic for $f$, then so is $f(x)$, so that $f$ induces a map $f_S$ from $S$ to $S$. That map is bijective. On the other hand, for every $x\in V$, the sequence $x, f(x),f^2(x),\dots$ will eventually repeat itself, because $V$ is finite, so that there exist integers $m$ and $n$ such that $0\leq m < n$ and $f^m(x)=f^n(x)$. In particular, $f^m(x)=f^{n-m}(f^m(x))$ is periodic for $f$. Let us then denote by $v(x)$ the first periodic point in the sequence $x,f(x),f^2(x),\dots$ of iterates of $x$. (Technically, $v(x)=f^m(x)$ where $m$ is the smallest integer such that $f^m(x)$ is periodic for $f$.
For each periodic point $s\in S$, let $V_s$ be the set $v^{-1}(s)$. We define a tree with set of vertices $V_s$ as follows: its edges are simply the pairs $\{x,f(x)\}$, for $x\in V_s\setminus\{s\}$. To convince oneself that this actually forms a tree, it maybe better to imagine its construction from the vertex set $s$. One has an edge from $s$ to all non-periodic points $x\in V$ such that $f(x)=s$. And then an edge from each of these points $x$ to the points $y\in V$ such that $f(y)=x$ (and such $y$ are distinct from $x$, and are non-periodic), etc. building the tree from its root $s$.
In conclusion, self-maps $f$ are in bijections with triples $(S,f_S, (V_s))$ where $S$ is a subset of $V$, $f_S$ is a bijection of $S$ and $(V_s)$ is a family of disjoint trees disjoint containing $s$ such that $V=\bigcup V_s$.
To conclude this proof of Cayley's theorem, it remains to observe that for each subset $S$ of $V$, there are $\operatorname{Card}(S) !$ ways to, either put the elements of $S$ in some linear order, or to define a bijection of $S$. In both cases, it remains to additional families of trees are equinumerous, so that the number of self-maps of $V$ is equal to the number of animals with vertex set $V$, as claimed.
No comments :
Post a Comment