KAIST Discrete Math Seminar

A map is a 2-cell embedding of a graph into a closed surface and a regular map is a highly symmetric map like five Platonic solids. A map is not merely a topological object. It is also a sequence of permutations, which provides a relation to group theory, and a ramified covering of the Riemann sphere, which gives a relation to Riemann surface. Furthermore, it can be realized by a complex algebraic curve called Belyi function.

In this talk, classifications of regular maps are considered from several aspect. And, some connections between maps and permutation group, Riemann surface and Belyi functions and their applications are given.

For a labeled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij as i to j if i<j. The indegree sequence λ=1^e₁2^e₂ … is then a partition of n-1. Let a_λ be the number of trees on [n] with indegree sequence λ. In a recent paper (arXiv:0706.2049v2) Cotterill stumbled across the following remarkable formulas  where k = Σ_i e_i. In this talk, we first construct a bijection from (unrooted) trees to rooted trees which preserves the indegree sequence. As a consequence, we obtain a bijective proof of the formula. This is a joint work with Jiang Zeng.

Equational reasoning is fundamental in automated theorem proving (that is, the proving of mathematical theorems by a computer program), and rewriting is a powerful method for equational reasoning. Category theory is a mathematical theory that deals in an abstract way with mathematical structures and relationships between them.

Using category theory, we have developed a framework for equational reasoning. A Term Equational System (TES) is given by a semantic universe and an abstract notion of syntax; and given this, we automatically derive a sound logical deduction system, called Term Equational Logic (TEL). Furthermore, we provide an algebraic free construction for the system, which may be used to synthesize a sound and complete rewriting system for it.

Existing systems arising in this framework include:

• first-order equational logic and rewriting system;
• combinatory reduction system of Klop;
• binding equational logic and rewriting system of Hamana; and
• nominal equational logics independently developed by Gabbay and Matheijssen, and Clouston and Pitts.

Especially, following the above scenario in our framework, we have newly developed a sound and complete rewriting system for nominal equational logic.

In this talk, rather than going into the technical details, I will focus on explaining basic ideas of category theory and how it can be used in practice.

This is joint work with Marcelo Fiore.

The Euler number E_n counts the number of alternating permutations on the set [n]. It is well known that its exponential generating function equals Tan z + Sec z. For this reason, E_2n and E_2n+1 are called secant numbers and tangent numbers, respectively. Certain polynomials arising in series expansions for zeros of generalized Rogers-Ramanujan functions provide a q-analog of the tangent numbers, which is part of a wider class of polynomials with similar combinatorial interpretations. In this talk, we will discuss various q-Euler numbers. This is a joint work with Tim Huber from Iowa State University.