论文标题
在Ramsey-Minimal Infinite图上
On Ramsey-minimal infinite graphs
论文作者
论文摘要
对于固定有限的图$ g $，$ h $，拉姆西理论中的一个常见问题是研究图$ f $，以便$ f \ to（g，h）$，即$ f $的每种红蓝色颜色都会产生a红色$ g $或a蓝色$ h $。我们将这项研究概括为无限图$ g $，$ h $;特别是，我们想确定是否有这种$ F $最少。这个问题与可自动化图的研究具有牢固的联系：无限图形，适当地包含自己的副本。我们证明了一些紧凑的结果将此问题与有限案例有关，然后给出一对$（g，h）$的一般条件，以使用Ramsey-Minimal图。我们使用这些证明，例如，如果$ g = s_ \ infty $是无限的星星，而$ h = nk_2 $，$ n \ ge 1 $是匹配的，则对$（s_ \ infty，nk_2）$承认没有Ramsey-Minimal图形。
For fixed finite graphs $G$, $H$, a common problem in Ramsey theory is to study graphs $F$ such that $F \to (G,H)$, i.e. every red-blue coloring of the edges of $F$ produces either a red $G$ or a blue $H$. We generalize this study to infinite graphs $G$, $H$; in particular, we want to determine if there is a minimal such $F$. This problem has strong connections to the study of self-embeddable graphs: infinite graphs which properly contain a copy of themselves. We prove some compactness results relating this problem to the finite case, then give some general conditions for a pair $(G,H)$ to have a Ramsey-minimal graph. We use these to prove, for example, that if $G=S_\infty$ is an infinite star and $H=nK_2$, $n \ge 1$ is a matching, then the pair $(S_\infty,nK_2)$ admits no Ramsey-minimal graphs.
