Upper density of monochromatic infinite paths
Upper density of monochromatic infinite paths
复制标题
DOI：
10.19086/aic.10810
复制
发表时间：
2018-08
影响因子：
--
通讯作者：
Jan Corsten;Louis DeBiasio;Ander Lamaison;R. Lang
中科院分区：
文献类型：
--
作者：
Jan Corsten;Louis DeBiasio;Ander Lamaison;R. Lang
拉姆齐理论研究大型单色子结构的存在。与单色完全子图的最经典情况不同，双边彩色完全图中单色路径的最大保证长度是很好理解的。 Gerencsér 和 Gyárfás 在 1967 年证明，完整图 Kn 的任何两条边着色都包含一条具有 ⌊2n/3⌋+1 个顶点的单色路径。下面的双边着色表明这是最好的可能：将 Kn 的顶点划分为两个集合 A 和 B，使得 |A|=⌊n/3⌋ 和 |B|=⌈2n/3⌉，并将 A 和 B 之间的边着色为红色，将每个集合内的边着色为蓝色。最长的红色路径有 2|A|+1 个顶点，最长的蓝色路径有 |B|顶点。本文的主要结果涉及可数无限图的相应问题。为了测量单色子图的大小，我们将顶点与正整数相关联，并考虑单色子图的顶点集的下密度和上密度。正整数子集 A 的上密度是 |A∩{1,...,}|/n 的上极限，下密度是下极限。以下示例表明，不一定存在具有正上密度的单色路径，使其顶点形成递增序列：如果 ⌊log2i⌋≠⌊log2j⌋，则连接顶点 i 和 j 的边为红色，否则为蓝色。特别是，着色产生具有 1、2、4、8 等顶点的蓝色团，这些顶点通过红色边缘相互连接。同样，存在双边缘着色的构造，使得每个单色路径的较低密度为零。 1970 年代 Rado 的结果断言任何 k 边彩色可数无限完全图的顶点都可以被 k 条单色路径覆盖。对于正整数上的双边彩色完全图，这意味着存在上密度至少为 1/2 的单色路径。 1993年，Erdős和Galvin提出了确定最大c的问题，使得正整数上的完整图的每一条两条边着色都包含一条上密度至少为c的单色路径。作者通过证明 c=(12+8–√)/17≈0.87226 解决了这个 25 年前的问题。
Ramsey Theory investigates the existence of large monochromatic substructures. Unlike the most classical case of monochromatic complete subgraphs, the maximum guaranteed length of a monochromatic path in a two-edge-colored complete graph is well-understood. Gerencsér and Gyárfás in 1967 showed that any two-edge-coloring of a complete graph Kn contains a monochromatic path with ⌊2n/3⌋+1 vertices. The following two-edge-coloring shows that this is the best possible: partition the vertices of Kn into two sets A and B such that |A|=⌊n/3⌋ and |B|=⌈2n/3⌉, and color the edges between A and B red and edges inside each of the sets blue. The longest red path has 2|A|+1 vertices and the longest blue path has |B| vertices. The main result of this paper concerns the corresponding problem for countably infinite graphs. To measure the size of a monochromatic subgraph, we associate the vertices with positive integers and consider the lower and the upper density of the vertex set of a monochromatic subgraph. The upper density of a subset A of positive integers is the limit superior of |A∩{1,...,}|/n, and the lower density is the limit inferior. The following example shows that there need not exist a monochromatic path with positive upper density such that its vertices form an increasing sequence: an edge joining vertices i and j is colored red if ⌊log2i⌋≠⌊log2j⌋, and blue otherwise. In particular, the coloring yields blue cliques with 1, 2, 4, 8, etc., vertices mutually joined by red edges. Likewise, there are constructions of two-edge-colorings such that the lower density of every monochromatic path is zero. A result of Rado from the 1970's asserts that the vertices of any k-edge-colored countably infinite complete graph can be covered by k monochromatic paths. For a two-edge-colored complete graph on the positive integers, this implies the existence of a monochromatic path with upper density at least 1/2. In 1993, Erdős and Galvin raised the problem of determining the largest c such that every two-edge-coloring of the complete graph on the positive integers contains a monochromatic path with upper density at least c. The authors solve this 25-year-old problem by showing that c=(12+8–√)/17≈0.87226.