On unavoidable‐induced subgraphs in large prime graphs
On unavoidable‐induced subgraphs in large prime graphs
复制标题
关于大素图中不可避免的导出子图
作者：
M. Malliaris;C. Terry
Chudnovsky、Kim、Oum 和 Seymour 最近证实，任何素数图都包含一个简短的归纳素数子图列表之一 [1]。在本文中，我们使用许多相同的想法来反驳他们的定理，但关键的模型理论要素是首先确定所谓的图的稳定性量。这种方法改变了适用的拉姆齐定理，改进了界限，并为所讨论的图提供了不同的结构视角。作为补充，我们给出了暗示有限结果的无限证明。
Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs [1]. In the present article, we reprove their theorem using many of the same ideas, but with the key model‐theoretic ingredient of first determining the so‐called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof that implies the finite result.