.png){kind=icon}
返回
Countable Ramsey
.png){kind=icon}
PRE
AI
DOI：10.1142/S0219061325500217.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
著名的Erdős-Hajnal猜想指出，在任何适当的遗传类有限图中，我们都保证存在一个大小为n(c)的团或反团，这比拉姆齐定理在一般情况下提供的对数大小界限要好得多。另一方面，在不可数基数中，稳定性这一模型论性质保证了一个比Erdős-Rado定理在一般情况下提供的界限大得多的均匀集。尽管稳定性的有限后果在文献中已得到广泛研究，但可数设置在先验上似乎相当不同，具体来说，在可数无限中仅基于基数的“大”概念并未揭示任何结构，因为拉姆齐定理在一般情况下已经提供了可数无限的均匀集。在本文中，我们证明了由上密度给出的自然“大”概念揭示出这些现象在可数情况下相遇：一个可数图具有正上密度的几乎团或反团，当且仅当它具有正上密度的几乎稳定集。此外，这一结果也自然地扩展到有限关系语言中的可数普遍理论模型。我们的方法探索了与稠密组合对象极限理论中收敛概念的关联，引入并研究了一种自然的近似Erdős-Hajnal性质，允许边（一般情况下的谓词）存在可忽略的误差，但要求在模型收敛序列中具有线性大小的均匀集（这比稳定正则性所能提供的要强得多，因为误差要求趋于零）。最后，令人惊讶的是，我们完全刻画了所有具有这种近似Erdős-Hajnal性质的有限图遗传类。证明突出了与原始猜想之间的差异和相似之处。
Keyword:
Ramsey theory
Erd & odblac
s-Hajnal Conjecture
graph limit
theon
stability
ultraproduct
期刊
J
IF:
0.9
论文数:
12
被引数:
0
机构
引用论文
暂无论文信息