论文标题
不对称图的拉姆齐等效性
Ramsey equivalence for asymmetric pairs of graphs
论文作者
论文摘要
如果有$ f $的边缘的任何红色/蓝色颜色为$ g $，则图形$ f $是一对图$（g，h）$的Ramsey（g，h）$，所有边缘有色红色或$ h $的副本均为$ h $，所有边缘颜色为蓝色。如果有相同的拉姆西图集合，则将两对图称为Ramsey等效。对称设置，即$ g = H $，受到了极大的关注。这导致了一个公开的问题，是否有连接的图$ g $和$ g'$，使得$（g，g）$和$（g'，g'）$是Ramsey等效的。我们在此问题的不对称版本上取得了进展，并确定了Ramsey等效图的几个非平凡家族。 某些恒星对Ramsey等效的连接图提供了第一个，尽管是微不足道的，虽然是微不足道的示例。我们的第一个结果是所有拉姆齐等效的恒星对。本文的其余部分重点介绍了$ $（t，k_t）$的对，其中$ t $是一棵树，$ k_t $是完整的图形。我们表明，如果$ t $属于某种树木家族，包括所有非平凡的恒星，那么$（t，k_t）$与Ramsey相当于形式的$ $（t，h）$的一对家族，其中$ h $是从$ k_t $中获得$ k_t $，通过将较小的较小的较小的cliques添加到其某些Vertices中。此外，我们确定$（t，h）$的拉姆西等于$（t，k_t）$，$ h $必须大致具有此表格。另一方面，我们证明，对于许多其他树$ T $，包括所有奇数至直径树，$（t，k_t）$都不等于任何此类对，甚至不与这对$（t，k_t \ cdot k_2）$，其中$ k_t \ cdot k_2 $ k_2 $是一个完整的图形$ k_t $ k_t $ k_t $ k_t $ a单端均匀。
A graph $F$ is Ramsey for a pair of graphs $(G,H)$ if any red/blue-coloring of the edges of $F$ yields a copy of $G$ with all edges colored red or a copy of $H$ with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case $G=H$, received considerable attention. This led to the open question whether there are connected graphs $G$ and $G'$ such that $(G,G)$ and $(G',G')$ are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several non-trivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form $(T,K_t)$, where $T$ is a tree and $K_t$ is a complete graph. We show that, if $T$ belongs to a certain family of trees, including all non-trivial stars, then $(T,K_t)$ is Ramsey equivalent to a family of pairs of the form $(T,H)$, where $H$ is obtained from $K_t$ by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for $(T,H)$ to be Ramsey equivalent to $(T,K_t)$, $H$ must have roughly this form. On the other hand, we prove that for many other trees $T$, including all odd-diameter trees, $(T,K_t)$ is not equivalent to any such pair, not even to the pair $(T, K_t\cdot K_2)$, where $K_t\cdot K_2$ is a complete graph $K_t$ with a single edge attached.
