论文标题
最小的初级年龄，单词和置换图
Minimal prime ages, words and permutation graphs
论文作者
论文摘要
本文是对遗传类别有限图的研究的贡献。我们根据它们所包含的主要结构数量对这些类进行分类。我们认为这样的类是\ emph {minimal prime}：包含无限很多数量但每个适当的遗传子类仅包含许多素数的类。我们对此类课程进行完整的描述。实际上，这些课程中的每个班级都是一个良好的序列（W.Q.O）年龄，并且有许多班级。这些年龄中有11个几乎是多数的。当添加W.Q.O中的标签时，它们仍然是W.Q.O，因此具有有限的界限。其中五个时代很耗尽。在其余的添加一个标签时，只有许多界限仍保留，并且这些标签具有有限的界限（除了无限路径的年龄及其补充）。其他人的界限无限。 除六个示例外，我们表征的这些年龄的成员是置换图。实际上，每个年龄不在11个时代都是图形的年龄，与整数上的统一反复出现有关。还提供了最小的PRIME类别的POSET和BICHAINS的描述。 我们的结果支持以下猜想：如果将W.Q.O设置的标签添加到这些图表时，如果遗传类有限的图不会保留W.Q.O，则如果我们仅在这些图中添加两个常数，则不会是W.Q.O Our description of minimal prime classes uses a description of minimal prime graphs \cite{pouzet-zaguia2009} and previous work by Sobrani \cite{sobranithesis, sobranietat} and the authors \cite{oudrar, pouzettr} on properties of uniformly recurrent words and the associated graphs.我们描述的完整性基于Chudnovsky，Kim，Oum和Seymour \ Cite {Chudnovsky}的分类结果，Malliaris和Terry \ Cite \ Cite {Malliaris}。
This paper is a contribution to the study of hereditary classes of finite graphs. We classify these classes according to the number of prime structures they contain. We consider such classes that are \emph{minimal prime}: classes that contain infinitely many primes but every proper hereditary subclass contains only finitely many primes. We give a complete description of such classes. In fact, each one of these classes is a well-quasi-ordered (w.q.o) age and there are uncountably many of them. Eleven of these ages are almost multichainable; they remain w.q.o when labels in a w.q.o are added, hence have finitely many bounds. Five ages among them are exhaustible. Among the remaining ones, only countably many remain w.q.o when one label is added, and these have finitely many bounds (except for the age of the infinite path and its complement). The others have infinitely many bounds. Except for six examples, members of these ages we characterize are permutation graphs. In fact, every age which is not among the eleven ones is the age of a graph associated to a uniformly recurrent word on the integers. A description of minimal prime classes of posets and bichains is also provided. Our results support the conjecture that if a hereditary class of finite graphs does not remain w.q.o when adding labels from a w.q.o set to these graphs, then it is not w.q.o if we add just two constants to each of these graphs Our description of minimal prime classes uses a description of minimal prime graphs \cite{pouzet-zaguia2009} and previous work by Sobrani \cite{sobranithesis, sobranietat} and the authors \cite{oudrar, pouzettr} on properties of uniformly recurrent words and the associated graphs. The completeness of our description is based on classification results of Chudnovsky, Kim, Oum and Seymour \cite{chudnovsky} and Malliaris and Terry \cite {malliaris}.
