Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs

Nicholas Day, Allan Lo*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number103625
Number of pages8
JournalEuropean Journal of Combinatorics
Volume110
Early online date11 Mar 2023
DOIs
Publication statusPublished - 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.

Cite this