A large number of $m$-coloured complete infinite subgraphs

Abstract

Given an edge colouring of a graph with a set of $m$ colours, we say that the graph is $m$-\textit{coloured} if each of the $m$ colours is used. For an $m$-colouring $\Delta$ of ${\mathbb{N}}^{(2)}$, the complete graph on $\mathbb{N}$, we denote by ${\mathcal{F}}_{\Delta }$ the set all values $\gamma$ for which there exists an infinite subset $X\subset \mathbb{N}$ such that $X^{(2)}$ is $\gamma$-coloured. Properties of this set were first studied by Erickson in $1994$. Here, we are interested in estimating the minimum size of ${\mathcal{F}}_{\Delta }$ over all $m$-colourings $\Delta$ of ${\mathbb{N}}^{(2)}$. Indeed, we shall prove the following result. There exists an absolute constant $\alpha >0$ such that for any positive integer $m\ne \left\{\left(\genfrac{}{}{0ex}{}{n}{2}\right)+1,\left(\genfrac{}{}{0ex}{}{n}{2}\right)+2:n\ge 2\right\}$, $|{\mathcal{F}}_{\Delta }|\ge (1+\alpha )\sqrt{2m}$, for any $m$-colouring $\Delta$ of ${\mathbb{N}}^{(2)}$, thus proving a conjecture of Narayanan. This result is tight up to the order of the constant $\alpha$.

arXiv comment22 pages