Colour diversity in spanning structures under Dirac-type conditions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912930132393984 |
|---|---|
| author | Cheng, Xinbu Huang, Xinqi Liu, Hong Wang, Bin Yan, Zhifei |
| author_facet | Cheng, Xinbu Huang, Xinqi Liu, Hong Wang, Bin Yan, Zhifei |
| contents | 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 $δ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23801 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Colour diversity in spanning structures under Dirac-type conditions Cheng, Xinbu Huang, Xinqi Liu, Hong Wang, Bin Yan, Zhifei Combinatorics 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 $δ(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. |
| title | Colour diversity in spanning structures under Dirac-type conditions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.23801 |