平面图的词表示性质的组合学研究

Both words and graphs are basic objects in Combinatorics. A word is a sequence, finite or infinite, of elements from a finite set, and a graph is a 2-tuple consisting of a vertex set and an edge set. There is a long history to study the relationship between words and graphs in the theory of combinatorics on words, as well as in graph theory. Word-representation of graphs is a very new research direction in this field. Word-representable graphs may find applications in algebra, graph theory, combinatorics on word, computer science, scheduling problems, security patrol problem, etc...A graph G = (V, E) is said to be word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if {x, y} ∈ E. The notion of word-representable graphs has its roots in the study of the celebrated Perkins semigroup. These graphs possess many attractive properties (e.g. a maximum clique in such graphs can be found in polynomial time). It is known that a graph is word-representable iff it can be represented by a word consisting of k copies of each letter for some k. The minimum such k is called graph's representation number. There are several important results on the word-representability of planar graphs, yet word-representable planar graphs are not classified completely. In this project, we will use combinatorial and analytical methods to study word-representability of operations on special planar graphs such as grid graphs and one-skeleton of convex polyhedrons; structural properties of the word-representable planar graphs; and the representation numbers of word-representable planar graphs under given conditions such as a fixed chromatic number, connectivity, vertex degree, grith, etc.

词和图是组合数学中两类经典的组合对象。图的词表示理论是联系词与图的重要理论，该理论源自于Perkins半群的研究，在代数学、计算机编码、调度问题、自然语言处理等方面有重要的应用。一个图G是可词表示的是指存在一个由顶点构成的可重复序列w，满足x和y在G中相邻当且仅当x和y在w中的位置是交错的。这些图具有许多重要的性质，比如其最大团问题是多项式时间可解的。一个图是可词表示的当且仅当其存在每个元素出现k次的词表示；这个k的最小值被称为词表示数。平面图是一类重要的图，对其词表示性质的研究也得到一些重要的结果，但是尚未对其进行完整的刻画。本项目旨在用组合的方法研究平面图的词表示性质，主要研究内容包括：平面图中特殊图及其变换的词表示性质；对平面图的词表示性质的结构进行刻画；分析可词表示的平面图词表示数的上下界等。

本项目的研究背景源于词的组合学，旨在研究可平图的词表示性质，但随着研究的逐步进行以及对原问题的了解逐步深入，我们对项目的研究内容进行了反思并合理修正，具体研究内容为：.1.项目前期按照研究计划，我们借助计算机逐一筛选出了顶点数不大于18的极小的不可词表示平面图，发现并不能够找到一个相对小的禁用子图集合来刻画可词表示的可平图。但是，通过这些筛选的图中发现门槛图是可词表示的。门槛图是一类特殊的分裂图，我们进而研究了分裂图的词表示性质。研究中我们套用了项目的研究路线和方法，归纳并证明了可词表示的分裂的禁用模式。.2.根据前期的结果，我们对研究内容进行了延拓及修正，将研究目标转向了词表示的推广形式：通用词和通用偏词。我们系统的研究了通用词和通用偏词的稳健性问题：①研究了n元字符集上所有k长词构成集合的通用词和通用环词性质，探究了在删除给定个数的元素后通用词的存在性问题，对删除点集的各种情况进行了分析和讨论，解决了等概率地删除集合中给定词后存在通用词和通用环词的概率问题。②结合偏词理论，在通用词中引入可变字符后定义了通用偏词，较为系统地讨论了词模式和集合分拆的通用偏词的存在性问题，建立了通用偏词与图和组合结构之间的关系，对词模式和集合分拆的偏词的存在性及其结构作了完整的刻画。.综上所述，虽然本项目的最终研究内容与一开始的设想有所出入，但还是秉持了筛选结构、提出猜想和分析论证的研究方法，并取得了较为完整的结果，基本完成研究目标。