阶数不超过12的非匹配型分配格的枚举

doi:10.12677/pm.2025.1511287

期刊菜单

阶数不超过12的非匹配型分配格的枚举
Enumeration of Non-Matchable Distributive Lattices of Order Not Exceeding 12

DOI: 10.12677/pm.2025.1511287, PDF, HTML, XML, 国家自然科学基金支持
作者: 张诗晗, 王海艳, 姚海元^*：西北师范大学数学与统计学院，甘肃兰州
关键词: 完美匹配；匹配型分配格；非匹配型分配格；凸子格；Perfect Matching； Matchable Distributive Lattice； Non-Matchable Distributive Lattice； Convex Sublattice

摘要: 张和平等人在平面基本二部图的完美匹配集合上建立了一个分配格结构，这样的分配格称为匹配型分配格；而对于一个有限分配格，若找不到与之对应的平面二部图，使其同构于该图完美匹配集合上的分配格，则称之为非匹配型分配格。本文中，我们通过研究匹配型分配格的特定结构，得到几个非匹配型分配格的判定方法，作为以上工作的简单应用，由此枚举了所有阶数不超过12的非匹配型分配格。

Abstract: Zhang Heping et al. established a distributive lattice structure on the set of perfect matchings of a plane elementary bipartite graph; such a distributive lattice is called a matchable distributive lattice. Conversely, for a finite distributive lattice, if no corresponding plane bipartite graph can be found such that the lattice is isomorphic to the distributive lattice formed by the set of perfect matchings of that graph, then it is referred to as a non-matchable distributive lattice. In this paper, by characterizing the specific structure of matchable distributive lattices, we derive several criteria for identifying non-matchable distributive lattices. As a straightforward application of the above work, we enumerate all non-matchable distributive lattices with up to 12 elements.

文章引用：张诗晗, 王海艳, 姚海元. 阶数不超过12的非匹配型分配格的枚举[J]. 理论数学, 2025, 15(11): 259-270. https://doi.org/10.12677/pm.2025.1511287

1. 引言

1988年，张福基等人[1]引入了六角系统的完美匹配集合上的Z-变换图(共振图)的概念。后来张和平等人[2]将此概念推广到了平面二部图上，并通过区分两种不同的匹配交错圈，给Z-变换图进行了定向，建立了有向Z-变换图。对于平面弱基本二部图，Lam和张和平等人[3]证明了有向Z-变换图无(有向)圈，以此建立了其完美匹配集合上的有限分配格结构，并证明了每个连通的共振图都是median图，因此可等距离嵌入到超立方体中。Z-变换图的概念因其自然性也曾被Gründler [4]，Randić和Forunier [5]等人从不同角度独立提出。后来张和平等人[6]提出了非匹配型分配格的结论并研究了相关基本性质；Klavžar [7]，姚海元等人确定了斐波那契和卢卡斯立方体是否为匹配型的分配格；2014年，姚海元[8]归纳了几类具有割元的非匹配型分配格并构造了两类匹配型分配格。2019年，姚海元、王旭[9]等在一类非匹配型分配格中，通过引入基于平面基本二部图某个完美匹配的交不可约内环并给出其等价刻画，得到了一类新的非匹配型分配格，推广了一类没有割元的非匹配型分配格。尽管已得到不少有关非匹配型分配格的结论，然而有关非匹配型分配格的枚举目前仍然是空白的。本文中主要枚举了一些低阶的非匹配型分配格。

本文中第二节我们主要回顾了一些有关偏序集、匹配、非匹配型分配格的基本概念及相关结论。第三节中我们通过刻画以几个特殊的分配格为凸子格的最小阶数的匹配型分配格，从而得到了不能由割元定理判定的非匹配型分配格的几个判定方法；将以上判定方法应用到所有阶数不超过12的分配格上后，完成了对所有阶数不超过12的非匹配型分配格的枚举。

2. 预备知识

在本节中我们给出了一些有关分配格和匹配方面的概念和性质，其余在本文中用到但未介绍的概念，偏序和格方面的见[10] [11] [12]，图论方面的见[13] [14]。

偏序集 $P = (P, \leq)$ 由它的覆盖关系“ $≺$ ”确定，并通常由Hasse图来表示。本文中将Hasse图当作有向图。设 $x, y \in P$ ，称 $z \in P$ 是x和y的一个下界，如果有 $z \leq x$ 和 $z \leq y$ ；x和y的一个下界z称为下确界，如果z是x和y的所有下界中最大的一个。x和y的下确界(若存在)是唯一的，记为 $x \land y$ ；对偶地，可以定义x和y的上界，及上确界 $x \lor y$ 。设 $Q$ 是 $P$ 的一个子偏序集，如果 $x, z \in Q$ 且 $x < y < z$ 时总可以得到 $y \in Q$ 的话，则称 $Q$ 是凸的。令 $x, z \in P$ 且 $x \leq y$ ，定义由集合 ${z \in P | x \leq z \leq y}$ 导出的子偏序集为区间 $I [x, y]$ 。设 $(P, \leq)$ 是一个有限偏序集。称 $P$ 的子集 $Y$ 是 $P$ 的(序)滤子，如果 $x \in Y, x \leq y \Rightarrow y \in Y$ 。对偶地，称 $P$ 的子集 $I$ 为 $P$ 的(序)理想，如果 $x \in I, z \leq x \Rightarrow z \in I$ 。特别地，我们称由 $P$ 中的一个元生成的滤子(理想)为主滤子(主理想)。

如果偏序集 $L$ 中任意两个元素都有下确界和上确界，则称 $L$ 是一个格。此时 $\land$ ， $\lor$ 构成 $L$ 上的两个二元运算，因此格 $L$ 也可以记为 $(L, \land, \lor)$ 。进一步，如果格 $L$ 中的两个二元运算 $\land$ 与 $\lor$ 互相满足分配律：

$x \land (y \lor z) = (x \land y) \lor (x \land z)$ ，

$x \lor (y \land z) = (x \lor y) \land (x \lor z)$ ，

则称 $L$ 是一个分配格。若一个分配格的子格满足凸性的定义，则称其为凸子格，我们记格 $L$ 的最大元与最小元分别为 ${\hat{0}}_{L}$ 和 ${\hat{1}}_{L}$ 。

令 $J (P)$ 表示由 $P$ 中的所有滤子按照反包含关系构成的分配格。易知 $\emptyset$ 和 $P$ 是 $J (P)$ 的最大元与最小元。称格 $L$ 的一个元素 $x$ 为交不可约元，若它恰被一个元素覆盖。记 $M i (L)$ 为 $L$ 的全体交不可约元导出的子偏序集。

定理2.1. [10] (有限分配格基本定理)设 $L$ 是一个有限分配格。则存在(同构意义下)唯一的偏序集 $P$ ，使得 $L ≅ J (P)$ 。实际上 $P ≅ M i (L)$ 。

本文研究的图默认为简单、无向的平面二部图，且其顶点用已用黑白两点进行了正常着色。在一般情况下，我们用G代表这样的一个图。

G的完美匹配是指关联G的所有顶点的独立边集合。令 $ℳ (G)$ 表示G的所有完美匹配构成的集合。称G的一条边是允许的，若它属于某个完美匹配，否则称为是禁止的；对于G中的一个圈C，如果其边在G的完美匹配M和E(G)/M中交替出现，则称C为M-交错圈。若图G的所有允许边构成一个连通图，则该图是基本的；若G的每个匹配交错圈及其内部构成的子图都是基本的，则称G是弱基本的。

设M为G的一个完美匹配，对G的一个M-交错圈C，如果按C的顺时针方向匹配边都是从白点到黑点，则称M-交错圈C是一个正常的；否则称为非正常的。设 $R = {r_{1}, \dots, r_{k}} (k \geq 1)$ 为G的两两不交的内面的集合，若存在G的完美匹配M，使所有内面均为(正常)M-交错内面，则称R为G的一个共振形，并称其中的k个内面是相互共振的；而当一个内面的集合中任意两个都构成G的一个共振形，则称该集合中的内面是两两共振的。对任意正常M-交错内面边界上的匹配边和非匹配边对换而得到另一个完美匹配 $M^{'}$ ，这样的操作称为对该面的一个Z-变换或扭转。之后该内面成为非正常 $M^{'}$ -交错的。下面我们给出一般平面二部图的Z-变换图的定义。

定义2.1. 设G是有完美匹配的平面二部图，G的有向Z-变换图 $\vec{Z} (G)$ ：顶点集为 $ℳ (G)$ ，对 $M_{1}, M_{2} \in ℳ (G)$ ，从 $M_{1}$ 到 $M_{2}$ 连一条弧当且仅当对某个 $M_{1}$ 正常交错内面做一次Z-变换得到 $M_{2}$ 。忽略所有弧的方向后就得到通常的Z-变换图 $Z (G)$ 。

有向Z-变换图 $\vec{Z} (G)$ 中无有向圈[3]蕴涵二元关系“ $\leq$ ”是 $M (G)$ 上的偏序关系。 $M (G) : = (ℳ (G), \leq)$ ，对任意 $M_{1}, M_{2} \in ℳ (G)$ ， $M_{1} \leq M_{2}$ 当且仅当在 $\vec{Z} (G)$ 中有一条从 $M_{2}$ 到 $M_{1}$ 的有向路。

令 $G^{↓}$ 表示将平面二部图G的两个色类交换(即将G中的顶点颜色黑白互换)之后得到的平面二部图，则以下的结论是显然的：

命题2.2. [8] $M (G^{↓}) ≅ M^{*} (G)$ ，其中 $M^{*} (G)$ 是偏序集 $M (G)$ 的对偶。

命题2.3. [8]一个有限分配格 $L$ 是匹配型分配格当且仅当其对偶 $L^{*}$ 是匹配型分配格。等价地，对非匹配型的情况仍适用。

定理2.4. [3]设G是平面(弱)基本二部图，则 $M (G)$ 是有限分配格，且 $\vec{Z} (G)$ 是 $M (G)$ 的Hasse图。

定义2.2. [15]称一个有限分配格 $L$ 为匹配型的，如果存在一个平面(弱基本)二部图G使得 $L ≅ M (G)$ ，否则为非匹配型的。

只有一个元素的分配格称为是平凡的，否则是非平凡的。

定义2.3. [16]称一个(非平凡)分配格是既约的，如果它不能表示成两个非平凡分配格的直积。

定理2.5. [16]设 $L$ 是一个有限分配格且有非平凡直积分解 $L = \prod_{i = 1}^{k} L_{i}$ ，则 $L$ 是一个匹配型分配格当且仅当每一个因子 $L_{i} (1 \leq i \leq k)$ 都是匹配型分配格。

注：若 $L$ 是既约的匹配型分配格，则一定存在一个平面基本二部图G，使 $L ≅ M (G)$ 。

定理2.6. [8] [16]设G是一个平面基本二部图，则Z(G)中的一个顶点， $M_{u}$ 是Z(G)的一个割点当且仅当G既有正常 $M_{u}$ -交错环也有非正常 $M_{u}$ -交错环，并且每一个正常 $M_{u}$ -交错环与每一个非正常 $M_{u}$ -交错环都相交。

定义2.4. [8] [16]设 $L$ 是一个有限分配格， $L$ 中的一个元u ( $u \neq {\hat{1}}_{L}, {\hat{0}}_{L}$ )称为一个割元，若 ${\hat{0}}_{L}$ 和 ${\hat{1}}_{L}$ 之间的所有极大链均包含u。称一个有限分配格 $L$ 的割元是 $(m, n)$ 型的，若 $L$ 中恰好有m个元素覆盖u和n个元素被u覆盖。易知，u是 $L$ 的一个 $(m, n)$ 型割元当且仅当 $u$ 是 $L^{*}$ 的一个 $(n, m)$ 型割元。

定理2.7. [8] [16]设G是一个平面基本二部图，且 $M (G)$ 有一个 $(2, n)$ 型割元 $M_{u}$ ，则 $Π_{n}$ 是 $M (G)$ 的一个凸子格。

定理2.8. [8] [16] (割元定理)设 $L$ 是一个有 $(2, n)$ ( $n \geq 2$ )型割元u的有限分配格。若 $L$ 不包含与 $Π_{n}$ 同构的凸子格，则 $L$ 是一个非匹配型分配格。

由定理2.8，我们可以直接判定部分阶数不超过12的含有(2, 2)、(2, 3)型的分配格是非匹配型的。给定两个集合 $A, B$ ，将 $A \oplus B$ 定义为两个集合的对称差。

设G是一个平面基本二部图，若匹配型分配格 $M (G)$ 有(2, 2)型割元 $M_{u}$ ，则G有两个非正常的 $M_{u}$ -交错圈分别设为 $f_{1}$ ， $f_{2}$ ，两个正常的 $M_{u}$ -交错圈分别设为 $g_{1}$ ， $g_{2}$ 。则在 $M (G)$ 中， $M_{u}$ 上有一个四边形，该四边形上的对边是由G中同一个面扭转出来的，则 $f_{1}$ ， $f_{2}$ 是 $M_{u}$ -正常交错的， $g_{1}$ ， $g_{2}$ 是 $M_{u}$ -非正常交错的。则在G中 $f_{1}$ ， $f_{2}$ 是共振的， $g_{1}$ ， $g_{2}$ 也是共振的，又因为 $f_{1}$ ， $f_{2}$ 分别与 $g_{1}$ ， $g_{2}$ 相交，所以此时 $f_{1} \oplus f_{2} \oplus g_{1} \oplus g_{2}$ 是两个不交圈的并，我们记被以上四个圈围在内部的圈为 $h$ 。则由定理2.7、定理2.8 ([8]，定理4.3.6，定理4.3.8)的证明过程可以得到以下引理。

引理2.9。在上述假定和符号下可知， $h$ 及其内部构成子图中的所有环必须在 $f_{1}$ ， $f_{2}$ 没扭转之前，且在 $g_{1}$ ， $g_{2}$ 都扭转之后都能分别扭转；特别地，若 $h$ 本身是个环，则 $h$ 恰在 $f_{1}$ ， $f_{2}$ 都没扭转之前，和在 $g_{1}$ ， $g_{2}$ 都扭转之后分别扭转一次。

设 $P$ 和 $Q$ 是两个不交的偏序集，符号 $P \times Q$ 、 $P$ ⨄ $Q$ 和 $P$ ⨅ $Q$ 分别表示 $P$ 和 $Q$ 的直积(卡氏积)、序和与垂直和； $\hat{P} =$ $1$ ⨄ $P$ ⨄ $1$ ， $n$ 代表n-长链；本文中粗体字母 $L$ 、 $P$ 、 $J (P)$ 表示偏序集而通常的字母 $L$ 、 $P$ 、 $J (P)$ 表示相应偏序集中元素的集合。

3. 主要研究内容

在上文定理2.8中介绍了割元定理，我们将所有可由割元定理判定的非匹配型分配格称为第一类；而将无法用割元定理判定的非匹配型分配格，称为第二类。本节我们给出几个判定第二类非匹配型分配格的判定方法。

引理3.1. [8] [16]下图1中的分配格(a)与(b)均是非匹配型分配格。

证明。(a) 反证法。不妨设存在平面基本二部图G使 $L ≅ M (G)$ 。同引理2.9，记与 $M (G)$ 的割元 $M_{u}$ 关联的两个非正常、两个正常 $M_{u}$ -交错圈及其内部围出的圈分别为 $f_{1}$ ， $f_{2}$ ， $g_{1}$ ， $g_{2}$ ， $h$ ，则 $h$ 是在环 $f_{1}$ ， $f_{2}$ 扭转之前， $g_{1}$ ， $g_{2}$ 扭转之后扭转的，所以 $h$ 一定是G中的一个环。下面再来考虑 $L$ 中最后扭转的面 $h^{'}$ ，因为它当且仅当在 $h$ 扭转完之后才能扭转，所以 $h \cap h^{'} \neq \emptyset$ 。由此， $h^{'}$ 必在由 $f_{1}$ ， $f_{2}$ 和 $g_{1}$ ， $g_{2}$ 围成的圈内部(具体见图1(c))。矛盾。

(b) 反证法。图中的一条路称为悬链，如果其内点都是2度的，且其两个端点的度大于等于3。由图1(a)中的讨论知， $h$ 和 $h^{'}$ 都在由 $f_{1}$ ， $f_{2}$ 和 $g_{1}$ ， $g_{2}$ 围成的圈内部且该圈内再无别的环。因此，它们都分别在 $f_{1}$ ， $f_{2}$ 扭转前和 $g_{1}$ ， $g_{2}$ 扭转后各扭转一次，且两次都是 $h^{'}$ 先于 $h$ 扭转。 $f_{1}$ ， $f_{2}$ 仅在 $h$ 第一次扭转后才扭转，则它们都与 $h$ 相交。由此可知，无论 $h$ 和 $h^{'}$ 的位置关系如何(它们是由C被其一条仅端点在C上的悬链所分而得)， $h$ 、 $h^{'}$ 中至少有一个和 $g_{1}$ ， $g_{2}$ 之一不交，不妨设 $h^{'}$ 和 $g_{1}$ 不交。易知，此时 $h^{'}$ 和 $g_{1}$ 是共振的(具体见图1(d))。

Figure 1. The non-matchable distributive lattice in Lemma 3.1, along with a schematic diagram of its proof

图1. 引理3.1中的非匹配型分配格及其证明示意图

因此在 $M (G)$ 中即 $h^{'}$ 可在 $g_{1}$ 扭转之前扭转，即 $M (G)$ 中比格 $L$ 多一个元素(具体见图1(e))。矛盾。

推论3.2。记下图2中(a)中的分配格为 $N$ ，则 $\hat{N}$ 是以 $N$ 为凸子格的最小阶数的匹配型分配格。

Figure 2. The posets $N$ and $\hat{N}$ in Lemma 3.2 and their corresponding plane elementary bipartite graph $G_{0}$

图2. 引理3.2中的 $N$ 、 $\hat{N}$ 及其对应的平面基本二部图 $G_{0}$

证明。记图2(c)中的平面二部图为 $G_{0}$ ，易知， $\hat{N} ≅ M (G_{0})$ 是匹配型分配格。接下来我们证明 $\hat{N}$ 是以 $N$ 为凸子格的最小阶数的匹配型分配格。

设 $L$ 是任意以 $N$ 为凸子格的阶数尽可能小的匹配型分配格，不妨设 $L$ 也是既约的，则存在平面基本二部图G，使得 $L ≅ M (G)$ 。设在 $L$ 中与 $N$ 最大元对应的完美匹配是 $M_{1}$ ， $M_{1}$ 正常交错的两个环分别为 $a, b$ ，记 $M_{2} : = M_{1} \oplus b$ ，则环a仍是正常 $M_{2}$ -交错的。记环c是除环a以外的另一正常 $M_{2}$ -交错环。记 $M_{3} : = M_{2} \oplus a$ ，则c也是正常 $M_{3}$ -交错的。记另一正常 $M_{3}$ -交错环为d， $M_{4} : = M_{3} \oplus c$ ，则d也是正常 $M_{4}$ -交错的。再记另一正常 $M_{4}$ -交错环为e。由此易知环 $a, b, c, d, e$ 互不相同且c与b共一段奇长路。因为 $N$ 是 $L$ 的一个区间，所以d与b共一段奇长路(否则d是正常 $M_{1} \oplus a$ 交错的，则 ${M^{'}}_{1} : = M_{1} \oplus a \oplus d \in L$ ，由区间的定义， ${M^{'}}_{1}$ 属于 $N$ ，与凸子格定义矛盾)。同理e与a都共一段奇长路。又因为d与a共一段奇长路，e与c共一段奇长路。因此在G的对偶图中环 $a, b, c, d, e$ 围成一个圈，且由 $a, b$ 都是正常 $M_{1}$ -交错的知 $a, b$ 共振，同理 $d, e$ 共振。因此在此圈内部至少有一个G中的内面，记为 $h$ (具体见图2(c))。由G的基本性知，在生成 $L$ 的过程中 $h$ 必定出现，再由引理2.9可知，在生成 $L$ 的过程中， $h$ 一定会至少转两次，即一次在 $a, b$ 没转之前，一次在 $a, b, c, d, e$ 都转之后。则可得 $N \subseteq L$ ，故 $\hat{N}$ 是以 $N$ 为凸子格的最小阶数的匹配型分配格。

由以上引理我们可以得到以下推论：

推论3.3. (i) $N$ ， $1$ ⨄ $N$ 与 $N$ ⨄ $1$ 均是非匹配型分配格。

(ii) 设 $L$ 是任意有限分配格，若 $\exists u \in L$ ，使得 $u$ 生成的主滤子(主理想)与 $N$ ( $N^{*}$ )同构，即 $I [u, 1_{L}] ≅ N$ , $I [0_{L}, u] ≅ N^{*} = N$ )，则 $L$ 是非匹配型分配格(图3)。

Figure 3. $N$ ⨄ $1$ and $1$ ⨄ $N$

图3. $N$ ⨄ $1$ 与 $1$ ⨄ $N$

引理3.4。图4中的四个分配格都是非匹配型分配格。

Figure 4. The non-matchable distributive lattice in Lemma 3.4

图4. 引理3.4中的非匹配型分配格

证明。设 $L$ 为其中一个给定的分配格。反证法，不妨设存在平面基本二部图G使 $L ≅ M (G)$ 。记与 $M (G)$ 的割元 $M_{u}$ 关联的两个非正常和正常M-交错环分别为 $f_{1}$ ， $f_{2}$ 和 $g_{1}, g_{2}$ 。并记由这四个环围成的其内部的圈为h。由引理2.9知，h中的所有环都在 $f_{1}, f_{2}$ 之前且在 $g_{1}$ ， $g_{2}$ 之后各扭转一次，因为格(a)的Hasse图显示存在路径“ $g_{2} \to h \to g_{1}$ ”，所以意味着h的扭转可以发生在 $g_{2}$ 之后， $g_{1}$ 之前。然而，根据引理2.9，h必须在在 $g_{1}$ ， $g_{2}$ 都扭转之后才能扭转，矛盾。

如图所示的标记情况，由图5(a)，我们可得出图5的(b)，(c)，(d)也是非匹配型的，其证明过程是完全一致的。

推论3.5. 设 $n \geq 2$ ，则 $L : = (2 × n) ⨅ (S 1 ⨅ 2)$ 是一个非匹配型分配格。 $n = 2$ 与 $n = 3$ 的情况如下图5中(a)、(b)所示。

Figure 5. The cases of $n = 2$ and $n = 3$ in Corollary 3.5

图5. 推论3.5中 $n = 2$ 与 $n = 3$ 的情况

证明。图5的(a)为 $n = 2$ 的情况。不妨设存在平面基本二部图G，使 $L ≅ M (G)$ ，易知 $L$ 有且仅有一个(2, 2)割点 $M_{u}$ ，设与 $M_{u}$ 关联的2个正常环与非正常环分别为 $f_{1}, f_{2}, g_{1}, g_{2}$ ，由定理2.9的证明过程知， $f_{1}, f_{2}, g_{1}, g_{2}$ 围成一个圈，不妨设为h，易知 $L$ 的Hasse图都显示存在路径“ $g_{2} \to h \to g_{1}$ ”这意味着h的扭转可以发生在 $g_{2}$ 之后， $g_{1}$ 之前。然而，根据引理2.9，h必须在在 $g_{1}$ ， $g_{2}$ 都扭转之后才能扭转，矛盾。

引理3.6. 设下图6中的分配格(a) $C$ 为，则 $C^{'}$ (见图6(b))是以 $C$ 为凸子格的最小阶数的匹配型分配格。

Figure 6. The posets $C$ , $C^{'}$ , and the plane elementary bipartite graph $G_{1}$ corresponding to $C^{'}$ in Proposition 3.6

图6. 命题3.6中的 $C$ 、 $C^{'}$ 、以及 $C^{'}$ 对应的平面基本二部图 $G_{1}$

证明。记图6(c)中的平面二部图为 $G_{1}$ ，易知 $C^{'} ≅ M (G)$ ，所以 $C^{'}$ 是匹配型分配格。接下来我们证明 $C^{'}$ 是以 $C$ 为子格的最小阶数的匹配型分配格。

设 $L$ 是任意以 $C$ 为凸子格的阶数尽可能小的匹配型分配格，不妨设 $L$ 也是既约的，则存在平面基本二部图G，使得 $L ≅ M (G)$ 。设在 $L$ 中与 $C$ 最大元对应的完美匹配是 $M_{1}$ 。令 $M_{1}$ -交错圈为 $a, b$ ， $M_{2} : = M_{1} \oplus b$ ，则a仍是 $M_{1}$ -正常交错的；记 $M_{3} : = M_{2} \oplus a$ ，设环 $c, d$ 均为 $M_{3}$ -正常交错的；记 $M_{4} : = M_{3} \oplus c$ ，则d仍是 $M_{4}$ -正常交错的。综上易知：环 $a, b, c, d$ 互不相同且b与 $c, d$ 共奇长路，a与d共奇长路(否则a是正常 $M_{2} \oplus d$ -交错的，则 ${M^{'}}_{2} = M_{2} \oplus d \oplus a \in L$ ，由凸子格的定义可知， ${M^{'}}_{2}$ 属于 $C$ ，矛盾)。又因为环 $a, b$ 是 $M_{1}$ -正常交错的，所以 $a, b$ 是共振的，同理 $c, d$ 也是共振的，因此在G的对偶图中环 $a, b, c, d$ 围成一个圈，在此圈内部至少有一个G中的内面，记为f (具体见图6(c))。由G的基本性知，在生成 $L$ 的过程中f必定出现。由 $L$ 的结构知，还有另一个环的存在，不妨设其为e，若环e就是环f，则e与 $c, d$ 都共奇长路，与独立性矛盾。如果环e不是环f，则由于 $L$ 包含的环仅有 $a, b, c, d, e$ ， $L$ 缺元，矛盾。

再由引理2.9可知，在生成 $L$ 的过程中，f一定在环 $a, b$ 没转之前， $c, d$ 都转之后各转一次，即 $C^{'}$ ，其对应的平面二部图(具体见图6(c))。故 $C^{'}$ 是以 $C$ 为凸子格的最小阶数的匹配型分配格。

注：推论3.2、引理3.6中的凸子格不能改成子格，否则分别会有反例，具体见图7，(00134)是以 $N$ 为子格的但阶数比 $\hat{N}$ 更小的匹配型分配格；同理(00046)是以 $C$ 为子格，但阶数比 $C^{'}$ 更小的匹配型分配格(有限分配格的标号方法来自[18])。

Figure 7. Counterexample graphs after weakening the convexity in Corollary 3.2 and Lemma 3.6

图7. 减弱推论3.2、引理3.6凸性后的反例图

类似推论3.2，可得到以下推论。

推论3.7。1) $C$ ， $1$ ⨄ $C$ ， $C$ ⨄ $1$ 与 $\hat{C}$ 以及图8中的其余分配格均是以 $C$ 为凸子格的非匹配型分配格。

2) 设 $L$ 是任意有限分配格，若 $\exists u \in L$ ，使得 $u$ 生成的主滤子(主理想)与 $C$ 同构，即 $I [u, 1_{L}] ≅ C (I [0_{L}, u] ≅ C^{*})$ ，则 $L$ 是非匹配型分配格。

3) 设 $L$ 是任意有限分配格，若 $L$ 以 $1$ ⨄ $C$ 为主理想，则 $L$ 是非匹配型分配格(图8)。

推论3.8。设 $L$ 是任意有限分配格，则：

(1) $T$ 为 $\hat{S_{2}}$ ( $Π_{2}$ )、 $\hat{S_{3}}$ 、 $\hat{S_{4}}$ ，或

(2) $T$ 为推论3.2中的(a)、推论3.3中任意一个分配格，或

(3) $T$ 为 $S_{2}$ ⨄ $2$ ，或

(4) $T$ 为引理3.4中四个分配格中的任意一个，或

(5) $T$ 为引理3.6中(a)、3.7中两个分配格，

Figure 8. Some non-matchable distributive lattices with C as a convex sublattice

图8. 以C为凸子格的一些非匹配型分配格

则 $L$ ⨅ $T$ 和 $T^{*}$ ⨅ $L$ 都是非匹配型分配格。

作为以上工作的简单应用，我们可将阶数不超过12阶的非匹配型分配格进行枚举，其中阶数不超过11的非匹配型分配格已经在[1 6]中给出。由以上结论可以把所有阶数不超过12的非匹配型分配格刻画出来。直接可得以下结论。

引理3.9。以下24个分配格都是第一类非匹配型分配格(图9)。

Figure 9. The first type of non-matchable distributive lattices

图9. 第一类非匹配型分配格

本引理中给出了阶数不超过12的所有可以用割元定理证明的非匹配型分配格，共有45个，在此只列出 $L$ 和 $L^{*}$ 之一，因而只有24个，其中3个是自对偶的。

引理3.10。以下26个分配格都是第二类非匹配型分配格(图10)：

Figure 10. The second type of non-matchable distributive lattices

图10. 第二类非匹配型分配格

本引理中给出了阶数不超过12的所有不能用割元定理判定的剩余的非匹配型分配格，共有47个，在此只列出 $L$ 和 $L^{*}$ 之一，因而只有26个，其中5个是自对偶的。

为验证格 $L$ 是匹配型的，由匹配型分配格的基本定义，则需至少构造出一个弱平面二部图G，使之满足 $L ≅ M (G)$ 。易知 $L$ 的Hasse图上的点集是G的完美匹配集，边集为G的内面重集。也就是说 $L$ 的Hasse图呈现了图G中可做Z-变换的交错内面圈的扭转先后顺序以及内圈之间的共振关系，Hasse图中四边形上的对边是由G中同一个面扭转出来的。我们的工作主要如下：1、根据 $L$ 的Hasse图得到扭转顺序；2、根据 $L$ 的Hasse图确定G中面的相邻情况及共振情况；3、画出G的内面，标出顶点的黑白着色。

下面给出一个根据12阶的匹配型分配格构造出与之对应的平面二部图的具体例子及构造过程。

Figure 11. The Hasse diagram of 0034459a and its corresponding plane bipartite graph

图11. 0034459a的Hasse图及其对应的平面二部图

由图11中0034459a的Hasse图可得与其对应的平面二部图中交错内面的扭转顺序以及共振关系：a是 $M_{1}$ -交错内圈，b是a扭转之后才能扭转的内面，因此b与a必定共奇长路，且该奇长路按a顺时针来看，起点是黑点，终点是白点(下同)；在b扭转之后c和d都可以扭转，说明b与c、d分别交奇长路，也说明b与c是共振的，即b与c是两个不交的内面；因为e是在d扭转之后可以扭转的内面，所以d与e也交奇长路，通过观察0034459a的Hasse图可以发现c与e是Hasse图中一个四边形的邻边，则c与e也是共振的，所以c与e不交；且f是c与e均扭转之后才能扭转的内面，所以f与c、e均共奇长路；最后，h与g都是f扭转后才能扭转的内面，因此h与g是共振的，所以f分别与h、g共奇长路。根据以上关系，我们可以画出图11右侧的平面基本二部图及其正常黑白着色(为保证其二部性并避免出现重边，需适当添加一些二度点)。

阶数不超过12阶的分配格共有342个[17]，除上述92个非匹配型分配格之外，针对剩余的250个分配格，我们证明了它们都是匹配型的(对这些匹配型分配格及其对应的平面二部图的构造与讨论，我们将会在另一篇文章中给出)。实际上，我们首先画出了每个分配格对应的至少一个平面二部图，以及构造了该平面二部图对应的以内面为集合、以内面扭转的先后次序为偏序关系的偏序，其中多次扭转的面我们在偏序集中用不同记号分别标出；最后验证了生成的分配格与原分配格是同构的。由此可得以下结论。

引理3.11。除了在引理3.9、引理3.10中出现的分配格外，其余阶数不超过12的分配格均为匹配型分配格。

综上，我们找到了所有的阶数不超过12阶的非匹配型分配格。

定理3.12. 、图10及其对偶共93个分配格是所有阶数不超过12的非匹配型分配格。

基金项目

国家自然科学基金(编号：12161081)。

NOTES

^*通讯作者。

参考文献

[1]	Blair, C. (1984) Every Finite Distributive Lattice Is a Set of Stable Matchings. Journal of Combinatorial Theory, Series A, 37, 353-356. [Google Scholar] [CrossRef]
[2]	Zhang, H. and Zhang, F. (2000) Plane Elementary Bipartite Graphs. Discrete Applied Mathematics, 105, 291-311. [Google Scholar] [CrossRef]
[3]	Lam, P.C.B. and Zhang, H. (2003) A Distributive Lattice on the Set of Perfect Matchings of a Plane Bipartite Graph. Order, 20, 13-29. [Google Scholar] [CrossRef]
[4]	Griüindler, W. (1982) Signifkante elektronenstrukturen für benzenoide kohlenwasserstoffe. Wissenschaftliche Zeitschrift der Universität Halle, 31, 97-116.
[5]	Fournier, J.C. (2003) Combinatorics of Perfect Matchings in Plane Bipartite Graphs and Application to Tilings. Theoretical Computer Science, 303, 333-351. [Google Scholar] [CrossRef]
[6]	Zhang, H., Yang, D. and Yao, H. (2014) Decomposition Theorem on Matchable Distributive Lattices. Discrete Applied Mathematics, 166, 239-248. [Google Scholar] [CrossRef]
[7]	Klavžar, S. and Žigert, P. (2005) Fibonacci Cubes Are the Resonance Graphs of Fibonaccenes. The Fibonacci Quarterly, 43, 269-276. [Google Scholar] [CrossRef]
[8]	Yao, H. and Zhang, H. (2015) Non-Matchable Distributive Lattices. Discrete Mathematics, 338, 122-132. [Google Scholar] [CrossRef]
[9]	王旭. 几类匹配型和非匹配型分配格[D]: [硕士学位论文]. 兰州: 西北师范大学, 2019.
[10]	Brikhoff, G. (1979) Lattice Theory. 3rd Edition, American Mathematical Society.
[11]	黄天民, 徐扬, 赵海良. 格、序引论及其应用[M]. 成都: 西南交通大学出版社,1998.
[12]	Davey, B.A. (1990) Priestley. Introduction to Lattices and Order. Cambridge University Press.
[13]	Bondy, J.A. and Murty, U.S.R. (1982) Graph Theory with Applications. Elsevier Science Publishing Co. Inc.
[14]	(德)R.迪斯特尔. 图论(原书第五版) [M]. (加)于青林, 译. 北京: 科学出版社, 2020.
[15]	Zhang, H. (2010) Direct Sum of Distributive Lattices on the Perfect Matchings of a Plane Bipartite Graph. Order, 27, 101-113. [Google Scholar] [CrossRef]
[16]	姚海元. 平面二部图的完美匹配和分配格结构[D]: [博士学位论文]. 兰州: 兰州大学, 2007.
[17]	Erné, M., Heitzig, J. and Reinhold, J. (2002) On the Number of Distributive Lattices. The Electronic Journal of Combinatorics, 9, 1-23. [Google Scholar] [CrossRef]
[18]	杨德五. 匹配分配格的分解定理[D]: [硕士学位论文]. 兰州: 兰州大学, 2005.

为你推荐

友情链接