Colour diversity in spanning structures under Dirac-type conditions

Abstract

Finding spanning structures with many distinct colours in properly edge-coloured graphs is a central theme in extremal combinatorics. A classical result of Andersen shows that every proper edge-colouring of the complete graph $K_n$ contains a Hamilton cycle with $n-O(n^{1/2})$ distinct colours. In the bipartite setting, the analogous question for perfect matchings is closely related to permutations in Latin squares. In this paper, we investigate how a Dirac-type minimum degree condition forces colour diversity in spanning structures. For every constant $1/2<c\le 1$, we prove the following. $\bullet$ Every properly edge-coloured graph $G$ on $n$ vertices with $\hat{I}´(G)\ge cn$ contains a Hamilton cycle with at least $cn-O(n^{1/2})$ distinct colours. $\bullet$ Every subset of an $n\times n$ Latin square with at least $cn$ cells in each row and each column contains a permutation with at least $cn-O(n^{2/3})$ distinct symbols. Both bounds are best possible up to the error term.

14 pages