阶数不超过12的非匹配型分配格的枚举
Enumeration of Non-Matchable Distributive Lattices of Order Not Exceeding 12
DOI: 10.12677/pm.2025.1511287, PDF,    国家自然科学基金支持
作者: 张诗晗, 王海艳, 姚海元*：西北师范大学数学与统计学院，甘肃 兰州
关键词: 完美匹配；匹配型分配格；非匹配型分配格；凸子格；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] 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.

为你推荐