论文标题
有序图的饱和
Saturation of Ordered Graphs
论文作者
论文摘要
最近，$ 0 $ - $ 1 $矩阵的饱和问题引起了很多关注。该问题可以被视为有序的两分图的饱和问题。在此激励的情况下，我们启动了有序和周期有序图的饱和问题的研究。 我们证明，在这两种情况下，二分法也存在，即，对于（周期性）有序的图，其饱和函数是有界或线性的。我们还确定了大量（周期性）有序图的数量级，这给出了许多表现出可能行为的示例，从而回答了Pálvölgyi的问题。特别是，在有序的情况下，我们定义了有序匹配的自然子类，链接的匹配类别，并开始他们的系统研究，专注于最多三个链接的链接匹配，并证明其中许多具有有限的饱和功能。 在有序和周期性有序的情况下，我们也考虑了二分法也存在的半饱和问题，甚至可以充分表征具有半度性函数的图。
Recently, the saturation problem of $0$-$1$ matrices gained a lot of attention. This problem can be regarded as a saturation problem of ordered bipartite graphs. Motivated by this, we initiate the study of the saturation problem of ordered and cyclically ordered graphs. We prove that dichotomy holds also in these two cases, i.e., for a (cyclically) ordered graph its saturation function is either bounded or linear. We also determine the order of magnitude for large classes of (cyclically) ordered graphs, giving infinite many examples exhibiting both possible behaviours, answering a problem of Pálvölgyi. In particular, in the ordered case we define a natural subclass of ordered matchings, the class of linked matchings, and we start their systematic study, concentrating on linked matchings with at most three links and prove that many of them have bounded saturation function. In both the ordered and cyclically ordered case we also consider the semisaturation problem, where dichotomy holds as well and we can even fully characterize the graphs that have bounded semisaturation function.
