STRUCTURES WITH NO FINITE MONOMORPHIC DECOMPOSITION:

Abstract

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 (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 Sµ be the class of relational structures of signature µ which do not have a finite monomorphic decomposition. We show that if a hereditary subclass D of Sµ is made of ordered relational structures then it contains a finite subset A such that every member of D embeds some member of A. Furthermore, for each R ∈ A the profile of the age 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.

Keywords

• ordered set
• well quasi-ordering
• relational structures
• profile
• asymptotic enumeration
• indecomposability
• graphs
• tournaments
• permutations

-

The profile of a class C of finite relational structures is the integer function ' C which counts for each non negative integer n the number of members of C on n elements, isomorphic structures being identified. The behavior of this function has been discussed in many papers, particularly when C is hereditary (that is contains every substructure of any member of C ) and is made of graphs (directed or not), tournaments, ordered sets, ordered graphs or ordered hypergraphs. Futhermore, thanks to a result of Cameron [ 7 ], it turns out that the line of study about permutations (see [1]) originating in the Stanley-Wilf conjecture, solved by Marcus and Tardös (2004) [ 20 ], falls under the frame of the profile of hereditary classes of ordered relational structures (see [ 23, 25 ]). The results show that the profile cannot be arbitrary: there are jumps in its possible growth rate. Typically, its growth is polynomial or faster than every polynomial ([ 29 ] for ages, see [ 34 ] for a survey) and for several classes of structures, it is either at least exponential (e.g. for tournaments [4, 6], ordered graphs and hypergraphs [ 2, 3, 16 ] and permutations [ 14 ]) or at least with the growth of the partition function (e.g. for graphs [5]). For more, see the survey of Klazar [ 17 ].

In this paper, we consider hereditary classes of ordered relational structures. We describe those with polynomially bounded profile, we identify those with unbounded polynomial profile which are minimal w.r.t. inclusion and prove that their profile is exponential. The case of ordered binary relational structures and particularly the case of ordered ∗The first author was supported by CMEP-Tassili grant.

Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). irreflexive directed graphs are treated in Chapter 8 of [ 22 ] and are presented in [ 26 ]. On the surface, the cases of ordered binary relational structures and the case of ordered relational structures are similar. But the case of ternary relations is more involved. oLredteursopnreVseanntdoeuarcmh a⇢ijn irsesaunltjs-.aEryacrhelasttriuocntaulrsetrwuectcuornesoidneVr i,sthoaftthiseafosurmbseRt o∶=f V(Vn,j≤f,o(r⇢ sjo)jm∈Je)n,ownh-neerega≤tiviseainlitnegeearr nj , the arity of ⇢ j . We will say that the sequence µ ∶= (nj )j∈J is the restricted signature of R. The age of R is the set A(R) consisting of the structures induced by R on the finite subsets of V , these structures being considered up to isomorphy. A relational structure of the form (V, ≤) where ≤ is a linear order on V is a chain; if it is of the form ≤ ) where ≤ and ≤′ are two linear orders on V this is a bichain, and if it is of the form G ∶= (V, ≤, ⇢ ) where B ∶= (V, ≤, ′ ⇢ is a binary relation this is an ordered directed graph. Chains, bichains and ordered directed graphs are the basic examples of ordered structures.

An interval decomposition of R is a partition P of V into intervals I of the chain C ∶= (V, ≤) such that for every integer n and every pair A, A′ of n-element subsets of V , the induced structures on A and A′ are isomorphic whenever the traces A ∩ I and A′ ∩ I have the same number of elements for each interval I. For example, if R is the bichain (V, ≤, ≤′), P is an interval decomposition of V iff each block I is an interval for each of the two orders and they coincide or are opposite on I (see [ 21 ]). If a relational structure R has an interval decomposition decomposition into finitely many blocks, say k + 1, then trivially, the profile of A(R) is bounded by some polynomial whose degree is, at most, k. According to a result of [ 35 ] this must be a quasi-polynomial, that is a sum ak(n)nk + + a0(n) whose coefficients ak(n), . . . , a0(n) are periodic functions. Here, we show that this is in fact a polynomial.

We prove that essentially the converse holds.

Theorem 1.1. Let C be a hereditary class of finite ordered relational structures with a finite restricted signature µ. Then, either there is some integer k such that every member of C has an interval decomposition into at most k + 1 blocks, in which case C is a finite union of ages of ordered relational structures, each having an interval decomposition into at most k + 1 blocks, and the profile C is a polynomial, or the profile of C is at least exponential. The jump of the growth of profile from polynomial to exponential was obtained for bichains by Kaiser and Klazar [ 14 ] and extended to ordered graphs by Balogh, Bollobás and Morris (2006) (Theorem 1.1 of [3]). Their results go much beyond exponential profile.

The first step of the proof of Theorem 1.1 is a reduction to the case where C is of the form A(R). For that, we prove the following lemma: Lemma 1.2. If a hereditary class C of finite ordered relational structures with a finite signature µ contains for every integer k some finite structure which has no interval decomposition into at most k + 1 blocks, then it contains a hereditary class A with the same property which is minimal w.r.t. inclusion.

Clearly, A cannot be the union of two proper hereditary classes, hence it must be up-directed w.r.t. embeddability. Thus, according to an old and well know result of Fraïssé [ 8 ] p.279, this is the age of some relational structure R. Clearly, R is ordered and does not have a finite interval decomposition. Hence our reduction is done. For the second step, we introduce the class Dµ of ordered relational structures of signature µ, µ finite, which do not have a finite interval decomposition. We define an equivalence relation ≡R on the domain of a relational structure R whose classes form a monomorphic decomposition, a notion previously introduced in [ 35 ]. This equivalence is an intersection of equivalences ≡k,R. When R is ordered, there is some integer k such that ≡R and ≡k,R coincide. Using Ramsey’s theorem, we prove that Theorem 1.3. There is a finite subset A made of incomparable structures of Dµ such that every member of Dµ embeds some member of A.

Note that if D is the subclass of Dµ made of bichains then A ∩ D has twenty elements [ 21 ]. If D is made of ordered reflexive (or irreflexive) directed graphs, A ∩ D contains 1246 elements (cf Theorem 8.23 of [ 26 ]). The members of A have a special form. There are almost multichainable (a notion introduced by the second author in his thèse d’État [ 29 ] which appeared in [ 32 ] and [ 30 ]).

Next, we prove that the profile of members of A grows at least exponentially.

Theorem 1.4. : If R ∈ Dµ(k) then the profile ' R is at least exponential. Indeed, for n large enough it satisfies ' R(n) ≥ d.cn where c is the largest solution of Xk+1 − Xk − 1 = 0 and d is a positive constant depending upon k. In the case of ordered undirected graphs, it was proved in [3] that it grows as fast as the Fibonacci sequence. From Lemma 1.2 and Theorem 1.1, we can deduce the following.

Corollary 1.5. If the profile of a hereditary class C of finite ordered relational structures (with a finite restricted signature µ) is not bounded by a polynomial then it contains a hereditary class A with this property which is minimal w.r.t. inclusion.

Proof. If the profile of C is not bounded by a polynomial then for every integer k it contains some finite structure which has no interval decomposition into at most k + 1 blocks. According to Lemma 1.2 it contains a hereditary class A with this property which is minimal w.r.t. inclusion. As already observed, there is some R such that A = A(R). According to Theorem 1.1, the profile of A is exponential. Since the profile of every proper subclass of A is bounded by a polynomial, A is minimal.

This result holds for arbitrary hereditary classes of relational structures (provided that their arity is finite). It appears in a somewhat equivalent form as Theorem 0.1 of [ 35 ]. It is not trivial, the main argument relies on a result going back to the thesis of the second author [ 29 ], namely Lemma 4.1 p. 23 of [ 35 ]. No complete proof has been yet published. The proof of Corollary 1.5 is complete.

The proof of Lemma 1.2 relies on properties of well-quasi-ordering and of ordered structures. The proof of Theorem 1.3 relies on Ramsey’s theorem. These results are part of the study of monomorphic decompositions of a relational structure, a notion introduced in [ 35 ] in the sequel of R. Fraïssé who invented the notion of monomorphy and C. Frasnay who proved the central result about this notion [ 9 ]. Indeed, an ordered relational structure has a finite interval decomposition iff it has a finite monomorphic decomposition. The profile of a class of finite relational structures, not necessarily ordered, each admitting a finite monomorphic decomposition in at most k + 1 blocks, is the union of finitely many ages of relational structures admitting a finite monomorphic decomposition in at most k + 1 blocks and is a quasi-polynomial (this is the main result of [ 35 ]). Lemma 1.2 extends. But, we do not know if Theorem 1.3 extends in general. We state that as a conjecture.

Let Sµ be the class of all relational structures of signature µ, µ finite, without any finite monomorphic decomposition. Conjecture 1.6. There is a finite subset A made of incomparable structures of Sµ such that every member of Sµ embeds some member of A.

The difficulty is with ternary structures. We may note that if one restricts Sµ to tournaments, there is a set A with twelve elements [6]. The first author has shown that the conjecture holds if Sµ consists of binary structures. She proved that for ordered reflexive graphs, A contains 1242 elements. We show that if we consider the class of undirected graphs, A has ten elements. The proof is easy, we give it in order to illustrate in a simple setting the technique used in the proof of Theorem 1.3. We may note that a graph has a finite monomorphic decomposition iff it decomposes into a finite lexicographic sum of cliques and independent sets. Hence our latter result can be stated as follows: Proposition 1.7. There are ten infinite graphs such that a graph does not decompose into a finite lexicographic sum of cliques and independent sets iff it contains a copy of one of these ten graphs.

We may note that some of these graphs have polynomial profile, hence our machinery is not sufficient to illustrate the jump in profile beyond polynomials.

Results of this paper are included in Chapter 7 of the thesis of the first author [ 26 ]. They have been presented in part at ICGT 2014 (June 30-July 4 2014, Grenoble) [ 24 ]. Proofs are included in the full version of the paper. Acknowledgement We thank an anonymous referee who pointed out an analogy between the jumps in profile of finite structures and the Main Gap Theorem of Shelah for infinite structures, showing that exponential growth is obtained for unstable theories, and referred to [ 36 ] and [ 12 ]. [1] M.H. Albert and M.D. Atkinson, Simple permutations and pattern restricted permutations. Discrete Mathematics, 300 (2005) 1–15. [2] J. Balogh, B. Bollobás and R. Morris, Hereditary properties of partitions, ordered graphs and ordered hypergraphs.

European Journal of Combinatorics, 8, (2006) 1263–1281. [3] J. Balogh, B. Bollobás and R. Morris, Hereditary properties of ordered graphs, in Topics in discrete mathematics, 179–213, Algorithms Combin., 26, Springer, Berlin, 2006. [4] J. Balogh, B. Bollobás and R. Morris, Hereditary properties of tournaments. Electron. J. Combin. 14 (2007), no. 1,

Research Paper 60, 25 pp. [5] J. Balogh, B. Bollobás, M. Saks and V. T. Sós, The unlabelled speed of a hereditary graph property. J. Combinatorial

Theory, series B 99 (2009) 9–19. [6] Y. Boudabous and M. Pouzet, The morphology of infinite tournaments; application to the growth of their profile.

European Journal of Combinatorics. 31 (2010) 461-481.

References

[7] P. J Cameron , Homogeneous permutations . Permutation patterns (Otago , 2003 ). Electron. J. Combin . 9 ( 2002 /03), no. 2 , Research paper 2, 9 pp.

[8] R. Fraïssé , Theory of relations. Second edition , North-Holland Publishing Co., Amsterdam, 2000 .

[9] C. Frasnay , Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes . Thèse. Paris. Annales Institut Fourier Grenoble 15 ( 1965 ), pp. 415 - 524 .

[10] C. Frasnay , Détermination du degré optimal dm de monomorphie pour les structures relationnelles au plus m-aires . Math. Rep. Acad. Sci. Canada vol. 12 ( 4 ) p. 141 - 146 .

[11] D.H. Gottlieb , A class of incidence matrices , Proc. Amer. Math. Soc . 17 ( 1966 ), 1233 - 1237 .

[12] B. Hart , E.Hrushovski, M.C. Laskowski , The uncountable spectra of countable theories . Ann. of Math. (2) 152 ( 2000 ), no. 1 , 207 ? 257 .

[13] G. Higman , Ordering by divisibility in abstract algebras . Proc. London Math. Soc. , ( 3 ) 2 ( 1952 ) 326 - 336 .

[14] T. Kaiser , M. Klazar , On growth rates of closed permutation classes . Permutation patterns (Otago , 2003 ). Electron. J. Combin . 9 ( 2002 /03), no. 2 , Research paper 10 , 20 pp.

[15] W. Kantor , On incidence matrices of finite projection and affine spaces , Math.Zeitschrift 124 ( 1972 ), 315 - 318 .

[16] M. Klazar , On growth rates of permutations, set partitions, ordered graphs and other objects . Electron. J. Combin . 15 ( 2008 ), no. 1 , Research Paper 75 , 22 pp.

[17] M. Klazar , Overview of general results in combinatorial enumeration , in Permutation patterns, London Math. Soc. Lecture Note Ser. , Vol. 376 , ( 2010 ), 3 - 40 , Cambridge Univ. Press, Cambridge.

[18] G. Lopez , Sur la détermination d'une relation par les types d'isomorphie de ses restrictions . C. R. Acad. Sci. Paris Sér. A-B 275 ( 1972 ) A951 - A953 .

[19] G. Lopez , L' indéformabilité des relations et multirelations binaires . Z. Math. Logik Grundlag . Math. 24 ( 1978 ), no. 4 , 303 - 317 .

[20] A. Marcus , G. Tardös, Excluded permutation matrices and the Stanley-Wilf conjecture , J. Combin. Theory, Ser. A 107 ( 2004 ), 153 - 160 .

[21] T. Monteil and M. Pouzet , From the complexity of infinite permutations to the profile of bichains . In ROGICS'08: International Conference on Relations, Orders and Graphs: Interaction with Computer Science , pages 1 - 6 , 2008 .

[22] D. Oudrar , Sur l'énumération de structures discrète. Une approche par la théorie des relations . Thèse de Doctorat. Université des sciences et de la technologie Houari Boumediene, U.S.T.H.B., Alger (28 Septembre 2015 ) 248 pages. Available at arXiv: 1604 .05839[math.CO].

[23] D. Oudrar , M. Pouzet , Profile and hereditary classes of relational structures , Proceedings ISOR'11, International Symposium on Operational Research , Algiers , Algeria , May 30-June 2, 2011 , H.Ait Haddadene , I.Bouchemakh, M. Boudar , S.Bouroubi (Eds) LAID3 .

[24] D. Oudrar , M. Pouzet , Décomposition monomorphe des structures relationelles et profil de classes héréditaires. 7 pp, 2014 , arXiv: 1409 .1432[math.CO].

[25] D. Oudrar , M. Pouzet , Profile and hereditary classes of relational structures , J. of MVLSC Volume 27 , Number 5- 6 ( 2016 ), pp. 475 - 500 .

[26] D. Oudrar , Hereditary classes of ordered binary structures, preprint, 28pp . dec. 2018 .

[27] M. Pouzet , Un belordre d'abritement et ses rapports avec les bornes d'une multirelation . Comptes rendus Acad. Sci . Paris, Sér A 274 ( 1972 ), pp. 1677 - 1680 .

[28] M. Pouzet , Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations , Math. Zeitschr. 150 ( 1976 ), no. 2 , 117 - 134 .

[29] M. Pouzet , Sur la théorie des relations , Thèse d'État, Université Claude-Bernard, Lyon 1 , 1978 .

[30] M. Pouzet , Relation minimale pour son âge . Z. Math. Logik Grundlag . Math. 25 ( 1979 ), 315 - 344 .

[31] M. Pouzet , The asymptotic behavior of a class of counting functions . Combinatorics 79 Part 2 . M. Deza and I.G .Rosenberg, Eds., Annals of Discrete Math. 9 ( 1980 ), 223 - 224 .

[32] M. Pouzet , Relation impartible . Dissertationnes 103 ( 1981 ), 1 - 48 .

[33] M. Pouzet , Application de la notion de relation presque -enchaînable au dénombrement des restrictions finies d'une relation , Z. Math. Logik Grundlag. Math., 27 ( 1981 ), 289 - 332 .

[34] M. Pouzet , The profile of relations, Glob . J.Pure Applied Math. 2 ( 2006 ) 237 - 272 (Proceedings of the 14th symposium of the Tunisian Mathematical Society, held in Hammamet, March 20 -23, 2006 ).

[35] M. Pouzet and N. M. Thiéry . Some relational structures with polynomial growth and their associated algebras I: Quasi-polynomiality of the profile . Electron. J. Combin. , 20 ( 2 ):Paper 1, 35 , 2013 .

[36] S. Shelah , Classification theory and the number of nonisomorphic models , Volume 92 , 2nd Edition , North Holland, 1990 .