Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs
Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs
复制标题
DOI：
10.1016/j.ejc.2022.103625
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
A. N. Day;A. Lo
中科院分区：
文献类型：
--
作者：
A. N. Day;A. Lo
定义V（G）≠ N的无限图G的上密度为d <$（G）= lim supn →∞| V（G）{1，...，n}|/n.设KN是顶点集为N的无限完全图. Corsten，DeBiasio，Lamaison和Lang证明了在K-N的每一个2-边着色中，都存在一个最大密度至少为（12+ 8）/17的单色路径，这是最好的可能。本文将这一结果推广到了K-N（k≥ 3）的k-边染色.我们猜想每个k边着色的KN都包含一条单色路径，其上密度至少为1/（k− 1），这是最好的可能性（当k− 1是素数幂时）。我们证明，这是真的，当k= 3和渐近当k= 4。此外，我们表明，这个问题可以推导出它的二分变体，这是独立的利益。
The upper density of an infinite graph G with V (G)⊆ N is defined as d¯(G)= lim sup n→∞| V (G)∩{1,…, n}|/n. Let K N be the infinite complete graph with vertex set N. Corsten, DeBiasio, Lamaison and Lang showed that in every 2-edge-colouring of K N, there exists a monochromatic path with upper density at least (12+ 8)/17, which is best possible. In this paper, we extend this result to k-edge-colouring of K N for k≥ 3. We conjecture that every k-edge-coloured K N contains a monochromatic path with upper density at least 1/(k− 1), which is best possible (when k− 1 is a prime power). We prove that this is true when k= 3 and asymptotically when k= 4. Furthermore, we show that this problem can be deduced from its bipartite variant, which is of independent interest.