Generalized and geometric Ramsey numbers for cycles

详细信息    查看全文

• 作者：Ká ; rolyi ; Gyula ; et. al.
• 刊名：Theoretical Computer Science
• 出版年：2001
• 出版时间：July 28, 2001
• 年：2001
• 卷：263
• 期：1-2
• 页码：87-98
• 全文大小：127 K

文摘

Let C_n denote the cycle of length n. The generalized Ramsey number of the pair (C_n,C_k), denoted by R(C_n,C_k), is the smallest positive integer R such that any complete graph with R vertices whose edges are coloured with two different colours contains either a monochromatic cycle of length n in the first colour or a monochromatic cycle of length k in the second colour. Generalized Ramsey numbers for cycles were completely determined by Faudree–Schelp and Rosta, based on earlier works of Bondy, Erdős and Gallai. Unfortunately, both proofs are quite involved and difficult to follow. In the present paper we treat this problem in a unified, self-contained and simplified way. We also extend this study to a related geometric problem, where we colour the straight-line segments determined by a finite number of points in the plane. In this case, the monochromatic subgraphs are required to satisfy an additional (non-crossing) geometric condition.