论文标题
单色跨越树和匹配有序完整的图表
Monochromatic spanning trees and matchings in ordered complete graphs
论文作者
论文摘要
可以嵌套，交叉或分离的两个独立的边缘。这些关系定义了六种类型的子图，具体取决于禁止的关系。我们完善了Erdős和Rado的言论，即完整图的每个边缘的每2个色都包含一个单色生成树。我们表明，禁止一个关系，我们始终在2边彩的有序完整图中具有单色（非象征性，非横断，非分离）跨越树。另一方面，如果禁止两种关系，那么我们有可能只有大小的单色（嵌套，分离，交叉），其顶点的一半是顶点的一半。在2色中，单色非巢式生成树的存在可验证扭曲图的更一般的猜想。我们的第二个主题是完善Ramsey数量的订购完整图。 Cockayne和Lorimer证明，对于给定的正整数t，n，m =（t-1）（n-1）+2n是最小的整数，具有以下属性：完整图的每个t颜色都包含与n个边缘的单色匹配。我们猜想了一个强化：在m顶点上的T色有序完整的图包含单色非巢和非分离匹配的n边缘。我们在某些特殊情况下证明了这个猜想。 （i）T+3顶点上的每个T色有序的完整图都包含一个单色的非态匹配，尺寸为2。 （ii）3N-1顶点上的每2色有序完整的图形都包含一个单色的非分离匹配尺寸n。 对于嵌套，分离和越野匹配，情况有所不同。在每种T颜色中的大小n的单色匹配度最小的最小m是前两种情况下的2（t（n-1））+1），在第三种情况下较小。
Two independent edges in ordered graphs can be nested, crossing or separated. These relations define six types of subgraphs, depending on which relations are forbidden. We refine a remark by Erdős and Rado that every 2-coloring of the edges of a complete graph contains a monochromatic spanning tree. We show that forbidding one relation we always have a monochromatic (non-nested, non-crossing, non-separated) spanning tree in a 2-edge-colored ordered complete graph. On the other hand, if two relations are forbidden, then it is possible that we have monochromatic (nested, separated, crossing) subtrees of size only half the number of vertices. The existence of a monochromatic non-nested spanning tree in 2-colorings of ordered complete graphs verifies a more general conjecture for twisted drawings. Our second subject is to refine the Ramsey number of matchings for ordered complete graphs. Cockayne and Lorimer proved that for given positive integers t, n, m=(t-1)(n-1)+2n is the smallest integer with the following property: every t-coloring of the edges of a complete graph Km contains a monochromatic matching with n edges. We conjecture a strengthening: t-colored ordered complete graphs on m vertices contain monochromatic non-nested and also non-separated matchings with n edges. We prove this conjecture for some special cases. (i) Every t-colored ordered complete graph on t+3 vertices contains a monochromatic non-nested matching of size two. (ii) Every 2-colored ordered complete graph on 3n-1 vertices contains a monochromatic non-separated matching of size n. For nested, separated, and crossing matchings the situation is different. The smallest m ensuring a monochromatic matching of size n in every t-coloring is 2(t(n-1))+1) in the first two cases and one less in the third case.
