Imbedding Types for Linear Families, Markov Chains, and Smoothing

Thomas Tucker
Colgate University

Jonathan Gross
Columbia University, New York, NY 10027, USA

Toufik Mansour
University of Haifa, 31905 Haifa, Israel

PDF

PLENARY TALK

Content: e genus polynomial $g_G(z)=\Sigma a_iz^i$ of graph $G$ is the generating function where $a_i$ is the number of imbeddings of $G$ in the surface of genus $i$. A genus polynomial is always {\em interpolating}, that is the nonzero coefficients form an interval. Little else is known; for example the number of imbeddings of $K_7$ is $(6!)^7$ and its genus polynomial has not been computed. On the other hand, for any ``linear family' of graphs $G_n$, one can partition into imbedding types and compute a ``production" (recursion) matrix $M(z)$ with polynomial entries (with non-negative integer coefficients) such that the vector $v_n(z)$ of genus polynomials partitioned by imbedding types satisfies $v_n(z)=M^n(z) v_0(z)$. The matrix $M(1)$ has constant column sum $s$, so $(1/s)M(1)$ is the matrix of a Markov chain. We conjecture that it is regular, that is $M^n(1)$ has all positive entries for some $n$. We also conjecture that multiplication by $M^n(z)$ is a form of smoothing analogous to multiplication of any polynomial (with nonnegative coefficients) by $(1+z)^n$, which is eventually interpolating and log-concave.

Back to all abstracts