What is Ramsey-equivalent to a clique?
What is Ramsey-equivalent to a clique?
复制标题
拉姆齐相当于什么派系？
DOI：
10.1016/j.jctb.2014.06.003
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Tibor Szabó
中科院分区：
文献类型：
--
作者：
Jacob Fox;Andrey Grinshpun;Anita Liebenau;Yury Person;Tibor Szabó
如果 G 的每条双色边都包含 H 的单色副本，则图 G 是 H 的拉姆齐。如果每个图 G 都是 H 的拉姆齐当且仅当它是 H' 的拉姆齐，则两个图 H 和 H' 是拉姆齐等价的。在本文中，我们研究确定哪些图与完全图 K k 拉姆齐等价的问题。 Nešetřil 和 Rödl 的著名定理意味着任何拉姆齐等价于 K k 的图 H 都必须包含 K k。我们证明拉姆齐等价于 K k 的唯一连通图就是它本身。这对 Szabó、Zumstein 和 Zürcher 的问题给出了否定的答案：K k 是否拉姆齐等价于 K k⋅ K 2，k+ 1 个顶点上的图由带有下垂边的 K k 组成。事实上，我们证明了一个更强的结果。如果 H 是 Ramsey，但 G 没有真子图是 H 的 Ramsey，则图 G 是图 H 的 Ramsey 最小图。设 s (H) 是 H 的所有 Ramsey 最小图的最小最小度。Burr、Erdős 和 Lovász 介绍了 s (H) 的研究，他们证明 s (K k)=(k− 1) 2。我们证明 s (K k⋅ K 2)= k− 1，因此 K k 和 K k⋅ K 2 不等价于 Ramsey。我们还解决了哪些非连通图拉姆齐等价于 K k 的问题。令 f (k, t) 为最大 f，使得由 K k 和 K t 的 f 个不相交副本组成的图 H= K k+ f K t 与 K k 拉姆齐等价。 Szabó、Zumstein 和 Zürcher 给出了 f (k, t) 的下界。我们证明了 f (k, t) 的上限，该上限大致在下限的 2 倍之内。
A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H′ are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H′. In this paper, we study the problem of determining which graphs are Ramsey-equivalent to the complete graph K k. A famous theorem of Nešetřil and Rödl implies that any graph H which is Ramsey-equivalent to K k must contain K k. We prove that the only connected graph which is Ramsey-equivalent to K k is itself. This gives a negative answer to the question of Szabó, Zumstein, and Zürcher on whether K k is Ramsey-equivalent to K k⋅ K 2, the graph on k+ 1 vertices consisting of K k with a pendent edge. In fact, we prove a stronger result. A graph G is Ramsey minimal for a graph H if it is Ramsey for H but no proper subgraph of G is Ramsey for H. Let s (H) be the smallest minimum degree over all Ramsey minimal graphs for H. The study of s (H) was introduced by Burr, Erdős, and Lovász, where they show that s (K k)=(k− 1) 2. We prove that s (K k⋅ K 2)= k− 1, and hence K k and K k⋅ K 2 are not Ramsey-equivalent. We also address the question of which non-connected graphs are Ramsey-equivalent to K k. Let f (k, t) be the maximum f such that the graph H= K k+ f K t, consisting of K k and f disjoint copies of K t, is Ramsey-equivalent to K k. Szabó, Zumstein, and Zürcher gave a lower bound on f (k, t). We prove an upper bound on f (k, t) which is roughly within a factor 2 of the lower bound.
登录
查看更多内容
最小拉姆齐图的最小度
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
Raj Raina
通讯作者：
Raj Raina
Ramsey 最小图的最小度
影响因子：
0.9
作者：
J. Fox;Kathy Lin
通讯作者：
Kathy Lin
关于多种颜色的最小 Ramsey 图的最小度
DOI：
10.1016/j.jctb.2016.03.006
发表时间：
2015
期刊：
J. Comb. Theory B
影响因子：
--
作者：
J. Fox;A. Grinshpun;Anita Liebenau;Y. Person;Tibor Szabó
通讯作者：
Tibor Szabó
关于最小 Ramsey 图的最小度
影响因子：
0.9
作者：
Tibor Szabó;P. Zumstein;Stefanie Zürcher
通讯作者：
Stefanie Zürcher