本文给出向上平面序的简单介绍.

什么是向上平面序呢? 它是我和合作者对因果网络提出的一个新的组合结构. 简单地讲, 向上平面序就是因果网络的边集合上的一种特殊的线序. 换句话说,  向上平面序是对因果网络的边进行的一种线性排序, 但要满足一定的性质(套嵌性质). 下图展示了一个例子, 其中的因果网络一共有20条边,  它的向上平面序定义了这20条边的一个线性顺序. 可以认为这20条边的线性顺序完全确定了因果网络在平面的嵌入方式.

为什么要定义和研究向上平面序呢? 原因是我们要研究定向图的向上平面性, 向上平面序是对向上平面性的组合刻画. 那什么是向上平面性呢? 向上平面性是定向图的在平面上的一种可嵌入的性质, 它对于定向图的意义恰恰如同平面性对于非定向图的意义. 

图的平面性是图论的一个经典课题, 它研究的是图在平面上的画法或者几何实现. 其中的一个自然的限制就是任意两条边在中间不可以相交, 如果相交也必须仅仅在端点处相交. 没有这个限制的研究, 从数学上看就没有多少意思了, 因为研究太随意的结构往往不会得到什么好的定理.  

我们知道图可以分为无向图和有向图. 对于无向图, 它们的平面嵌入的要求就是边的内部不能相交. 可以嵌入到平面上的无向图称为可平面图. 已经嵌入到平面的无向图称为平面图.  注意, 可平面性是图的一种拓扑性质, 而平面嵌入是图上的一种拓扑结构.对于有向图, 它的平面嵌入除了要求边的内部不能相交, 还要求所有的定向边都指向一个固定的方向, 这样的嵌入称为向上平面画法或向上平面嵌入. 具有向上平面画法的定向图称为可向上平面图.

 同样地, 已经向上平面嵌入到平面的定向图称为向上平面图. 上面展示的平面定向图就是一个向上平面图的例子, 它的所有的边都从上方指向下方.  很容易发现, 因为要求所有的定向边都指向同一个方向, 所以向上平面图是没有定向环路的, 换句话说, 它们其实都是因果网络, 即有向无环图. 同样需要注意的是, 可向上平面性是因果网络的一种拓扑性质, 向上平面嵌入是因果网络上的一种拓扑结构.

对于有向图, 当然可以仅仅考虑它的平面嵌入, 而不考虑它的定向边的走向问题, 但是这样的结构并没有多少研究, 因为边上的定向结构和平面性没有约束关系.

2015年, 我们发现可以用一种边集上线性序刻画因果网络的向上平面性, 这种特殊的线序被称为向上平面序. 我们证明了一个因果网络有向上平面嵌入当且仅当它的边集上有一个向上平面序.因果网络是无环定向图, 它的边集合关于到达关系形成一个偏序集. 向上平面序是边集合上的一个全序, 它要满足两个性质, 其中第一个性质(Q1)说明它是到达偏序的一个线性扩张, 可以理解为是边的到达关系和向上平面序的相容关系; 第二个性质(Q2)称为套嵌性质, 它是对相连的两条边和它们之间的第三条边的平面位置关系的约束.

向上平面序理论是张量范畴的图形演算理论的组合版本, 借鉴图形演算的复合方法, 我们也发展了向上平面序的复合理论. 对于一个向上平面图, 我们有一个确定的算法来计算它的向上平面序.  这个算法比较简单, 其思路是首先对向上平面图进行分层切割, 使得每一层的子图都非常简单(叫做基本向上平面图), 然后我们可以直观地确定每一层子图的向上平面序, 最后通过一个简单的复合规则计算出整个因果网络的向上平面序. 

如下图所示, 上方的因果网络就是一个基本的向上平面图, 它的向上平面序非常简单, 就是按照从上到下, 从左到右的规则确定的. 当然, 如果做一个连续形变, 可能会得到不同的向上平面序. 所以, 对于一般的基本向上平面图, 它的向上平面序并不唯一, 但是差一个组合等价. 向上平面序的组合等价类刻画了向上平面图的拓扑等价类.

每一层的基本子图都容易确定其向上平面序.

接下来我们可以利用一个简单的复合规则, 计算出向上平面图整体的向上平面序.

特别要说明的是, 向上平面序的复合规则非常自然, 就是一种洗牌(shuffle)规则. 对于两个可以复合的向上平面图, 它们的切口是一一对应的, 这些切口所对应的边分别称为两个向上平面图的输出边和输入边, 它们分别把每一个向上平面图的边集划分成了一系列区间(这是因为向上平面序是线序), 这些区间称为基本区间. 向上平面序的复合规则就是把这些基本区间, 根据输出边和输入边的位置, 进行洗牌操作, 可以证明最后的复合序还是向上平面序, 即满足(Q1)和(Q2), 它编码了向上平面图在平面上的画法信息.

本文中讲的故事只是冰山之一角, 它的背后是涉及到张量范畴, 图形演算, 偏序集的拓扑理论等诸多数学结构的大纲领, 完全地描绘清楚整个冰山还有很多工作要做, 需要很多年轻人的加入. 感兴趣的可以搜索"图形演算和向上平面性", 了解我对整个纲领的布局.关于图形演算的资料, 大家可以到下面的网页查找:

https://ncatlab.org/nlab/show/string+diagram

关于向上平面序的三篇原始论文, 可以看

• Sen Hu, Xuexing Lu, Yu Ye: A graphical calculus for semi-groupal categories, Appl Categor Struct 27 (2019) 163–197 [arXiv:1604.07276, doi:10.1007/s10485-018-9549-8]

• Xuexing Lu, Yu Ye: Combinatorial characterization of upward planarity, Commun. Math. Stat. 7 (2019) 207–223 [arXiv:1608.07255, doi:10.1007/s40304-018-0169-2]

• Xue Dong, Xuexing Lu, Yu Ye:  A composition theory for upward planar orders, [https://arxiv.org/abs/2505.13865]