Jumps in speeds of hereditary properties in finite relational languages
Jumps in speeds of hereditary properties in finite relational languages
复制标题
有限关系语言中遗传属性的速度跳跃
DOI：
10.1016/j.jctb.2021.12.004
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Terry, C.A.
中科院分区：
文献类型：
--
作者：
Laskowski, M.C.;Terry, C.A.
给定一个有限关系语言L，遗传L-性质是一类在同构和子结构下封闭的有限L-结构H。H的速度是将整数n ≥ 1发送到具有基础集合{1，.，n}。本文描述了遗传L-性质的可能速度的许多新的跳跃，其中L是任何有限关系语言。特别是，我们的特点的多项式和阶乘范围内的跳跃，并显示它们基本上是相同的情况下，图。在阶乘范围的结果是新的所有例子需要一个arity大于2的语言，包括设置的遗传性质的k-一致超图的k> 2。此外，通过改编Balogh，Bollobás和Weinreich的例子，我们证明了对于所有k ≥ 2，k-一致超图存在遗传性质，其速度在倒数第二范围的上界和下界附近的函数之间振荡，排除了许多自然函数在该范围内的跳跃。我们关于阶乘值域的定理使用了与互代数性概念相关的模型论工具。
Given a finite relational language L, a hereditary L-property is a class H of finite L-structures closed under isomorphism and substructure. The speed of H is the function which sends an integer n≥ 1 to the number of distinct elements in H with underlying set {1,..., n}. In this paper we give a description of many new jumps in the possible speeds of a hereditary L-property, where L is any finite relational language. In particular, we characterize the jumps in the polynomial and factorial ranges, and show they are essentially the same as in the case of graphs. The results in the factorial range are new for all examples requiring a language of arity greater than two, including the setting of hereditary properties of k-uniform hypergraphs for k> 2. Further, adapting an example of Balogh, Bollobás, and Weinreich, we show that for all k≥ 2, there are hereditary properties of k-uniform hypergraphs whose speeds oscillate between functions near the upper and lower bounds of the penultimate range, ruling out many natural functions as jumps in that range. Our theorems about the factorial range use model theoretic tools related to the notion of mutual algebraicity.
登录
查看更多内容
关于封闭排列类的增长率
影响因子：
0.7
作者：
Tomás Kaiser;Martin Klazar
通讯作者：
Martin Klazar
没有线性循环的超图的数量
DOI：
10.1016/j.jctb.2018.07.003
发表时间：
2017
期刊：
J. Comb. Theory B
影响因子：
--
作者：
J. Balogh;Bhargav P. Narayanan;J. Skokan
通讯作者：
J. Skokan
遗传财产中几乎所有图形的结构
DOI：
10.1016/j.jctb.2010.10.001
发表时间：
2009
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Alon;J. Balogh;B. Bollobás;R. Morris
通讯作者：
R. Morris
仅具有可数个非同构子结构的二元关系结构
影响因子：
0.6
作者：
D. Macpherson;J. Schmerl
通讯作者：
J. Schmerl
Füredi-Hajnal 猜想中线性界的扩展
DOI：
10.1016/j.aam.2006.05.002
发表时间：
2005
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
Martin Klazar;A. Marcus
通讯作者：
A. Marcus