# 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.