J Tomasini

Realizations of self branched coverings of the 2-sphere

Keywords: MSC Classification: 57M12, 57M15 Branched coverings, Hurwitz problem, Balanced map

may come

Realizations of self branched coverings of the 2-sphere

Introduction

The main topic of this article is the study of branched covers from S 2 to S 2 . Typical examples are meromorphic functions defined on the Riemann sphere. Our objective is to introduce a new set of combinatorial properties of these branched coverings and solve the related realization problems.

A map π : S 2 → S 2 is called a branched (or ramified) covering of degree d, if there exists some finite subset F ⊂ S 2 such that • the restriction map π : S 2 \ π -1 (F ) → S 2 \ F is a covering map of degree d;

• for each point x ∈ F , there is a neighborhood V of x, and a neighborhood U of each preimage y of x by π, such that the restricted map π| U : U → V is equivalent, up to topological change of coordinates, to the map z → z k on the unit disc, for some integer k > 0.

This integer is uniquely determined for any point y of π -1 (F ) (and more generally for any point of S 2 ), and it's called the ramification number of y. Notice that this number is equal to the number of preimages, close to y, of a point close to x. In particular, this integer is equal to 1 if and only if π is locally a homeomorphism.

A point whose the ramification number is greater than 1 is called a critical point, and its image a critical value. Moreover, the sum of the ramification numbers of the preimages of any point in S 2 is constant, equal to the degree of the branched covering. In other words, the ramification numbers of the preimages of any point x in S 2 form an integer partition of d. And this partition is not the trivial partition (1, . . . , 1) if and only if x is a critical value.

So, let π be a branched covering π of degree d, then we can associate to π two combinatorial properties:

• the (unordered) list l = (a 1 , . . . , a m ) of ramification numbers at the critical points, with 2 ≤ a i ≤ d for every i;

• the branch datum D = [Π 1 , . . . , Π n ], with each Π i a non trivial integer partition of d, representing the collection of ramification numbers of the preimages of the i-th critical value.

Here, the integers m and n are respectively the number of critical points and the number of critical values of π. Notice also that the branch datum incorporates the information of all the other properties of π. For example, consider the application f : Ĉ → Ĉ defined by:

f (x) = (x 2 -1) 2 x 3 .
This function defines a branched covering of the sphere of degree 4 with 5 critical points (0, ±1, ±i), 4 critical values (0, ±4i, ∞), its list of ramification numbers is (3, 2, 2, 2, 2) and its branched datum is

[[3, 1], [2, 2], [2, 1, 1], [2, 1, 1]].
Our focus will be on the realization problem of these combinatorial properties. It can be expressed as follows:

Realization problem Consider an integer d ≥ 2. Given a list l = (a 1 , . . . , a m ) of integers, with 2 ≤ a i ≤ d, or a list D of non-trivial integer partition of d, can it be realized by a branched covering of S 2 of degree d?

This problem, in particular the realization problem of an abstract branch datum, is generally called the Hurwitz problem. There exists an important necessary condition, called the Riemann-Hurwitz condition (we will reprove it along the way).

Let Π i = [k 1 , . . . , k ni ] be an integer partition of d. We define the weight of Π i , denoted ν(Π i ), by

ν(Π i ) = ni j=1
(k j -1).

We define the branched weight (or total weight) of a list D = [Π 1 , . . . , Π n ] of such partitions by

ν(D = n i=1 ν(Π i ).
Riemann-Hurwitz condition If a list D = [Π 1 , . . . , Π n ] of integer partitions of d is the branch datum of a branched covering of degree d, then ν(D) = 2d -2.

(1)

We can also rewrite this condition for the list of ramification numbers: Riemann-Hurwitz condition If a list of integers l = (a 1 , . . . , a m ) is the list of ramification numbers at the critical points of a branched covering of degree d, then 2 ≤ a i ≤ d for every i and i (a i -1) = 2d -2.

Notice that the numbers m of critical points, and n of critical values of a branched covering of degree d ≥ 2 satisfy 2 ≤ n ≤ m ≤ 2d -2.

A list that satisfies the Riemann-Hurwitz condition will be called a ramification distribution of degree d, and a list D of integer partitions of d that satisfies the Riemann-Hurwitz condition is generally called a passport in the literature. The classical Hurwitz problem can then be expressed as follows: which passport is realized?

There is a huge literature on this problem. Many partial results have been obtained, using either the initial approach of Hurwitz, see for example [START_REF] Edmonds | Realizability of branched coverings of surfaces[END_REF] or [START_REF] Gersten | On branched covers of the 2-sphere by the 2-sphere[END_REF]), or using a more geometric approach, see for example [START_REF] Baranski | On realizability of branched coverings of the sphere[END_REF] or [START_REF] Zheng | Realizability of branched coverings of S 2[END_REF]. Nevertheless, this problem remains largely open till today.

Following an initial work of W. Thurston, we will introduce a new set of combinatorial properties, namely a bipartite map and its incident matrix, all incorporating the information about the ramification numbers at the critical points. We then solve completely their realization problem.

Thurston's geometrical approach

During the autumn 2010, W. Thurston conducted a group discussion through e-mails on what he called the shapes of rational maps. Along the way, he established a beautiful result, which becomes the starting point of our present study. Here is an account of his statement. For a presentation of the initial proof of W. Thurston, the reader can refer to the manuscript of Sarah Koch and Tan Lei [START_REF] Koch | On balanced planar graphs[END_REF].

Consider π : S 2 → S 2 a generic branched covering of the sphere of degree d, i.e. π has exactly 2d -2 distinct critical values. Then, pick a Jordan curve Σ running through the critical values. For example, for a rational map with all critical values real, one may pick the real axis union the point at infinity as Σ. We will consider Σ as a planar map (i.e. a connected graph drawn on the sphere) with 2d -2 vertices, each of valence 2. Now, pulling back Σ by π, we get a new planar map π -1 (Σ). Forgetting the 2-valence vertices of π -1 (Σ), we get a further planar map Γ with 2d -2 vertices (the critical points of π), all of valence 4. We call Γ the underlying 4-valent map of π -1 (Σ). This is the combinatorial object we will be focused on. Thurston solved its realization problem as follows:

Theorem 1. (Thurston, [START_REF] Koch | On balanced planar graphs[END_REF]) A 4-valent planar map Γ is realized by a generic branched covering π as the underlying map of π -1 (Σ) for some choice of Σ, if and only if it satisfies the following balanced condition:

1. (global balance) In an alternative coloring of the complementary faces of Γ, there are equal numbers of white and black faces.

(local balance)

For any oriented simple closed curve drawn on the map that keeps black faces on the left and white faces on the right (except at the corners), there are strictly more black faces than white faces on the left side.

The key idea to prove this theorem is to translate the realization problem into finding a pattern of dots so that each face is incident to exactly 2d -2 vertices, and then into a matching problem on the map. More exactly, consider a 4-valent planar map Γ and put 2d -2 men in each black face, and 2d -2 women in each white face. Then, for each face, remove one person per vertex incident to this face. Each remaining person is trying to find a partner from one of the neighboring faces.

Thurston proves that the usual marriage criterion (see Theorem 2.17) can be reduced to the global and local balance conditions in Theorem 1. An interested reader may compare the geometrical point of view of Thurston to that of Baranski in [START_REF] Baranski | On realizability of branched coverings of the sphere[END_REF].

Our contributions

We will conduct a self-contained study, similar to that of Thurston, for all branched coverings. In a way, we recover Thurston's result in the generic case, with a similar idea of proofs, but with a different presentation.

For our purpose, we find it convenient to pull back a different map than a Jordan curve running through the critical values.

Let π : S 2 → S 2 be a branched covering of degree d ≥ 2. Color white each of its critical values. Pick a non critical value point and color it black. Pick a collection of pairwise disjoint 'legs' connecting the black vertex to each white vertex. We obtain a bipartite map T , i.e. a planar map whose edges are connected to a white and a black vertex. Now pulling back by π the map T and then erasing every 1-valence white vertex together with its unique incident edge, we obtain a bipartite map G, called a skeleton of π. This is the first combinatorial object we will be focused on. We will establish the following realization results: Theorem A A planar bipartite map G is realized as a skeleton of a branched covering if and only if it satisfies the following balanced condition:

• (global balance condition) G has as many black vertices as faces.

• (local balance condition) Each submap H of G containing at least one black vertex has at least as many black vertices as faces.

A bipartite map, or more generally a bipartite graph (see definitions below) induces a white-to-black incident matrix A = (a ij ) as follows: numerate separately the black vertices and the white ones, and set a ij = k if there are k edges connecting the i-th white vertex to the j-th black vertex. Our next realization result can be stated as follows:

Theorem B Let d ≥ 2 be an integer. Pick an integer 1 ≤ m ≤ 2d -2 and an m × d matrix A = (a ij ). Then A is realized as the incident matrix of a skeleton of a degree d branched covering if and only if it satisfies the following conditions:

• the bipartite graph associated to A is connected and admits an embedding into the plane.

• (global balance condition) The column vector (b i ) obtained by summing up the columns of A satisfies i (b i -1) = 2d -2.

• (local balance condition) For any integer 1 ≤ k < d, and any choice of k distinct columns of A, the column vector (c i ) obtained by summing up the selected columns satisfies i (c i -1) ≤ 2k -2.

Notice that these conditions on the matrix A are invariant under permutations of lines and columns of A, so do not depend on the numerations of the vertices of its bipartite graph. As an easy consequence, we obtain a solution of one of our initial realization problem:

Theorem C Let d ≥ 2 be an integer. Pick a list l = (a 1 , . . . , a m ) of integers, with 2 ≤ a i ≤ d for every i. Then l is realized as the list of critical ramification numbers of a degree d branched covering if and only if it satisfies the following condition:

• (global balance condition) i (a i -1) = 2d -2.
The necessity comes from the Riemann-Hurwitz condition. It is interesting to notice that there is no local condition for this last realization result. In particular, this result supposes that the construction of a branched datum from a list of integers is hidden in this local condition. For example, consider the list (3, 2, 2, 2, 2), then this list satisfies the Riemann-Hurwitz condition for d = 4, and the realized passports we can construct from this list are

[[3, 1], [2, 1], [2, 1], [2, 1], [2, 1]] or [[3, 1], [2, 2], [2, 1], [2, 1]], but the list [[3, 1], [2, 2], [2, 2]] is not a realized passport.
Here appears another interesting question: consider a ramification distribution of degree d, for a given integer d. What is the minimal number of partition of d we need to construct a realized passport? In our example, this number is equal to 4. The problem of minimality is a difficult problem, and will be considered in future project. The interested reader can still find an equivalent problem in ([Tom14],p.101).

Contents

The structure of this article is based on the following schema. After introducing all the tools necessary for the understanding and the construction of the combinatorics used here, we begin the third section by the study of the branched coverings of S 2 to itself, leading to a classification up to topological equivalence. The starting point of this work is the characterization of Thurston we mentioned earlier. Then, we give a new characterization of the balanced maps that allow us to "extend" this notion on the set of graphs.

We finish this section by proving one of the main result of this article (Theorem A) which is a generalization of the result of Thurston (Theorem 1) that proves there exists a bijection between what we call a skeleton of a branched covering, and the set of balanced maps.

In the last section, we come back to the Hurwitz problem mentioned earlier. More exactly, after giving a relation between the global balanced condition on our maps and the Riemann-Hurwitz condition, we establish a matrix interpretation of the balanced conditions defined in the third section (Theorem B), we finally prove that a ramification distribution of degree d always comes from a branched covering of degree d (Theorem C).

Combinatorial tools 2.1 Increasing bipartite maps

The purpose of this subsection is to introduce the main combinatorial objects, and some constructions that will be useful in the following. As there is many manner to introduce planar maps, we begin this subsection by introducing the main definition in order to fix the notion and notation we use in this article. The approach chosen here comes from the books of C. Berge [START_REF] Berge | Graphs[END_REF], W. T. Tutte [START_REF] Tutte | Graph theory[END_REF], P. Flajolet and R. Sedgewick [START_REF] Flajolet | Analytic Combinatorics[END_REF], or again J. L. Gross and T. W. Tucker [START_REF] Gross | Topological graph theory[END_REF].

Definition 2.1. A graph G is given by two finite sets E G and V G and an application ρ

G from E G to V G × V G .
An element of V G (resp. E G ) is called a vertex (resp. an edge) of G. For each edge a of E G is associated a couple of vertices ρ(a) forming the tips of a. We say that two vertices of G are adjacent if they are the tips of an edge. An edge whose tips are the same is called a loop of G. Finally, we say that an edge a is incident to a vertex v if v is one of the two tips of a. In this case, we say also that v is incident to a. Particularly, a loop of tip v is doubly incident to the vertex v. The degree of a vertex v of G is the number of edges of G being incident to v, counted with multiplicity. Particularly, if G is a graph with n edges, the sum of the degree of all the vertices of G is equal to 2n, i.e the degrees of the vertices give a partition of 2n.

Notice that this definition of graph is a combinatorial definition, but we often consider in the following a graph as a topological object, i.e a set of points (the vertices) link by some line (the edges).

Definition 2.2. Let G and H be two graphs. We say G and H are isomorphic if there exists a bijection φ : V G → V H and a bijection ψ :

E G → E H such that ρ H • φ = ψ • ρ G .
In other words, the bijections φ and ψ preserve the incident relation. This relation between graphs defines an equivalence relation. In the following, graphs are always considered up to this equivalence relation. Now, we can define the notion of map. We call embedding of a graph G a repreasentation of G in a surface such that the edges of G only have intersection on the vetices of G. Notice that such an embedding is not always possible in a given surface (see "problème des trois ponts" for example). If a graph admits such an embedding on the Riemann sphere, or equivalently on the plane, we say that G is a planar graph. The embedding of a graph G on a surface divise this surface into some connected components called faces. An embedding is called cellular if each face is simply connected.

Definition 2.3. A planar map is a cellular embedding of a graph G in the Riemann sphere.

In particular, a planar map is connected. As for the graph, we can define some incident relation between vertices-faces, vertices-edges and edges-faces. Notice that an edge is incident to exactly two faces (eventually the same) whereas a vertex can be incident to an arbitrary number of faces.

For convenience, we draw a planar map on the plane and not on the sphere, but this drawing is only a representation of the planar map. In fact, by projecting the sphere on the plane via a stereographic projection, we send a point of the sphere to infinity, so depending of the choice of the projection we obtain different representations of the same planar map.

Definition 2.4. Let G and H be two planar maps. We say that G and H are isomorphic if the vertices, edges and faces of one map can be sent bijectively on the vertices, edges and faces of the second one, preserving the three incident relations.

Once again, this relation define an equivalence relation and so from now planar maps are considered up to this equivalence relation. We can now define the notion of submap.

Definition 2.5. Let G be a planar map. We say that H is a submap of G, denoted by H ⊂ G, if H is itself a planar map and H can be obtained by erasing some edges and vertices of G. Moreover, we say that H is a full submap of G, denoted by H < G, if H is a submap of G and there exists at most one face f of H such that every edge of G not in H is contained in f . By convention, G itself is a (full) submap of G. Note that if H is a submap of G, then the set of vertices, resp. edges, of H is a subset of those of G, but a face of H either coincides with a face of G or contains several faces of G. The reader can see examples of full submaps in Figure 4.

This terminology of full submap is motivated by the notion of planar full continua namely compact sets that are connected with a connected complement in the 2-sphere.

Definition 2.6. Let G be a planar map with at least two vertices. We say that G is (black and white) bipartite if each vertex of G is colored in either white or black and each edge of G has a black and a white tip (in particular a bipartite map has no loop).

A tree is a bipartite map with a unique face. A star-like map is a bipartite tree with a unique black vertex. This condition is clearly necessary. To prove the condition is sufficient, we can use an idea similar to that used later to prove Proposition 3.4 (details are left to the reader). Bipartite maps will be used in the following to describe branched covering of the sphere, where black and white vertices play very different roles, that's why we need always to distinguish these two kind of vertices. In the following, we always use the following notations: Notation 2.8. Let G be a bipartite map. We denote by: • V G the set of black vertices of G, and by V G the cardinal of V G .

• W G the set of white vertices of G, and by W G the cardinal of W G .

• E G the set of edges of G, and by E G the cardinal of E G .

• F G the set of faces of G, and by

F G the cardinal of F G .
To conclude these definitions, let's introduce the notion of increasing bipartite maps. Definition 2.9. We say that G is a increasing bipartite map if G is a bipartite map with a numbering on each white vertex such that for each black vertex of G, the labels of its adjacent (white) vertices appear in an increasing order counterclockwise.

Notice that an increasing bipartite map can not have multiple edges, i.e. two vertices are connected by at most one edge. There are some examples of increasing bipartite maps in Figure 2 and5. Now that we have introduced the general context in which we will work, we can focus a little more on notions and constructions specific to these maps. First, we define the notion of degree of a face.

Definition 2.10. Let G be a bipartite map, and let f be a face of G. The degree of f , denoted by deg G (f ), or simply deg(f ), is equal to the number of white vertices on the boundary of f , counted with multiplicity. For example, in Figure 2 the unbounded face has degree 7 (the vertex labeled 5 counts twice, whereas the vertices labeled 2 and 3 count only once). Notice that this definition of degree is not the usual one, but is more convenient in this context, the role of the white vertices being predominant in the following.

Then, we can give a relation between the degree of black (resp. white) vertices, the degree of faces and the number of edges of a bipartite map.

Property 2.11. Let G be a bipartite map, then

w∈WG deg G (w) = v∈VG deg G (v) = f ∈FG deg G (f ) = E G .
Proof. As G is bipartite, each edge of G is incident to a unique black (resp. white) vertex, and so we deduce immediately the first relations:

w∈WG deg G (w) = E G = v∈VG deg G (v).
To prove the remaining relation, it suffices to see that the degree of a face f is equals to half of the number of edges incident to f , counted with multiplicity. Then, as each edge is incident to exactly two faces (maybe the same), we deduce the required relation.

Rk: this property is also true if G is a disjoint union of bipartite maps.

Union and intersection

Let H 1 and H 2 be two submaps of a bipartite map G having at least one common vertex. We define the union H 1 ∪ H 2 of H 1 and H 2 to be the unique submap of G constructed by erasing all the vertices, resp. edges, of G that do not belong to

V H1 ∪ V H2 , resp. E H1 ∪ E H2 . In particular, H 1 , resp. H 2 , is a submap of H 1 ∪ H 2 .
Similarly, we define the intersection H 1 ∩ H 2 of H 1 and H 2 to be the submap (or the disjoint union of submaps) of G constructed by erasing all the vertices, resp. edges, of G that do not belong to V H1 ∩ V H2 , resp.

E H1 ∩ E H2 . In particular, each connected component of H 1 ∩ H 2 is a submap of both H 1 and H 2 .
Finally, we give some relations between the number of faces and black vertices of these different maps. But first, we need to define these numbers. Consider two submaps H 1 and H 2 as previously, and denote by L 1 , . . . , L n the connected components of H 1 ∩ H 2 . Then the number of faces of H 1 ∩ H 2 is equal to

F H1∩H2 = n i=1 F Li -1 + 1.
In other words, F H1∩H2 is the number of connected components of S2 \ (H 1 ∩ H 2 ). Similarly, the number of black vertices of H 1 ∩ H 2 is equal to

V H1∩H2 = n i=1 V Li .
Property 2.12. Let H 1 and H 2 be two submaps of a bipartite map G, such that H 1 ∩ H 2 is not empty. Then,

F H1∪H2 = F H1 + F H2 -F H1∩H2 + (n -1) V H1∪H2 = V H1 + V H2 -V H1∩H2 ,
where n is equal to the number of connected components of

H 1 ∩ H 2 .
The proof of this property is not difficult, and is left to the reader. Notice that this result can be generalized to the case where H 1 and H 2 are disjoint, i.e. H 1 ∩ H 2 = ∅, by imposing that F H1∩H2 = V H1∩H2 = 0 and n = 0. In particular, we can generalize the Euler's characteristic for a finite union of disjoint planar maps as follows.

Theorem 2.13. Let G be the union of n disjoint planar maps, for n ≥ 1. Then

V G + F G = E G + 2 + (n -1).

Complements

Let G be a bipartite map, and H ⊂ G, H = G. We consider the two following sets

• M c (H) is the set of (disjoint union of) submap(s) K of G such that H ∩ K = ∅. • M c (H) is the set of (disjoint union of) submap(s) K of G such that H ∪ K = G.
Then, we define the strict complement of H, denoted H c , by

H c = K∈Mc(H) K.
In other words, H c is a disjoint union of submaps 2 of G obtained by erasing the vertices and edges of H, as well as the edges with at least one tip in V H ∪ W H .

Similarly, we define the relative complement of H, denoted H c , by

H c = K∈M c (H) K.
So, H c is the same as H c with the addition of the edges of G not in H but with at least one tip in V H ∪ W H , and the tips of these edges (see Figure 4 for an example). In particular, each connected component of H c is a submap of a connected component of H c .

Figure 4: Example of a full submap (solid edges) of a bipartite map, and its relative complement (dashed edges).

Proposition 2.14. Let G be a bipartite map, and H a submap of G. Suppose that H is not a full submap of G, then there exists a finite number of full submaps

H i of G such that i H i = H and H i ∪ H j = G for any pair i = j.
The minimum number of full submaps H i we need to obtain the equality is called the genus of H. By convention, the genus of a full submap of G is equal to 1.

Proof. We denote by F the set of faces of H not in F G . Then for each f ∈ F , we construct a submap K f of G by erasing each edge and vertex of G except those contained in the face f and its boundary. Then we construct the planar map H f as follows:

H f = H g∈F g =f K g .
Clearly, H is a submap of H f , and H f is a full submap of G. The rest is a direct consequence of the construction of the submaps H f , and is left to the reader.

Hall's marriage theorem

Let A be a set of elements, and S a finite family of finite subsets {A 1 , A 2 , . . .} of A.

Definition 2.15. S has a system of distinct representatives if there exists distinct elements {x 1 , x 2 , . . .} such that x i ∈ A i , for each i = 1, 2, . . . If furthermore card(S) = card ( A i ), we say that S has a perfect matching. Now, we have to determine a condition such that a family of finite sets has a system of distinct representatives.

Definition 2.16. We say that S satisfies the marriage condition if the union of any k of the sets A i contains at least k elements for k = 1, 2, . . . Theorem 2.17. (Hall,[START_REF] Hall | On Representatives of Subsets[END_REF]) S has a system of distinct representatives if and only if S satisfies the marriage condition.

Proof. If S has a system of distinct representatives, then it's evident that S satisfies the marriage condition. Now we prove that the converse is true by induction. If the family S contains only one finite set, the result is obvious. Suppose that the result of the Theorem 2.17 is true for any family containing at most n finite sets, and consider a family S of (n + 1) finite sets {A 1 , . . . , A n+1 } which satisfies the marriage condition. Then two situations can appear:

• The union of any k of the sets of S contains at least (k + 1) elements for k = 1, . . . , n. In this case, we can choose any element of A n+1 as representative of this set, and construct the family S = {B 1 , . . . , B n }, where

B i = A i \ {x n+1 } if x n+1 ∈ A i A i else .
Then S is a family of n finite sets which satisfies the marriage condition. So by induction, S has a system of distinct representatives, and we deduce that S has also a system of distinct representatives.

• There exists a subfamily F of S, F = S, such that there are as many finite sets in F as elements in the union of the sets of F . Up to change the order of the sets in S, we can suppose that F = {A 1 , . . . , A k }.

In this case, as F is a subfamily of S, then F satisfies the marriage condition, so by induction F has a system of distinct representatives. We denote by (x 1 , . . . , x n ) the distinct representatives of F . Now, consider the subfamily G = {A k+1 , . . . , A n+1 }, and construct a new family G = {B k+1 , . . . , B n+1 } where

B i = A i \ {x 1 , . . . , x k }.
Then it's easy to see that G satisfies the marriage condition. In fact, suppose G does not satisfy the marriage condition, so there exists l sets of G such that the union of these l sets contains at most (l -1) elements. Once again, up to change the order of the sets of G, we can suppose that these l sets are B k+1 , . . . , B k+l . In this configuration, we deduce that the union of the k + l sets A 1 , . . . , A k+l contains at most (k + l -1) elements, but this is in contradiction this the fact that S satisfies the marriage condition.

In conclusion, G satisfies the marriage condition, so it has a system of distinct representatives, and the union of the distinct representatives of F and G gives a system of distinct representatives for S.

Balanced maps

The objective of this section is to characterize combinatorially self branched coverings of the sphere by means of a specific kind of maps, namely the balanced maps. The precise statement will be given in Theorem 3.12.

Construction of a map from a branched covering

Let π : S 2 → S 2 be a branched covering of the sphere of degree d. Let A be a set of n distinct points consisting of (or more generally containing) the critical values. Up to postcomposition by an orientation preserving homeomorphism, we can suppose that this set of n points is located at the n-th roots of unity. We represent each point by a white dot, and label these dots from 1 to n such that exp(2iπk/n) gets the label k. Place a black dot at the origin, and trace a radial edge between this black dot and each white dot, so we obtain a connected map. Moreover, this map, denoted by T , is an increasing bipartite map (and more precisely a star-like map since T has only one face and one black vertex).

From now on, we are interested in the pull-back map of T by π. Proof. By construction, we prove easily that Γ is an increasing bipartite map. So the only difficulty is to prove that Γ is a map with d faces. Note that the induced map π : S 2 \ Γ → S 2 \ T is a covering of degree d, and

S 2 \ T is a simply connected open set. Fix a point b ∈ S 2 \ T . Then, for each point x ∈ π -1 (b), the continuous function Id : S 2 \ T → S 2 \ T has a (unique) lift s : S 2 \ T → S 2 \ Γ such that s(b) = x.
Moreover, the function s is a global section of π and defines a homeomorphism of S 2 \ T on the connected component of S 2 \ Γ containing x. So S 2 \ Γ is the union of d simply connected domains.

Moreover, the complement of a union of disjoint simply connected domains in S 2 is necessarily connected. In conclusion, Γ is an increasing bipartite map with d faces. Now, let us give some details about the map Γ. By definition, for each point of the regular set of the branched covering π, there exists an open neighborhood U such that the preimage of U by π is a disjoint union of d open sets, each homeomorphic to U . In other words, each point of the sphere, except the critical values of π, has exactly d distinct preimages by π. In particular, the black vertex and each edge of T has d preimages by π. So Γ is an increasing bipartite map consisting of d faces, n • d edges and d black vertices. Moreover, the degree of each face and black vertex of Γ is the same, equals to n.

Finally, as the passport of π describes the behavior of each of its critical value, it's easy to see that the number of white vertices of Γ is equal to the number of integers in the passport of π.

A direct consequence of this last theorem is the Riemann-Hurwitz condition that a passport must satisfy to be realizable. In fact, by Theorem 3.1 and as π is a branched covering of degree d, Γ is a connected map with d faces, n • d edges and d black vertices. So if we denote by m the number of white vertices of Γ, given by the passport of π, then by the Euler characteristic, we have

(d + m) + d = d • n + 2 and so 2d -2 = d • n -m = ν(D(π)).
Definition 3.2. We call Γ a representation of the branched covering π.

Thus we have a first model of a branched covering by a geometrical object. Nevertheless, this object is actually too complicated and so from now on, our goal is to simplify it without losing important information to be able to solve some realizability problems of given passports. For that, we use two maps in order to reduce the complexity of Γ, and then we prove in the next subsection that we can combine these two ideas.

First, let's see what happens if we erase each 1-valence (automatically white) vertex and its attached edge of Γ. As Γ is an increasing bipartite map with as many black vertices as faces, each of degree n, and with white vertices labelled from 1 to n, then by erasing every 1-valence vertex of Γ, we obtain a unique increasing bipartite map with the same properties as Γ except those about the degree of each black vertex and face.

Conversely, if we consider such a map, it's simple to reconstruct our representation Γ (cf Figure 6 for an example). In conclusion, we have a first bijection that allows us to simplify our representation. We call this map the labeled skeleton of the branched covering π. An alternative possibility is to erase the label of each white vertex of Γ such that we obtain a unique bipartite map, denoted by Γ, with as many black vertices as faces, each of degree n. We call these maps a n-regular skeleton of the branched covering. Conversely, consider such a map Γ, we prove the following proposition: Proposition 3.3. Every bipartite map with equal number d of faces and black vertices, each of constant degree n, comes from a representation of a branched covering of degree d, with at most n distinct critical values.

For that, we first need to transform Γ by changing each black vertex and the n edges coming from this vertex by a black n-gon (cf Figure 7 for an example), so we obtain a n-regular map, i.e. a map in which each face is of degree n, denoted by Γ r . Notice that Γ r has two kinds of faces (those containing black vertices and those that are blank) and the two kinds alternate like a chessboard. So we can orient the edges of Γ r keeping black faces to the left. Now, choose a vertex v of Γ r (i.e. a white vertex of Γ), and label it by 0. Then we label all other vertices by the directed edge-distance from v modulo n, i.e. the number of edges we need to pass through following the edge-orientation of Γ r . Notice that this labeling depends on the choice of the first vertex v.

Proposition 3.4. This labeling is well-defined 3 .

3 One can prove easily this result using an argument of cohomology, but here we choose to avoid such a theory.

Proof. We have to prove that for any given vertex w of Γ r , the label of w is independent of the choice of a directed path from v to w, i.e. two paths from v to w have the same length modulo n. Consider two directed paths, denoted by γ 1 and γ 2 , from v to w, and a directed path γ from w to v, preserving the orientation of Γ r , so that the concatenation γ • γ i of γ and γ i gives a closed path, for i = 1, 2.

Let us fix an index i = 1 or 2. If γ ∩ γ i = {v, w}, then γ • γ i is a 'gluing' of some Jordan curves, and so up to study each Jordan curves separately, we can suppose that γ ∩ γ i = {v, w}, i.e. γ • γ i defines a Jordan curve. In consequence, γ • γ i divides the set F Γr into two subsets: one containing the faces to the left of γ • γ i , and the other containing the faces to the right of γ • γ i .

For the following, we consider the function

ω : F Γr → R[E Γr ] f → ε f • a∈EΓ r ∩∂f a ,
with ε f = 1 if f is a black face, and ε f = -1 else. Then, if we denote by ω(γ • γ i ) the sum of all the edges (with coefficient 1) passed through by γ • γ i , and by F ext the set of the faces to the left of γ • γ i , we prove easily that:

ω(γ • γ i ) = f ∈Fext ω(f ).
This last result implies that the length of the path γ

• γ i (modulo n) is equal to f ∈Fext a∈EΓ r ∩∂f 1.
As each face of Γ r is of degree n, we deduce that the length of γ • γ i is equal to 0 modulo n, i.e. the length of γ plus the length of γ i is equal to 0 modulo n.

In conclusion, γ 1 and γ 2 have the same length modulo n. So, the n-regular map Γ r admits a labeling which can be transported to a labeling of the map Γ. Moreover, the map Γ equipped with this labeling is an increasing bipartite map with equal number of faces and black vertices, each of constant degree. From this, one can construct a branched covering with Γ as a representation.

In conclusion, there is a bijection between the set of n-regular maps and the set of representations of branched coverings with n critical values up to the cyclic action of the permutation (1 2 • • • n) on the label of the representation.

Definition

In the previous subsection, we proved the existence of two different applications (a bijection and a surjection) in order to reduce the complexity of the map Γ. Obviously, we want to know if we can combine the two ideas used previously. So, let Γ be a representation of a branched covering, and denote by G the map obtained by erasing the label and each 1-valence white vertex with its unique incident edge. Definition 3.5. We call G a skeleton of the branched covering π. Notice that the function that sends a representation Γ to a skeleton G is not injective, in the sense that we can construct the representations of two different branched coverings that are sent to the same skeleton. For example, we can relabel by 7 one of the white vertices initially labeled by 1 in Figure 6. This changes the representation Γ and the associated branched coverings, but not the skeleton G.

By construction, G is a bipartite map, and so now a natural question is: which bipartite map comes from a skeleton of a branched covering? To answer this question, motivated by W. Thurston's treatment of the generic case, we introduce the following notion for bipartite maps: Definition 3.6. A bipartite map G is called a balanced map, or we just say that G is balanced, if it satisfies the following two conditions.

• (global balance condition) G has as many faces as black vertices. We say that G is globally balanced.

• (local balance condition) for each submap H containing at least one black vertex, the number of black

vertices of H is greater than or equal to the number of faces of H, i.e. V H ≥ F H . We say that G is locally balanced.

A star-like bipartite map with a central black vertex is a balanced map. A map with one vertex of each color and two edges (therefore two faces) is not balanced. A quadrilateral (i.e. a topological model of a square) is the simplest example of a balanced map that is not a tree. Some further examples of balanced maps can be found in Figures 1 and8.

By construction of a skeleton G, the global balance condition is natural (as this condition is still satisfied by the map Γ), but not sufficient to define a skeleton. We prove later that this condition is equivalent to the Riemann-Hurwitz condition (cf Proposition 4.1). This correlation between the two conditions allow us to make a connection between our model and the passport of a branched covering.

Notice that by definition, if G is a bipartite map that satisfies the local balance condition, and H ⊂ G with at least one black vertex, then H also satisfies the local balance condition.

Lemma 3.7. Let G be a bipartite map, and suppose that G is globally balanced. If for each full submap H with at least one black vertex, we have the inequality

V H ≥ F H then G is balanced.
In other words, we just need to verify the local condition for each full submap of G. Depending on the situation, we prefer to use Definition 3.6 rather than Lemma 3.7.

Proof. Let H be a non full submap of G with at least one black vertex. We want to prove that F H ≤ V H . First, by Proposition 2.14, there exists a finite number n of full submaps of G, denoted by H 1 , . . . , H n , such that i H i = H and H i ∪ H j = G for any pair i = j.

Then, by hypothesis,

F G = V G F Hi ≤ V Hi , for i = 1, . . , n.
So, using Property 2.12, we deduce that for each pair (i, j) ∈ {1, . . . , n}, i = j,

F Hi∩Hj = F Hi + F Hj -F G ≤ V Hi + V Hj -V G = V Hi∩Hj .
By induction, we prove similarly that the intersection of any number of maps H i satisfies the same relation. In particular, we have

F H = F Hi ≤ V Hi = V H .
Suppose now that H has k connected components L 1 , . . . , L k . If one of them does not contain black vertices, then it does not contain any edges so has a single white vertex. Erasing this connected component with not change the number of black vertices nor that of faces. Erasing now all the single-white-vertex connected components, each remaining connected component contains a black vertex (and there is at least one such component). So we may as well assume that each L i , i = 1, . . . , k, contains at least one black vertex.

Then, using the previous result, we have

V Li ≥ F Li ∀i = 1, . . . , k.
By Property 2.12, we deduce that

V H = k i=1 V Li ≥ k i=1 F Li ≥ k i=1 F Li -k + 1 = F H .
We end this subsection by a last proposition on balanced maps.

Corollary 3.8. Let G be a balanced map, and F be a subset of F G , F = F G . Denote by V the subset of V G that contains every black vertex having an incidence with a face of F , and by F , resp. V , the cardinal of F , resp. V. Then F < V .

Proof. By erasing the vertices and edges of G that are not incident to a face of F , we construct a submap (or a disjoint union of submap) of G. Without loss of generality, we can suppose that this construction gives a submap H of G. By construction, the number of vertices of H is equal to V and the number of faces of H is equal to F + 1. As G is locally balanced, we deduce immediately by Definition 3.6 that F + 1 ≤ V .

From balanced maps to balanced graphs

The goal of this subsection is to give some basic results about balanced maps in order to manipulate this notion.

Proposition 3.9. Let G be a balanced map. Then a white vertex w of G can not be doubly incident to any face of G. In particular, no edge of G is doubly incident to a face, except if the white tip is of degree 1. Moreover adding or erasing some 1-degree white vertices together with its attached edge changes neither the global nor the local balance condition.

Proof. Let us argue by contradiction. Suppose that there is a Jordan arc inside a face forming a Jordan curve γ with a white vertex w, with γ separating the black vertices of G. Erasing the vertices and edges of G in each complementary component of γ gives two submaps G 1 and G 2 . We have G = G 1 ∪ G 2 , and G 1 ∩ G 2 is reduced to a single white vertex. As G 1 and G 2 are submaps of G containing black vertices, and G is locally balanced, we deduce that

F Gi ≤ V Gi , for i ∈ {1, 2}. (2)
Thus, by construction,

F G = F G1 + F G2 -1 ≤ V G1 + V G2 -1 = V G -1 < V G .
This contradicts the fact that G is globally balanced. The rest of the proposition is obvious.

So, a bipartite map that satisfies both global and local conditions has some constraints. The next result gives another point of view about the balanced conditions. Theorem 3.10. Let G be a bipartite map. Then G is globally balanced if and only if

w∈WG (deg G (w) -1) = 2V G -2.

Similarly, G is locally balanced if and only if for each submap H of G, we have

w∈WH (deg H (w) -1) ≤ 2V H -2.
The reader may notice some similarity with the Riemann-Hurwitz condition. More exactly, using Theorem 3.12, we can prove that there exists a relation between the Riemann-Hurwitz condition for branched data and the global balance condition for balanced maps.

Proof. Let G be a bipartite map. By Euler characteristic, we have

F G + (V G + W G ) = E G + 2, thus E G -W G = F G + V G -2. (3)
Now, as each edge of G belongs to one and only one white vertex, the definition of the degree of a vertex implies that

w∈WG deg G (w) = E G .
From this relation and equality (3), we deduce that

w∈WG (deg G (v) -1) = E G -W G = F G + V G -2. ( 4
)
Therefore

F G = V G ⇐⇒ w∈WG (deg G (v) -1) = 2V G -2 (5)
and

F G ≤ V G ⇐⇒ w∈WG (deg G (v) -1) ≤ 2V G -2 (6)
Applying ( 5) to G, we can still deduce the required condition such that G is globally balanced. Now, assume that G is locally balanced, and let H be a submap of G. Then by definition, we have the relation

F H ≤ V H . Applying (6) to H we get w∈WH (deg H (v) -1) ≤ 2V H -2.
Conversely assume that the above inequality holds for every submap H of G. Then applying (6) to H, we deduce immediately that G is locally balanced. This result is important as it implies that the concept of balanced map may be defined using only the vertices and the edges of the map. In particular, it implies the following result.

Corollary 3.11. Let G 1 and G 2 be two bipartite maps, and suppose that G 1 and G 2 are equivalent as graphs. Then G 1 is globally (resp. locally) balanced if and only if G 2 is globally (resp. locally) balanced.

Generalization of Thurston's result

In this subsection, we finally answer our initial question: determine the bipartite maps that are skeletons of branched coverings. Theorem 3.12. A bipartite map G is a skeleton of a branched covering if and only if G is a balanced map.

Proof. To prove this Theorem, we need to come back to the construction of G. In fact, if G is a skeleton of a branched covering, then there exists a representation Γ, i.e. an increasing bipartite map with as many black vertices as faces each of the same degree, such that G = φ(Γ). Moreover, we prove in subsection 3.1 that a representative is essentially defined by a regular planar map, or equivalently by a bipartite map Γ with as many black vertices as faces, each of the same degree (we simply erase the labeling of the map Γ). In conclusion, if G is a skeleton of a branched covering, then by adding some 1-degree white vertices and edges to G, we can construct a map Γ. Conversely, if such a construction is possible, then G is a skeleton of a branched covering.

First, suppose that G is a balanced map with n white vertices, and add inside each face f of G a number of white dots such that the number of these dots plus the number of white vertex having an incidence with f is equal to n. Notice that by Proposition 3.9, the number of white vertex having an incidence with a given face of G is equal to the degree of this face. Now, we want to prove that we can connect each of these added dots to a black vertex having an incidence with the same face f by an edge in order to obtain a map where each black vertex is of degree n, and so the construction mentioned earlier is possible.

In order to prove this result, consider A the set containing all the black vertices v of G, each repeated (ndeg G (v)) times, and denote by S a family of finite subsets {A 1 , A 2 , . . .} of A where each subset A i corresponds to a white dot w and contains all the black vertices v of G (counted (ndeg G (v)) times) that can be connected to w. Then our construction is possible if and only if S is a perfect matching. So, let's prove that the family S is a perfect matching.

Denote by A the cardinal of A, and by S the cardinal of S. By definition, we have

A = v∈VG (n -deg G (v)) = n.V G - v∈VG deg G (v),
and

S = f ∈FG (n -deg G (f )) = n.F G - f ∈FG deg G (f ).
Moreover, as G is a bipartite map, then

f ∈FG deg G (f ) = v∈VG deg G (v) = E G ,
as each edge of G is incident to a unique black vertex. In conclusion, we have the relations

A = n.V G -E G , (7)
S = n.F G -E G . ( 8
)
As G is a balanced map, then V G = F G , and so using relations (7) and (8) we can conclude that A = S. Now, we just have to prove that S satisfies the marriage condition. Consider S ′ a subfamily of S, and denote by A ′ the subset of A containing each element of A that belongs to at least one subset of S ′ . Finally, denote by S ′ , resp. A ′ , the cardinal of S ′ , resp. A ′ . Then, we have to prove that S ′ ≤ A ′ . Up to adding some subsets of S into S ′ , we can suppose that if a subset A i corresponding to a white dot w belongs to S ′ then each other subset corresponding to a white dot in the same face of G as w also belongs to S ′ , as this operation does not increase the value A ′ .

Then, there exists a subset F of F G such that the family S ′ corresponds to all the white dots belonging to a face of F . We denote by V the subset of V G that contains each black vertex having an incidence with a face of F . Now consider the submap H of G obtained by erasing each edge of G that is not incident to a vertex of V, as well as each vertex that is not incident to one of the remaining edges. Clearly, by construction, we have

V = V H and F ⊂ F H .
Let's prove our inequality. By definition, we have

A ′ = v∈V (n -deg G (v)) = v∈VH (n -deg H (v)) = n.V H - v∈VH deg H (v) = n.V H -E H . (9)
So, we can deduce that

S ′ = f ∈F (n -deg G (f )) = f ∈F (n -deg H (f )) ≤ f ∈FH (n -deg H (f )) = n.F H -E H ≤ n.V H -E H , as G is locally balanced.
In conclusion, using the relation (9), we have S ′ ≤ A ′ and so S satisfies the marriage condition.

Conversely, suppose that G is a skeleton of a branched covering, then by adding some 1-degree white vertices and edges to G, we can construct a bipartite map Γ such that each black vertex and face have the same degree n. As previously, consider A the set containing all the black vertices v of G, each repeated (ndeg G (v)) times, and denote by S a family of finite subsets {A 1 , A 2 , . . .} of A where each subset A i corresponds to a 1-degree white vertex w of Γ and contains all the black vertices v of G (counted (ndeg G (v)) times) being incident to the same face as w. The existence of the map Γ implies that S is a perfect matching.

Denote by S, resp. A, the cardinal of S, resp. A. By definition, S and A satisfy the relations (7) and (8), and as S is a perfect matching, S = A. So we can still deduce that F G = V G , i.e. G is globally balanced. Now, consider a full submap H of G with at least two faces, H = G, and denote by f H the unique face of H that is not a face of G. Then, let S ′ be the subfamily of S that corresponds to all the 1-degree white vertices of G belonging to a face of F H \ {f H }, and A ′ be the subset of A containing each element of A that belongs to at least one subset of S ′ . Then, we prove easily that

S ′ := card(S ′ ) = f ∈FH \{fH } (n -deg G (f )), = f ∈FH \{fH } (n -deg H (f )). Thus, S ′ = n.F H -A H -(n -deg H (f H )). (10)
Similarly, we have

A ′ := card(A ′ ) = v∈VH (n -deg G (v)) ≤ v∈VH (n -deg H (v)),
and so

A ′ ≤ n • V H -A H . (11)
condition, mentioned in the introduction of this article, is a necessary condition for the realizability of a given branch datum D of degree d. Then, we consider another invariant: the ramification distribution. In particular, we prove that there exists a surjection from the set of branched coverings of degree d to the set of ramification distribution of degree d.

Let D = [Π 1 , . . . , Π n ] be a branch datum of degree d, where each Π i = [k 1 , . . . , k ni ] is a partition of d. We recall that the branched weight of D is equal to

ν(D) = n i=1 ν(Π i ), with ν(Π i ) = ni j=1 k j -1. Proposition 4.1. (Riemann-Hurwitz condition) If D is realizable then ν(D) = 2d -2.
Proof. As D is realizable, there exists a branched covering of the sphere π : S 2 → S 2 of degree d such that D = D(π). Denote by G a skeleton of π. Then by Theorem 3.12, G is balanced so it has exactly d black vertices and d faces, and moreover the values k i > 1 in the different partitions of D correspond to the degree of the white vertices of G. Now, by Euler characteristic (Theorem 2.13), we have:

(V G + W G ) + F G = E G + 2.
So, as G is globally balanced,

E G -W G = V G + F G -2 = 2V G -2 = 2d -2.
Moreover, by Property 2.11, we have the relation Notice that we don't use the local balanced condition of G to prove that the Riemann-Hurwitz condition is a necessary condition. So, as a skeleton of a branched covering is necessarily a globally and locally balanced map, we can deduce that the Riemann-Hurwitz condition is not a sufficient condition. So now, the natural question is to succeed in translating the local balanced condition on the bipartite map into a condition on the passport in order to find a necessary and sufficient condition for the Hurwitz problem.

E G = w∈WG deg (
Nevertheless, such a relation is not so simple as a passport has no information about the structure of the map G. More exactly, a given passport can correspond to several bipartite maps, as a passport has just information about the degree of white vertices. Conversely, a balanced map has no information on the number of critical values of the branched covering, and so a balanced map also corresponds to several passports. That's why we consider the following problem: let (a i ) be a ramification distribution of degree d, can we construct a realized passport of degree d using the values a i ?

First, we give a matrix interpretation of the balanced condition by using Theorem 3.10, and Corollary 3.11.

In fact, by Corollary 3.11, if G is a balanced map, then each map equivalent (as graph) to G is also balanced. So, we can restrict our study to graph structure. The interest is that we can associate to a given bipartite graph a white-to-black incident matrix A = (a i,j ) by the following construction: enumerate separately the white and black vertices. Then, the coefficient a i,j is equal to the number of edges having the white vertex i and the black vertex j as tips. Conversely, it's simple to construct a bipartite graph from a matrix containing only non-negative integers by using the same construction. Another interest of this construction is that the degree of a white (resp. black) vertex is just the sum of each coefficient in the corresponding line (resp. column). Now, the main idea is to construct a "good" matrix that corresponds to a given ramification distribution l.

We will denote by M m,d ({0, 1}) the set of m × d matrices whose entries are either 0 or 1.

Definition 4.2. Let l = (a 1 , . . . , a m ) be a ramification distribution of degree d. We say that a matrix A ∈ M m,d ({0, 1}) is a matrix representation of l if for all i, the i-th line of A contains exactly a i values 1.

For example, a matrix representation of the ramification distribution (2, 2, 2, 2, 2, 2) of degree 4 is given in Figure 9.

        1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1        
m i=1   max   1, k j=1 a i,dj   -1   ≤ 2k -2 and m i=1   d j=1 a i,j -1   = 2d -2.
For example, the previous matrix representation of (2, 2, 2, 2, 2, 2) satisfies the balanced condition. The reason of the maximum between 1 and the sum is to avoid the line whose each coefficient a i,dj = 0. Now, using Theorem 3.10, we prove that this condition for a matrix is equivalent to the balanced conditions for a bipartite map. Proof. Notice first that as the sum of each coefficient in a given line is equal to the degree of the corresponding white vertex, the following condition Conversely, suppose that the matrix A satisfies the balanced condition. Left to choose a representation of G on the sphere, we can suppose that G is a planar map. We still prove that G is globally balanced using Proposition 4.1. Now, let's prove that G is also locally balanced. Let H be a submap of G, then we can associate a matrix to H as previously. Moreover, this matrix is just a submatrix of A, i.e. is obtained by erasing some columns and lines of A. In particular, we deduce that there exists integers d 1 , . . . , d k , where k is the number of black vertices of H, such that As A satisfies the balanced condition, we deduce that w∈WH (deg H (w) -1) ≤ 2k -2 = 2V H -2. By Theorem 3.10, we deduce immediately that G is locally balanced. Now, we can finally answer our initial question: Theorem 4.5. Let l = (a 1 , . . . , a m ) be a ramification distribution of degree d. Then there exists a branched covering of degree d thus the ramification number are given by l.

Proof. Consider the matrix A ∈ M m,d ({0, 1}) constructed by the following recursive process: first place in the first line of A a value 1 in each column from 1 to a 1 . Now, suppose we still construct the i first lines of A and denote by b j the value a 1 + . . . + a jj + 1, for j = 1, . . . , n. We suppose that b 0 = 1. If b i < d, place in the (i + 1)th line of A a value 1 in each column from b i to b i+1 , by coming back to 1 if the number of the column exceeds d. Else place a value 1 in each column from b id + 1 to b i+1d + 1. By doing this process, we construct a matrix representation A of l. See for example the previous matrix representation of (2, 2, 2, 2, 2, 2) in Figure 9, or the example in Figure 10. Now we have to prove that this matrix satisfies the balanced condition. Obviously, we still know that

m i=1   d j=1 a i,j -1   = m i=1 [a i -1] = 2d -2,
as l is a ramification distribution of degree d. To prove the inequalities, we need to notice two points coming from the construction of A. The first point is that a m,d = 1, i.e. the last value 1 we place by our process is always in the last column of A. Moreover, we reach the last column of A exactly twice. This first point comes directly from the property satisfied by l:

m i=1 [a i -1] = 2d -2.
In particular, each column of A has necessarily 2, 3 or 4 values 1. The second point is a consequence of the first one: for any two columns j, k of A, with j = k, there exists at most two lines such that a i,j = a i,k = 1. In other words, the inner product of the two columns is at most equals to 2. Then, it's not difficult to prove that A satisfies the balanced condition using these two properties. Moreover, the graph coming from A is clearly planar using Kuratowski's theorem [START_REF] Kuratowski | Sur le problème des courbes gauches en topologie[END_REF]. We can also prove directly the graph is planar by constructing it with a similar process as the one proposed to construct the matrix A (see Figures 9 and 10 for some explicit examples).

Finally, using Theorem 4.4, we prove that there exists a balanced map corresponding to the matrix A (and so to the ramification distribution l), and so by Theorem 3.12, we deduce the wanted result.

Figure 1 :

 1 Figure 1: Example of a bipartite map G

Figure 2 :

 2 Figure 2: Example of an increasing bipartite map.

Figure 3 :

 3 Figure 3: Example of a non-full submap (solid edges) of a bipartite map (both solid and dashed edges).

Figure 5 :

 5 Figure 5: Example of the representation Γ of a branched covering π of degree 7.

Figure 6 :

 6 Figure 6: Example of the increasing bipartite map obtained by erasing all the 1-degree vertices of Γ.

Figure 7 :

 7 Figure 7: Example of the bipartite map obtained by erasing the labels of Γ.

Figure 8 :

 8 Figure 8: Example of a skeleton of a branched covering π of degree 7.

  w), and so 2d -2 = E G -W G = w∈WG deg(w) -W G = w∈WG (deg(w) -1).

Figure 9 :

 9 Figure 9: Example of a matrix representation of (2, 2, 2, 2, 2, 2) and its associated graph. Then, we define a balanced condition for our matrix A as follows: Definition 4.3. We say that a matrix A ∈ M m,d ({0, 1}) satisfies the balanced condition if for any choice of k(≥ 1) distinct columns d 1 , . . . , d k of A, we have

Theorem 4. 4 .

 4 Let A ∈ M m,d ({0, 1}) be the incident matrix of a planar bipartite graph G. Then G is balanced if and only if A satisfies the balanced condition.

  same as the Riemann-Hurwitz condition. So, using Proposition 4.1 if G is globally balanced, then this condition is satisfied. The converse is obviously true. Now, suppose that G is balanced. We want to prove that A satisfies the balanced condition. Choose arbitrarily k < d columns of A, denoted d 1 , . . . , d k . By definition of A, each column corresponds to a black vertex of G. So, consider the submap (or the disjoint union of submaps) H of G constructed by erasing each black vertices of G except those corresponding to the columns d i of A, as well as the edge coming from these vertices. Then, by applying Theorem 3.10 in each disjoint component of H, we deduce that:w∈WH (deg H (w) -1) ≤ 2V H -2 = 2k -2.Moreover, by construction, we have deg H (w) = k j=1 a i,dj , for a fixed i. And so, w∈WH (deg H (w) -1) =

Figure 10 :

 10 Figure 10: Example of a matrix representation of (3, 3, 2, 2) and its associated graph.

partially supported by ANR-13-BS01-0002, project LAMBDA

Hc can have multiple connected components

Acknowledge: I am grateful to Dylan Thurston and Gilles Schaeffer for many useful conversations. I also thank Tan Lei for introducing the subject, and for her constant help during the preparation of this work.

Moreover, as S satisfies the marriage condition, then S ′ -A ′ ≤ 0, and so using relations (10) and (11), we have 0

Finally, we deduce that

In conclusion F H ≤ V H , and so G is locally balanced.

A direct consequence of this geometric interpretation of a branched covering of the sphere, and of the Proposition 3.9 is the following result.

Corollary 3.13. Let π be a branched covering of the sphere S 2 , and U a simply connected subset of S 2 containing at most one critical value of π. Then the pull-back of S 2 \ U by π is connected.

Proof. Let V = S 2 \ U . As U is simply connected and contains at most one critical value of π, then we can construct a star-like map T with a unique black vertex representing a regular point of π, and each branched point of π in V is associated with a white vertex. Now consider the pull-back of T by π. Notice that this construction is similar to the one in section 3.1, except here we remove (at most) one of the branched point. Then, by Proposition 3.9, each white vertex of a balanced map is incident to a face at most once, so erasing a white vertex and its associated edge in the construction of the balanced map does not change the connectivity of the pull-back map. In conclusion, the pull-back of T by π is a connected map, and so, the pull-back of S 2 \ U by π is also connected.

Summary

From a representation Γ of a branched covering, we create two different bipartite maps: a n-regular skeleton, i.e. a globally balanced map whose all the black vertices and faces are of degree n, and an increasing skeleton, i.e. an increasing, globally balanced map without 1-valence vertices. More exactly, we define a surjection from the set of representations of a branched covering to the set of n-regular skeletons, whose the fiber is generated by the action of the permutation (1 • • • n) on the labels of the representation. And we define a bijection between the set of representations and the set of increasing skeletons.

Then, by composing the two previous applications, we define a surjection between the set of representations and the set of skeletons, and we prove in Theorem 3.12 that a skeleton defines a unique balanced map (here, a balanced map is supposed without 1-valence vertices). In the following, there is a summary of the relationships between the different sets of maps considered in this section. The main result of this section is to give a matrix interpretation of the balanced conditions we defined in the previous sections. First, we come back to the Hurwitz problem, and reprove that the Riemann-Hurwitz


Giulio Cerruti
email: gcerruti@aldebaran.com

Damien Chablat
email: damien.chablat@irccyn.ec-nantes.fr

David Gouaillier
email: dgouaillier@aldebaran.com

Sophie Sakka
email: sophie.sakka@irccyn.ec-nantes.fr

Design method for an anthropomorphic hand able to gesture and grasp

Keywords: robotic hand, gesture, hand dexterity, Kapandji test, thumb opposability, grasping

This paper presents a numerical method to conceive and design the kinematic model of an anthropomorphic robotic hand used for gesturing and grasping. In literature, there are few numerical methods for the finger placement of human-inspired robotic hands. In particular, there are no numerical methods, for the thumb placement, that aim to improve the hand dexterity and grasping capabilities by keeping the hand design close to the human one. While existing models are usually the result of successive parameter adjustments, the proposed method determines the fingers placements by mean of empirical tests. Moreover, a surgery test and the workspace analysis of the whole hand are used to find the best thumb position and orientation according to the hand kinematics and structure. The result is validated through simulation where it is checked that the hand looks well balanced and that it meets our constraints and needs. The presented method provides a numerical tool which allows the easy computation of finger and thumb geometries and base placements for a human-like dexterous robotic hand.

I. INTRODUCTION

The human hand is an astonishingly advanced mechanism which is too complicated to be faithfully replicated. Many techniques are used to model its kinematics, such as direct measurements of the human limbs or optimization algorithms. Currently, the most accurate hand model ever built is the anatomically-correct testbed (ACT) [START_REF] Vande Weghe | The act hand: design of the skeletal structure[END_REF]. In this design, the structure was machined with the same shape and mass to that of the human bones, and the joints were designed to preserve the same DoFs and passive stiffness of the human joints. However, the ACT is conceived to deeply investigate the human hand structure, function and control for medical purposes. Its complexity hinders the practical use of the artifact in robotics. In general, simplified joint structures and link shapes are commonly chosen by robotic hand designers. Furthermore, the number of independent DoFs are usually reduced due to technological limits (hardware and software) and mechanical constraints. Each human hand has its own peculiarities, and yet, its functional capabilities do not significantly change from the others. This implies that different link lengths, width and joint placements do not greatly alter the hand performance. As a consequence, no true optimal design exists for the construction of a human-like robotic hand. Nevertheless, an appropriate model has to be realized in order to fulfill all functional requirements: the hand is supposed to be able to express emotions and give information through gestures, grasping objects and manipulating them. These abilities require high interaction among fingers, in particular between each finger and the thumb. Therefore, finger geometry and kinematics are less important than the thumb kinematics and its interaction with the opposed fingers. Our project aims to design a self-contained human-inspired hand with following constraints: have the size and weight similar to a 6 years old child's hand (length approximately 120 mm and weight less than 0.6 Kg) in order to be embodied on a humanoid robot of a comparable height, be able to grasp small objects (such as a full soda can) and perform gestural communication (e.g. thumb-up, ok, pointing and counting). This document is the first step in the design process for which we solve geometric problems only. Section II presents a literature review on human hands and existing robotic hands. It will be shown that no hand that meets our constraints exists. Sections III addresses the problem presenting the kinematic aspects of our hand. Section IV proposes a new design method to place the thumb base in order to fulfill the required functional capabilities. Finally, results are discussed in Section V and conclusions are drawn in Section VI.

II. LITERATURE REVIEW

A. The human hand 1) Hand skeleton: The human hand is composed of 27 bones [START_REF] Van Der Hulst | A functional anatomy based kinematic human hand model with simple size adaptation[END_REF] which make up its three main parts: wrist, palm and fingers (Figure 1). The wrist is formed by 8 small bones called carpals which join the ulna and radius forearm bones to the hand. The palm is composed by 5 bones called metacarpals which connect the fingers and the thumb to the wrist. The joints between the wrist and the finger metacarpals are called the carpometacarpal (CMC) joints while the one linking the metacarpal of the thumb is called the radiocarpal (RC) joint. Each finger is composed by 3 long bones called phalanges whose names are given according to their distance to the palm: proximal, middle and distal. The proximal phalanx (PP) is linked to the metacarpal bone through the metacarpophalangeal joint (MCP) while the remaining phalanges are connected to each other through the interphalangeal joints. The joint between the proximal and the middle phalanx is the proximal interphalangeal joint (PIP) while the joint closest to the end of the finger is the distal interphalangeal joint (DIP). The thumb has one bone less with respect to the fingers (no middle phalanx) and it consequently has one interphalangeal joint plus the MCP joint.

2) Hand kinematics: The hand joints are classified into three main types: hinge (1 DoF), condyloid (2 DoFs) and saddle (2 DoFs) joints. The hinge joints on the human hand are the CMC, PIP and the DIP joints. They allow the fingers to flex (move toward the palm) and to extend (move further from palm). The condyloid joints are the finger MCP joints that allow flextion/extension and abduction/adduction of the fingers, the latter being the motion of spreading and gathering them. Hence, each finger can be represented as a kinematic serial chain of 5 DoFs: 1 at the CMC, 2 at the MCP, 1 at the PIP and a last one at the DIP. Finger PIP and DIP joints are orthogonal to the bone axis when the phalanx is fully extended and they progressively bend toward the middle (due to the bone surface) while flexing. As a result, all fingers converge to a common point improving the opposition of the thumb to the ring and little fingers. According to Vitruvian man's hand and the study conducted by Isobe [START_REF] Isobe | Hand position[END_REF], human fingertips approximatively lie on a common circle when abducted. The circle has a radius equal to the middle finger length and it is centered at the MCP joint of the middle finger. The thumb has the same number of DoFs of fingers but differently distributed: the RC joint is a saddle joint, the MCP is a condyloid joint and the IP joint is a hinge joint [START_REF] Giurintano | A virtual five-link model of the thumb[END_REF]. The thumb is the only finger able to turn and oppose to the other four fingers. The opposability of the thumb enables humans to grip and hold objects that they would not be able to take otherwise. Figure 2 shows the summarized DoFs of the human hand plus a further DoF in the palm that represents the small motions that occur among the carpal bones while flexing the wrist. However, some joints are relatively immobile due to the interousseous ligaments that stabilize the hand joints. The CMC joints at the bases of the index, middle and ring metacarpals can be neglected and the small intra-carpal motions can be collected into the wrist motion. Note that the CMC joint of the little finger should not be omitted since it forms the hollowed shape of the palm [START_REF] Norkin | Joint structure & function a comprehensive analysis[END_REF] when the little finger moves in opposition to the thumb. Not all DoFs in the human hand are independent. Tendons couple some joint like the PIP and DIP joints of the fingers. In the next paragraphs we will refer to the independent DoFs simply as DoFs.

B. Robotic hands

The number of joints and DoFs of human-inspired robotic hands is generally chosen according to the tasks for which they are conceived. For instance, robotic hands oriented to reproduce the human hand manipulation capabilities adopt nearly the same kinematic structure presented in the previous paragraph. Excluding the wrist, the Shadow Dexterous Hand [START_REF] Ltd | Shadow hand. Website[END_REF] has 18 independent DoFs, 5 of which are dedicated to the thumb, with the PIP and DIP joints coupled. The Awiwi hand, mounted on the DLR Hand Arm System [START_REF] Grebenstein | The dlr hand arm system[END_REF], has even more independent DoFs [START_REF] Bicchi | Modeling natural and artificial hands with synergies[END_REF]: its PIP and DIP joints of the index and middle are not coupled and it has a simplified thumb with 4 joints and 4 DoFs. The UB Hand IV [START_REF] Melchiorri | Development of the ub hand iv: Overview of design solutions and enabling technologies[END_REF] and DLR/HIT Hand II [START_REF] Liu | Multisensory five-finger dexterous hand: The dlr/hit hand ii[END_REF] (15 DoFs) do not include the CMC joint of the little finger in their kinematic models and their thumbs have 4 joints with the MCP and the IP coupled. Robotic hands designed only for grasping require less complex kinematic models with less joints and DoFs. Generally they have all finger joints coupled, the CMC joint of the little finger coupled with the thumb base motion and fingers with no abduction/adduction motion (MCP with 1 DoF). The Harada Robot Hand [START_REF] Keymeulen | Investigation of the harada robot hand for space[END_REF], for instance, has only 14 joints (3 per finger and 2 for the thumb) and 5 DoFs: 1 DoF per finger and 1 DoF for the thumb. Another example is the Prensilia IH2 Azzurra hand [START_REF] Srl | Ih2 azzurra series[END_REF] that has 11 joints, 5 of which actuated: 2 DoFs for the thumb, 1 DoF for index and middle and the last DoF for both ring and little fingers. Robotic hands that aim to both manipulate and grasp find a compromise between hand motion capabilities and control complexity. Among these we find hands such as the Robonaut II Hand [START_REF] Bridgwater | The robonaut 2 hand -designed to do work with tools[END_REF], Elu2-Hand [START_REF] Ltd | Elumotion robotic hand 2. Website[END_REF] (Shunk hand) and the iCub hand [START_REF] Schmitz | Design, realization and sensorization of the dexterous icub hand[END_REF]. Table I lists the DoFs and the weight of the aforementioned hands and it specifies if hands fully embed their actuators and electronic components. As it can be seen, none of them fulfill our requirements: half of them are not self-contained (i.e. they have hardware placed externally from the hand), the DLR/HIT Hand II is too heavy, the Harada Robot Hand, Prensilia IH2 Azzurra hand and TUAT/Karlsruhe Hand [START_REF] Fukaya | Design of the tuat/karlsruhe humanoid hand[END_REF] do not have enough DoFs to perform the required gestures. Only the Elu2-Hand could fulfill our functional needs, however, its size is similar to that of an adult's hand and it cannot be scaled to the demanded size.

In general, anthropomorphic robotic hands kinematics are not designed on the base of the finger-thumb interaction, even though hand performance strictly depends on the thumb dexterity and opposability. Thumb capabilities are determined by its kinematics and base placement. The problem of thumb placement has already been addressed in literature. Grebenstein et al. [START_REF] Grebenstein | A method for hand kinematics designers 7 billion perfect hands[END_REF] developed cardboard prototypes to incrementally refine the hand kinematics in order to obtain thumb functionalities and hand aesthetics similar to the human one. Wang et al. [START_REF] Wang | An anthropomorphic design guideline for the thumb of the dexterous hand[END_REF] approached the problem using a numerical method based on the Euler rotation theorem. The thumb placement was computed passing from a lateral posture to an opposing one in order to ensure basic grasping modes. This paper solves the problem using a numerical method based on a surgery test and a workspace analysis of the whole hand. The best thumb position and orientation is found according to the hand kinematics and structure.

III. OUR HAND DESIGN

The design of the kinematic model of our hand started from mechanical and functional observations which lead to the following objectives:

• be aesthetically anthropomorphic in order to be easily accepted by human beings; • be proportioned to a 6 years old child's hand;

• weigh less than 0.6 Kg -to be embodied on the robot; • be compliant -to have a safe human-robot interaction; • be silent. while from a functional point of view it has to:

• 70% communicate information and emotions using gestures: pointing, counting, thumb-up, ok, etc . . . ; • 30% grasp light objects, like a smart-phone or a full soda can.

A. Kinematics design

To have a light and small hand the number of actuators has to be as small as possible. A robotic hand that is able to grasp various objects does not need numerous actuators. Thanks to differential mechanisms and under-actuated fingers capable to adapt to different surfaces [START_REF] Birglen | Kinetostatic analysis of underactuated fingers[END_REF] only one actuator is sufficient [START_REF] Fukaya | Design of the tuat/karlsruhe humanoid hand[END_REF]. Also finger geometry and couplings based on postural synergies [START_REF] Bicchi | Modeling natural and artificial hands with synergies[END_REF] allow to use a reduced number of actuators. However, in our case, non-verbal communication should be added to grasping capabilities. For this reason, the design of the kinematic model is firstly oriented to satisfy the required gestures. To achieve this, the whole human hand kinematic model is firstly considered with all its joints coupled. Then, for each gesture, joint couplings are incrementally relaxed to minimally increase the number of actuators. After that, the number of joints is reduced to meet the weight and size limits. Obviously, this last step imposes a trade off between well-mimicked gestures and a light and small structure. To identify the less relevant joints, gestures are classified according to the feelings they trigger in the recipient: low priority is given to gestures inducing negative sensations, while, middle and high priorities are associated to the ones inspiring neutral and positive feelings respectively. Hence, to meet weight and size constraints, joints purely involved in performing low priority gesture are removed. The thumb is defined with four joints, abduction/adduction finger motions are removed as well as the CMC joint at the base of the little finger. Figure 3 shows our final hand kinematic model: 1 DoF per finger (they can only flex/extend) and 3 DoFs for the thumb. All joints can rotate by 90 • about their axes. Their range of motion normally goes from 0 • to 90 • , where 0 • refers to the hand configuration in which all fingers are fully extended on the same plane.

B. Finger and thumb proportions

No best practice to define finger lengths, widths and placements exists. Modular designs of some or all fingers are often used to help mechanical modeling and construction. Each finger has the same link length, width, joint RoM and DoFs and their placement on the palm determines the similarity to the human counterpart. Nevertheless, a better affinity with the human hand is achieved respecting human finger diversities. Link lengths and widths are derived from body proportions under the assumption that the structure and bones proportions of hands are maintained despite their physical size [START_REF] Chao | Biomechanics of the hand. A basic research study[END_REF]. Link lengths are commonly disclosed as percentage of the hand length [START_REF] Davidoff | A graphic model of the human hand using CATIA[END_REF], therefore, they can be easily computed knowing the distance between the wrist and the middle fingertip. Link widths measurements are determined as a function of the hand width using two linear equations as lower and upper bounds. This approach took inspiration from the comparison done by [START_REF] Komandur | Relation between index finger width and hand width anthropometric measures[END_REF] between the Grainer model [START_REF] Greiner | Hand Anthropometry of U[END_REF] and Buchholz and Armstrong model [START_REF] Buchholz | An ellipsoidal representation of human hand anthropometry[END_REF].

Table II gives the link lengths and widths for a humanoid robot of similar height to a 6 year old child.

C. Finger placement

Finger bases are computed using a circle centered at the MCP joint of the middle finger [START_REF] Isobe | Hand position[END_REF]. Since link lengths are fixed (Table II), the angle between each finger base determines the linking point to the palm. Small angles return closer finger bases, with similar heights from the wrist, while Fig. 4: Finger base placement approach. TABLE III: Finger base positions and orientations with respect to the hand frame (Figure 3). big angles locate finger bases at further distances and with various heights from the wrist. Obviously, too close finger bases are not mechanically feasible, while far finger bases result in an unaesthetic design. A compromise between the two is necessary in order to have a well-balanced hand (Figure 4). Along the z axis, fingers are placed so that the fingertips lie on a common xy plane when they are completely flexed. This allows the palm to have the same arched shape as the human hand. Designed fingers can only flex and extend (1 DoF) via three parallel hinge joints. Hence, MCP joints are inclined to preserve the finger convergence of the human hand towards the center of the palm. To determine maximum angles of inclination of the finger bases, intra-finger collisions are checked while flexing the joints. For each finger, finger distances are computed increasing the inclination angle from 0 • until a collision is detected (Figure 3). Table III shows the resulting finger base positions and orientations. The distance along y between the little and the ring bases is smaller than the others, slightly complicating the mechanical design. However, with these results the aesthetics of the human hand is globally met.

D. Thumb placement

To approximately attain human hand performances the thumb geometry and kinematics need to be carefully designed. To gesture and grasp, 4 joints with 3 DoFs are chosen for the thumb kinematics (Figure 3). Its proportions are calculated as described in the previous Section III-B. The thumb base configuration is computed following three criteria: dexterity, opposability and aesthetics. In order to imitate human thumb motions, the robotic thumb has to be able to reach a certain number of desired positions on the opposite fingers. These positions are defined by a wellknown surgery test, known as Kapandji test [START_REF] Kapandji | Cotation clinique de l'opposition et de la contreopposition du pouce[END_REF], used after pollicization, which consists in reconstructing the thumb by displacing the index finger from its MCP joint to the MCP joint of the thumb. The test contains all motion directions and an interesting set of positions which are useful to check the thumb range of motion and its dexterity. However, it cannot provide information about thumb grasping abilities. Reaching all required positions does not necessarily imply that the thumb is effectively able to interact with the opposed finger. Hence, an additional test is carried out to explore the physical interaction between the thumb fingertip and the opposed fingers. This test returns the intersection volume between the thumb and fingers as a thumb opposability index [START_REF] Mouri | Anthropomorphic robot hand: Gifu hand iii[END_REF], which denotes the hand grasping abilities from a kinematics point of view. Note that no forces are considered in this context; an additional evaluation metric should be taken into account to determine finger forces and grasping stability. Finally, the global appearance of the hand has to be equilibrated and easily accepted. Indeed, the hand will be mounted on a social robot and its aesthetics is fundamental to enhance and encourage human-robot interaction. In summary, the thumb base placement is the most delicate design step. In order to obtain the needed functionalities (gesturing and grasping) the thumb has to be dexterous and opposable. These two properties are respectively achieved through:

• The Kapandji test;

• The thumb opposability index. In addition, an aesthetic check is done to evaluate the overall hand appearance. This last test implies a cyclic design in which the intervals of search among the thumb base parameters are adapted at each iteration.

IV. THUMB BASE SELECTION

In this section the tests used to design a dexterous and opposable thumb are presented. According to the thumb geometry and kinematics, the thumb base configuration is determined by calculating the thumb base position (x, y, z) and orientation about the z (θ z ) axis with respect to the hand frame (Figure 3). The orientations about x and y axes are not included because of the 2 DoFs of the base.

A. The Kapandji test

The Kapandji test assigns a score for each reached position of the thumb on the opposite fingers. As shown in [START_REF] Kapandji | Cotation clinique de l'opposition et de la contreopposition du pouce[END_REF] the thumb passes from the index base to its fingertip and proceeds to the little fingertip touching the end of the fingers in between. Finally, it reaches the little base to complete the test. Based on this idea, the thumb is asked to reach all finger joints and fingertips for a total of 16 desired positions. If the thumb attains all 4 positions defined on each finger, the thumb base is collected as a candidate solution (Figure 5). Fig. 5: Desired positions defined at the joints and fingertip of the opposing finger. Target frames are placed exactly on the finger surface. The image shows simplified finger links to facilitate the view. As it can be seen, for each desired position on the finger (a, b, c, d), the thumb end-effector at the pulp is accordingly displaced so that it will reach the desired positions in configurations similar to the ones of the human hand.

1) Problem formulation:

The thumb and the finger in opposition are treated as two independent serial chains attached to a common base. On each chain an end-effector is defined according to the desired position that has to be reached. The objective is to determine if both kinematic chains can converge to a common position.

Definitions:

• j = t or f i respectively referring to the thumb fingertip and the i th end-effector (i = MCP, PIP, DIP and fingertip) on the f th finger; • q j vector of the independent joint variables of the j th chain; • T j (q j ) direct geometric model (DGM) of the j th serial kinematic chain. It computes the end-effector configuration passing from the joint space to the Cartesian space; • J j (q j ) Jacobian matrix. It provides the j th end-effector differential displacement (linear and angular) in terms of the differential variation of the joint variables. In this context, only its upper part is used in order to uniquely consider the linear displacement of the endeffector: dP = J j (q j )dq j . The problem can be solved using the inverse geometric model where the desired frame changes at each iteration:

1) Initialization of current joint variables q c t and q c f i to a random value or desired initial value within the joint domain; 2) Computation of the current end-effector transforms T t (q c t ) and T f i (q c f i ) of each chain (thumb and opposing finger); 3) Computation of the position error defined as: dP = P t (q c t ) -P f i (q c f i ), where P t (q c t ) and P f i (q c f i ) are the position vectors of T t (q c t ) and T f i (q c f i ) respectively; 4) If (||dP|| is as small as required): the algorithm stops; else: dP is scaled if it is too big to be used in the differential model dP = dP/||dP||dx, where dx is a properly defined small displacement; 5) Computation of thumb and finger current Jacobians J t (q c t ) and J f i (q c f i ); 6) Calculation of joint variations dq t = J t (q c t ) + dP/2 and dq f i = J f i (q c f i ) + (-dP/2); 7) Updating joint configurations q c t = q c t + dq t and q c f i = q c f i + dq f i within the joint domain; 8) Reiteration from step 2. In our context, q f i is always a scalar for each finger f , independently from the chosen end-effector since all finger joints are coupled. Finger joint couplings influence the thumb base selection since end-effector trajectories change. In this context, transmission ratios are set to 1:1. Note that, if more than 3 DoFs are available on a single chain, this algorithm can be extended when computing the joint displacements. Indeed, a correction in orientation, if desired, could be attained as a secondary objective, working in the null space of the Jacobian matrix of the serial chain. This iterative approach can return some undesired solutions: the thumb end-effector reaches the desired position passing through the finger in opposition. Consequently, a non-linear optimization algorithm with collision avoidance constraints is used: min q t ,q f i ||dP(q t , q f i )|| s.t. q t l min ≤ q t l ≤ q t l max , l = 1, . . . , DoFs(q t ) q f il min ≤ q f il ≤ q f il max , l = 1, . . . , DoFs(q f i )

d sph ≥ r t + r f i -ε (1)
where r t is the thumb radius at the fingertip (the half of the thumb width defined in Table II), r f i is the radius of the opposed finger at the desired point of interest (half of the joint or fingertip width defined in Table II), ε is an arbitrary fixed scalar (e.g. 0.5 mm) which defines the intersection acceptance between the two chains, considering that finger surfaces can be made of soft materials, and d sph is the distance between two sphere centers, one located within the thumb and the other one within the opposed finger. Spheres are placed so that their surfaces overlap with the finger ones.

Obviously, contour and constraining inequalities have to be adapted according to the finger shapes.

B. Volume of intersection

Volumes of intersection among fingers discerns their kinematic degree of interaction. Collision points are identified Fig. 6: Intersection between thumb fingertip and all fingers end-effectors. by exploring the finger workspaces. To evaluate the thumb opposability a modified version of the performance index [START_REF] Mouri | Anthropomorphic robot hand: Gifu hand iii[END_REF] is used:

I = 1 d 3 t k ∑ i=1 e ∑ j=1 w i j v i j (2)
where d t is the thumb length, k is the number of fingers (thumb excluded), e is the number of end-effectors considered on each opposed finger, w i j is a weighing coefficient, v i j is the volume of intersection between the thumb and the finger end-effector. This performance index includes and weights the interaction between the thumb fingertip and each finger portions involved in the Kapandji test. Intersection volumes (v i j ) are computed sampling the Cartesian space in x, y and z. The number of cells which compose the grid strictly depends on the hand workspace boundaries and the size of the sampling interval (set to 2 mm). Each contact is checked by visiting the thumb and finger joint spaces and it is stored in the corresponding cell. Consequently, the number of cells holding collisions reveals the intersection volume per finger:

v i j = n i j ∆V (3)
where n i j is the number of cells in which the thumb fingertip and the j th end-effector of the i th finger intersect and ∆V is the volume of a cell.

Differently from [START_REF] Wang | An anthropomorphic design guideline for the thumb of the dexterous hand[END_REF], the end-effector is not considered as a single point. Indeed, a single point does not determine the potential grasping capabilities of the hand. For this reason, a cloud of points within the finger and thumb mechanical structures is taken into account. In this case, v i j approximatively discloses the amount of effective interaction between the thumb and the fingers close to the Kapandji positions (Figure 6).

C. Solution selection

To select the best position and orientation of the first joint of the thumb the following algorithm is implemented: 1) Thumb bases are generated using a brute force exploration. Intervals are defined according to aesthetics and mechanical constraints; 2) For each base the Kapandji test is performed; 3) If the candidate passes the Kapandji test: the thumb opposability index is computed beside the relative standard deviation (σ r ) of the intersection volume:

σ r = σ 2 v 100 (4)
where

σ 2 = ∑ k i=1 (v i -v) 2 /k, v i = ∑ e
j=1 v i j and v is the mean value of v i . 4) If the relative standard deviation is lower than a desired threshold (in our case set to 20%) the candidate is stored (the thumb opposability is enough equilibrated). 5) The solution is selected picking the stored candidate with the highest thumb opposability index. Table IV lists some stored candidates. The one with the highest TOI is chosen.

V. VALIDATION AND DISCUSSION

The hand model is designed and simulated using Python and NAOqi [START_REF] Aldebaran | Naoqi framework. Website[END_REF] APIs. Geometric and kinematic parameters are inspected by direct visualization of the final robotic hand model. The Kapandji test is verified by moving the fingers and thumb in the collected configurations obtained during the algorithm execution and it is checked that the hand is able to reach the desired list of positions within the demanded precision. Figure 7 shows the furthest (a) and the closest (b) positions involved in the test. Hand grasping capabilities have been examined on various objects (e.g. soda can and a smartphone) using CAD software. However, no conclusions can be drawn on the grasping success since only a kinematic analysis has been conducted at this stage. Beside common gestures, like "pointing" (Figure 8-a), "thumb-up" or "ok" gestures, the hand is able to count from one to ten in the Chinese way and from one to five in the European one. For example, Figure 8-b shows the number three in the European counting. Note that, in order to give more emphasis to the finger kinematics a simplified palm is represented.

VI. CONCLUSIONS

A simple and effective numerical method for designing dexterous and highly opposable anthropomorphic robotic hands has been presented. The method is conceived to realize a fully embedded, small sized and light hand for a social humanoid robot of similar height to a 6 year old child. It consists in a design tool that generates the hand kinematics which are able to express emotions (gestures) and grasp small objects. Hand geometry has been conceived using anthropomorphic data and heuristics methods which allow a kinematic solution close to that of a human hand. The main focus has been given to the thumb base position and orientation, since its interaction with the opposed fingers strongly effects the hand performance. Three tests drove its selection: aesthetic, surgical and interaction tests. The first played a relevant role to obtain a fairly equilibrated hand, the second provided a human-like dexterous thumb, while the last one defined its opposability. Hand designers can follow this method to immediately obtain the hand kinematic model and structure. Future work will consist in improving the candidate selection among thumb bases using genetic algorithms rather than a brute force approach.

Fig. 1 :

 1 Fig. 1: Drawing of the human hand skeleton.

Fig. 2 :

 2 Fig. 2: Top view of simplified human hand kinematic model (22 DoFs). Note that the drawing does not aim to reproduce the real structure.

Fig. 3 :

 3 Fig. 3: Simplified kinematic model of our robotic hand. Each color refers to a single DoF.

Finger

  Base position [mm] (x, y, z) Base orientation [deg] Index (59.3, 18.1, -1.8

Fig. 7 :

 7 Fig. 7: Thumb opposition on the little fingertip (a) and the index MCP (b): two of the 16 positions demanded in the implemented Kapandji test. The thumb base is the last configuration listed in TableIV.

  Fig. 7: Thumb opposition on the little fingertip (a) and the index MCP (b): two of the 16 positions demanded in the implemented Kapandji test. The thumb base is the last configuration listed in TableIV.

Fig. 8 :

 8 Fig. 8: Two examples of gestures that can be performed by the hand: pointing (a) and counting (b).

TABLE I :

 I Comparison of robotic hands. Wrist not included in the considered DoFs.

	Name	DoFs Weight [Kg] Self-contained
	DLR Hand Arm System	19	13.5 *
	Shadow Dexterous Hand	18	4.2
	UB Hand IV	15	n.d.
	DLR/HIT Hand II	15	1.5
	Robonaut 2 Hand	12	2.25
	Elu2-Hand	9	0.74
	iCub hand	9	0.212
	Harada Robot Hand	5	0.369
	IH2 Azzurra	5	0.64
	TUAT/Karlsruhe Hand	1	0.125

* considering arm and hand together.

TABLE II :

 II Link lengths and widths for a humanoid robot of similar height to a 6 year old child.

	Finger	Link	Length [mm] Width [mm]
		Carpometacarpal	30.8	25
	Thumb	Proximal phx	22.6	16
		Distal phx	20.7	16
		Proximal phx	26.4	15
	Index	Middle phx	17.1	14
		Distal phx	16.8	13
		Proximal phx	29.7	15
	Middle	Middle phx	19.1	14
		Distal phx	18.2	13
		Proximal phx	26.9	15
	Ring	Middle phx	18.5	14
		Distal phx	18.1	13
		Proximal phx	21.4	13
	Little	Middle phx	13.1	12
		Distal phx	15.7	11

TABLE IV :

 IV Candidate thumb bases. TOI is the Thumb Opposability Index

	(x, y, z) [mm]	orientation [deg]	TOI	σ r [%]
	(8, 11, -9)	45 •	0.167	19.693
	(8, 11, -5)	40 •	0.169	17.421
	(8, 2, -5)	50 •	0.177	6.705
	(12, 2, -5)	45.0 •	0.196	12.252