Dessin D'enfant - Trees and Shabat Polynomials

Trees and Shabat Polynomials

The simplest bipartite graphs are the trees. Any embedding of a tree has a single region, and therefore by Euler's formula lies on a spherical surface. The corresponding Belyi pair forms a transformation of the Riemann sphere that, if one places the pole at ∞, can be represented as a polynomial. Conversely, any polynomial with 0 and 1 as its finite critical values forms a Belyi function from the Riemann sphere to itself, having a single infinite-valued critical point, and corresponding to a dessin d'enfant that is a tree. The degree of the polynomial equals the number of edges in the corresponding tree.

For example, take p to be the monomial p(x) = xd having only one finite critical point and critical value, both zero. Although 1 is not a critical value for p, it is still possible to interpret p as a Belyi function from the Riemann sphere to itself because its critical values all lie in the set {0,1,∞}. The corresponding dessin d'enfant is a star having one central black vertex connected to d white leaves (a complete bipartite graph K_1,d).

More generally, a polynomial p(x) having two critical values y₁ and y₂ is known as a Shabat polynomial, after George Shabat. Such a polynomial may be normalized into a Belyi function, with its critical values at 0 and 1, by the formula

but it may be more convenient to leave p in its un-normalized form.

An important family of examples of Shabat polynomials are given by the Chebyshev polynomials of the first kind, T_n(x), which have −1 and 1 as critical values. The corresponding dessins take the form of path graphs, alternating between black and white vertices, with n edges in the path. Due to the connection between Shabat polynomials and Chebyshev polynomials, Shabat polynomials themselves are sometimes called generalized Chebyshev polynomials.

Different trees will, in general, correspond to different Shabat polynomials, as will different embeddings or colorings of the same tree. Up to normalization and linear transformations of its argument, the Shabat polynomial is uniquely determined from a coloring of an embedded tree, but it is not always straightforward to find a Shabat polynomial that has a given embedded tree as its dessin d'enfant.