2014/09/04 by Djamila Oudrar, Oudrar, Djamila, Maurice Pouzet +1
Computer Science · Mathematics · #03C13 #05C30 #06F99 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1409.1432
openalex publication_date 2014/09/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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 start with 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 (Vx)x∈ X such that the restrictions of R to two finite subsets A and A' of V(R) are isomorphic provided that the traces A∩ Vx and A'∩ Vx have the same size for each x∈ 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∈ \mathfrak A the profile of the age \mathcal 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 by a polynomial then it is at least exponential. This result is a part of classification obtained by Balogh, Bollobás and Morris (2006) for ordered graphs. \it To cite this article: Djamila Oudrar, Maurice Pouzet, C. R. Acad. Sci. Paris, Ser. I.