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 monomorphic decomposition of a relational structure R is a partition of its domain V(R) into a family of sets <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$(V_x)_{x\in X}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>V</mi> <mi>x</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>x</mi> <mo>∈</mo> <mi>X</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> such that the restrictions of R to two finite subsets A and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$A'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>A</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> of V(R) are isomorphic provided that the traces <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$A\cap V_x$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo>∩</mo> <msub> <mi>V</mi> <mi>x</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$A'\cap V_x$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>A</mi> <mo>′</mo> </msup> <mo>∩</mo> <msub> <mi>V</mi> <mi>x</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> have the same size for each <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$x\in X$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>x</mi> <mo>∈</mo> <mi>X</mi> </mrow> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathscr {S}_\mu $</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">S</mi> <mi>μ</mi> </msub> </math></EquationSource> </InlineEquation> be the class of relational structures of signature <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\mu ,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>μ</mi> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> which do not have a finite monomorphic decomposition. We show that if a hereditary subclass <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\mathscr {D}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">D</mi> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\mathscr {S}_\mu $</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">S</mi> <mi>μ</mi> </msub> </math></EquationSource> </InlineEquation> is made of ordered relational structures, then it contains a finite subset <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\mathfrak A$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="fraktur">A</mi> </math></EquationSource> </InlineEquation> such that every member of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\mathscr {D}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">D</mi> </math></EquationSource> </InlineEquation> embeds some member of <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\mathfrak A$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="fraktur">A</mi> </math></EquationSource> </InlineEquation>. Furthermore, for each <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$R\in \mathfrak A,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo>∈</mo> <mi mathvariant="fraktur">A</mi> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> the profile of the age <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\mathcal {A}(R)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">A</mi> <mo stretchy="false">(</mo> <mi>R</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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 et al. (Eur J Combin 8:1263–1281, 2006).

Ordered Structures with No Finite Monomorphic Decomposition: Application to the Profile of Hereditary Classes

期刊论文
发表日期：

2025年12月3日

查看全文

Djamila Oudrar,
Maurice Pouzet

摘要

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 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}$ ${(V_{x})}_{x \in X}$ such that the restrictions of R to two finite subsets A and $A'$ $A^{'}$ of V(R) are isomorphic provided that the traces $A\cap V_x$ $A \cap V_{x}$ and $A'\cap V_x$ $A^{'} \cap V_{x}$ have the same size for each $x\in X$ $x \in X$ . Let $\mathscr {S}_\mu $ $S_{μ}$ be the class of relational structures of signature $\mu ,$ $μ,$ which do not have a finite monomorphic decomposition. We show that if a hereditary subclass $\mathscr {D}$ $D$ of $\mathscr {S}_\mu $ $S_{μ}$ is made of ordered relational structures, then it contains a finite subset $\mathfrak A$ $A$ such that every member of $\mathscr {D}$ $D$ embeds some member of $\mathfrak A$ $A$ . Furthermore, for each $R\in \mathfrak A,$ $R \in A,$ the profile of the age $\mathcal {A}(R)$ $A (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 et al. (Eur J Combin 8:1263–1281, 2006).