论文标题
图形和Theons的随机性弱
Weak randomness in graphons and theons
论文作者
论文摘要
如果存在Graphon $ W $，则将图形的遗传家庭$ \ MATHCAL {f} $非常持久，使得在所有子图中，$ w $ of $ w $ of $ w $，$ \ mathcal {f} $确切地是有限图类别具有$ W'$的正密度的有限图。我们的第一个结果是对遗传图的完整表征，这些遗传因素坚持不懈地持续存在，因为那些是在替代下封闭的。 我们将图形子称为弱随机性上方的自相似性属性。遗传族$ \ nathcal {f} $据说具有弱随机的erdős - hajnal属性（WR），如果每个图形限制为$ \ Mathcal {f} $中的图形限制都具有弱随机的子图。在替代下封闭的图形家庭中，我们完全将属于WR的家庭描述为“少数”素图的家庭。 我们还使用Theons的理论将上述结果扩展到有限关系语言中的结构。
Call a hereditary family $\mathcal{F}$ of graphs strongly persistent if there exists a graphon $W$ such that in all subgraphons $W'$ of $W$, $\mathcal{F}$ is precisely the class of finite graphs that have positive density in $W'$. Our first result is a complete characterization of the hereditary families of graphs that are strongly persistent as precisely those that are closed under substitutions. We call graphons with the self-similarity property above weakly random. A hereditary family $\mathcal{F}$ is said to have the weakly random Erdős--Hajnal property (WR) if every graphon that is a limit of graphs in $\mathcal{F}$ has a weakly random subgraphon. Among families of graphs that are closed under substitutions, we completely characterize the families that belong to WR as those with "few" prime graphs. We also extend some of the results above to structures in finite relational languages by using the theory of theons.
