Linear lambda terms as invariants of rooted trivalent maps
Linear lambda terms as invariants of rooted trivalent maps
复制标题
线性 lambda 项作为有根三价映射的不变量
DOI：
10.1017/s095679681600023x
复制
发表时间：
2015
影响因子：
1.1
通讯作者：
N. Zeilberger
中科院分区：
文献类型：
--
作者：
N. Zeilberger
摘要本文的主要目的是在封闭的线性lambda术语的α-等价类别之间提供简单而概念的说明（最初由Bodini，Gardy和Jacquot描述）没有边界的表面，作为线性lambda术语之间具有更一般对应关系的实例边缘，我们首先回忆起线性lambda术语的熟悉的图表表示，同时解释了如何正式读取此类图作为对称单体封闭（BI）类别的反射对象的符号。信件的“简单”方向是一个简单的健忘操作，它在线性lambda术语的图上删除注释，以产生扎根的三价图。术语是其潜在的植根三价图的完全不变，通过在带有自由边缘的地图上通过TUTTE式的拓扑复发来重建缺失的信息，我们将这种分析用来列举包含Bridgeless lineed Trivent Maps no封闭的适当的细胞，并包括对四种颜色定理的自然改革，以作为在lambda微积分中打字的陈述。
Abstract The main aim of the paper is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between α-equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact-oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.