

























We present a structural approach of some results about jumps in the behavior of the profile (alias generating function) of hereditary classes of finite structures. We consider the following notion due to N.Thiéry and the second author. A \emph{monomorphic decomposition} of a relational structure $R$ is a partition of its domain $V(R)$ into a family of sets $(V_x)_{x\in X}$ such that the restrictions of $R$ to two finite subsets $A$ and $A'$ of $V(R)$ are isomorphic provided that the traces $A\cap V_x$ and $A'\cap V_x$ have the same size for each $x\in X$. Let $\mathscr S_μ$ be the class of relational structures of signature $μ$ which do not have a finite monomorphic decomposition. We show that if a hereditary subclass $\mathscr D$ of $\mathscr S_μ$ is made of ordered relational structures then it contains a finite subset $\mathfrak A$ such that every member of $\mathscr D$ embeds some member of $\mathfrak A$. Furthermore, for each $R\in \mathfrak A$ the profile of the age $\age(R)$ of $R$ (made of finite substructures of $R$) is at least exponential. We deduce that if the profile of a hereditary class of finite ordered structures is not bounded above by a polynomial then it is at least exponential. For ordered graphs, this result is a part of classification obtained by Balogh, Bollobás and Morris (2006).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。