KPPY 67

The goal is to report on some long-term work on certain combinatorial properties of knot/link diagrams of given canonical genus. These turned out to have various ramifications and applications, including (1) enumeration of alternating knots by genus, (2) words in formal alphabets (Wicks forms), (3) graph embedding problems on surfaces, (4) markings and the $sl_N$ graph polynomial, (5) hyperbolic volume of polyhedra, graphs and links. I will try to explain (at least as far as time allows) some interrelations between these topics.

A graph is $(d_1, \ldots, d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, \ldots, V_r$ where the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $i\in \{1, \ldots r\}$. For improper coloring of planar graphs with two parts, given $g$ and $d_1$, the question of determining the minimum $d_2=d_2(g, d_1)$ such that planar graphs with girth $g$ are $(d_1, d_2)$-colorable has attracted much interest. The finiteness of $d_2(g, d_1)$ is known for all cases except when $(g, d_1)=(5, 1)$. Montassier and Ochem, as well as Rapaud, asked if $d_2(5, 1)$ is finite. We answer this question in the affirmative with $d_2(5, 1)\leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable. Moreover, we prove that for any Euler genus $\gamma$, there exists a $K=K(\gamma)$ where graphs with girth $5$ that are embeddable on a surface of Euler genus $\gamma$ are $(1, K)$-colorable. This is joint work with H. Choi, J. Jeong, and G. Suh.

For a ring $R$, the zeta function of $R$ is defined by \[ \zeta_R(s)=\sum_{I} (R:I)^{-s},\] the sum extending over all ideals $I$ in $R$ with finite index $(R:I)$. We only view the zeta function as a formal Dirichlet series. Using fiber product diagrams, we find the zeta functions in the cases \[R=\mathbb{Z}[x]/((x-a)(x-b)),\] where $a$ and $b$ are integers. Then we get the zeta functions of adjacency algebras of complete graphs as a corollary.

In this talk, we show that there is a one-to-one correspondence between the set of compositions (resp. prime compositions) of $n$ and the set of circulant digraphs (resp. connected circulant digraphs) of order $n$. We also show that there is a one-to-one correspondence between the set of palindromes (resp. aperiodic palindromes) of $n$ and the set of circulant graphs (resp. connected circulant graphs) of order $n$. As a corollary of this correspondence, we enumerate the number of connected circulant (di)graphs of order $n$.