论文标题
关于抽象的色数及其对有限公理理论的可计算性
On the abstract chromatic number and its computability for finitely axiomatizable theories
论文作者
论文摘要
著名的Erdős-石 - simonovits定理以$ \ nathcal {f} $ - 免费图表为$ 1-1/（χ（χ（\ Mathcal {f}）-1） - 1） + o（o（o（o（o（nat）），$χ（\ qutcal {f}）在[L.的示例25和31中N. Coregliano和A. A. Razborov。密集组合对象的语义极限。 Uspekhi Mat。 Nauk, 75(4(454)):45-152, 2020], it was shown that this result can be extended to the general setting of graphs with extra structure: the maximum asymptotic density of a graph with extra structure without some induced subgraphs is $1 - 1/(χ(I) - 1) + o(1)$ for an appropriately defined abstract chromatic number $χ(I)$.顾名思义，抽象色编号的原始公式是如此抽象，以至于其（算法）可计算性打开。 在本文中，我们两者都将此结果扩展到表征$ t $ cliques的最大渐近密度，这些图的图表具有额外的结构，而没有某些引起的子图，而$χ（i）$，我们提出了一个更具体的$χ（i）$的公式，该公式可以在额外的结构和禁止的子量表上表现出其可计算性，可以表现出一定量的priveners fripers fripers fripers fripers a prionders exiomiz。我们的$χ（i）$的替代公式利用了Ramsey定理的党派版本，用于一阶关系语言的结构。
The celebrated Erdős--Stone--Simonovits theorem characterizes the asymptotic maximum edge density in $\mathcal{F}$-free graphs as $1 - 1/(χ(\mathcal{F})-1) + o(1)$, where $χ(\mathcal{F})$ is the minimum chromatic number of a graph in $\mathcal{F}$. In Examples 25 and 31 of [L. N. Coregliano and A. A. Razborov. Semantic limits of dense combinatorial objects. Uspekhi Mat. Nauk, 75(4(454)):45-152, 2020], it was shown that this result can be extended to the general setting of graphs with extra structure: the maximum asymptotic density of a graph with extra structure without some induced subgraphs is $1 - 1/(χ(I) - 1) + o(1)$ for an appropriately defined abstract chromatic number $χ(I)$. As the name suggests, the original formula for the abstract chromatic number is so abstract that its (algorithmic) computability was left open. In this paper, we both extend this result to characterize maximum asymptotic density of $t$-cliques in of graphs with extra structure without some induced subgraphs in terms of $χ(I)$ and we present a more concrete formula for $χ(I)$ that allows us to show its computability when both the extra structure and the forbidden subgraphs can be described by a finitely axiomatizable universal first-order theory. Our alternative formula for $χ(I)$ makes use of a partite version of Ramsey's Theorem for structures on first-order relational languages.
