Projects per year
Abstract
The upper density of an infinite graphG with V(G)⊆ℕ is defined as d̅(G)=lim supn→∞|V(G)∩{1,…,n}|/n. Let Kℕ be the infinite complete graph with vertex set ℕ. Cortsen, DeBiasio, Lamaison and Lang showed that in every 2-edge-colouring of Kℕ, there exists a monochromatic path with upper density at least (12+√8)/17. In this paper, we extend this result to k-edge-colouring of Kℕ for k≥3. We proved that (for k=3) every 3-edge-coloured Kℕ contains a monochromatic path with upper density at least 1/2, which is best possible. For k≥4, we prove that there exists a monochromatic path with upper density at least 1/(2k−4). Furthermore, we show that this problem can be deduced from its bipartite variant, which is of independent interest.
Original language | English |
---|---|
Article number | 103625 |
Number of pages | 8 |
Journal | European Journal of Combinatorics |
Volume | 110 |
Early online date | 11 Mar 2023 |
DOIs | |
Publication status | Published - May 2023 |
Fingerprint
Dive into the research topics of 'Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
A graph theoretical approach for combinatorial designs
Lo, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils