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

Publication date: 21 January 2022

Abstract: The upper density of an infinite graph

G

with

V (G) s u b s e t e q m a t h b b N

is defined as

o v e r l i n e d (G) = l i m s u p_{n i g h t a r r o w i n f t y} | V (G) c a p 1, l d o t s, n | / n

. Let

K_{m a t h b b N}

be the infinite complete graph with vertex set

m a t h b b N

. Corsten, DeBiasio, Lamaison and Lang showed that in every

2

-edge-colouring of

K_{m a t h b b N}

, there exists a monochromatic path with upper density at least

(12 + s q r t 8) / 17

, which is best possible. In this paper, we extend this result to

k

-edge-colouring of

K_{m a t h b b N}

for

k g e 3

. We conjecture that every

k

-edge-coloured

K_{m a t h b b 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.

This page was built for publication: Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs