Edge-colourings of K-n,K-n with no long two-coloured cycles

摘要

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Haggkvist in 1978 and, specifically, L(n, K-n,K-n) has received recent attention. Here we construct, for each prime power q >= 8, an edge-colouring of K-n,K-n with n colours having all two-coloured cycles of length <= 2q(2), for integers n in a set of density 1 - 3/(q - 1). One consequence is that L(n, K-n,K-n) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n - 4.